Тема: «Применение алгоритма Евклида при решении задач »

Задача 1 На какое число квадратов можно разделить прямоугольник 9 5, если каждый раз отрезать от него квадрат максимального размера?

Имеется прямоугольник 9 5

Максимальный размер квадрата, который мы можем врезать из прямоугольника 9 5 равен 5 5, так, как минимальная сторона прямоугольника равна 5. После того, как мы отрежем один квадрат останется прямоугольник 4 5.

На следующем шаге мы отрежем квадрат размером 4 4, так как минимальная сторона оставшегося прямоугольника равна 4. После этого останется прямоугольник 4 1. Из которого мы можем вырезать 4 квадрата размером 1 1. Т. о. прямоугольник 9 5 мы разрезали на шесть квадратов.

На какое же число квадратов можно разделить прямоугольник m n, если каждый раз отрезать от него квадрат максимального размера?

Для того, чтобы узнать какой квадрат максимального размера можно вырезать из того или иного прямоугольника, необходимо сравнить значения его сторон. Найти значение наименьшей стороны, и вырезать из прямоугольника квадрат со стороной равной данной. При этом длина наибольшей стороны прямоугольника уменьшается на величину минимальной из сторон

Подобную операцию нам необходимо будет произвести не один раз! До каких же пор мы будем делить прямоугольник на квадраты максимального размера?

?

Прямоугольник m n мы будем делить до тех пор, пока m не станет равна n! Как же посчитать количество квадратов, на которые мы разрежем таким образом прямоугольник?

Задача 2 «Кузнечик» Вперед 2 Назад 2 Кузнечик находится на числовой прямой и может выполнять следующие команды: Какие значения может принимать координата кузнечика?

Координата кузнечика может быть равна: … … Вперед 2 Назад 2 НОД(2,2)=2

Координата кузнечика может быть равна: … … Вперед 3 Назад 3 НОД(3,3)=3

Координата кузнечика может быть равна: … … Вперед 6 Назад 3 НОД(3,6)=3

Координата кузнечика может быть равна: … … Вперед 7 Назад 5 Демонстрация «кузнечик» НОД(7,5)=1

Задача 3 «Водолей! Имеются два сосуда емкостью A и B литров каждый и неограниченный источник воды. Первоначально оба сосуда пусты. Требуется набирая воду в эти сосуды и переливая из одного в другой, получить в каком-либо из них требуемое количество воды за наименьшее число переливаний. При этом сосуды разрешается опорожнять только полностью!

Пусть, например, сосуды имеют емкости 5 и 7 литров соответственно, а получить требуется один литр. Как это сделать? Демонстрация «Водолей»

ДействиеA=7лB=5л Налить В 05 Перелить из В в А 50 Налить в 55 Перелить из В в А 73 Вылить из А 03 Перелить из В в А 30 Налить В 35 Перелить из В в А 71

Заметим, что нам потребовалось три раза налить 5 – литровый сосуд и два раза опорожнить 7- литровый, что соответствует равенству: 1=5*3-7*2. Эта формула по сути является способом представить наибольший общий делитель (НОД) двух чисел (5 и 7) в виде разности чисел. Как известно из математики, для НОД такое представление существует всегда. Мало того, если требуемое число литров не является кратным НОД емкостей исходных сосудов, тол такое представление невозможно в принципе!

Можно ли отмерить 3 литра с помощью сосудов емкостью 4 и 8 литров? Можно ли отмерить 2 литра с помощью сосудов емкостью 4 и 8 литров? Можно ли отмерить 4 литра с помощью сосудов емкостью 4 и 8 литров? Можно ли отмерить 3 литра с помощью сосудов емкостью 21 и 6 литров? Можно ли отмерить 1 литр с помощью сосудов емкостью 15 и 5 литров?

Оказывается, что всегда можно отмерить количество литров, кратное НОД(А,В) и не превышающее емкость большего сосуда.

Рассмотрим случай, когда А=7л, а В=5 л, требуется получить 2 литра. Вышеприведенная схема позволяет получить результат за 18 переливаний (2=5*6-7*4) ДействиеА=7лB=5лB=5л Налить B05 Перелить из B в A50 Налить B55 Перелить из B в A73 Вылить из A03 Перелить из B в A30 Налить B35 Перелить из B в A71 Вылить из A01 Перелить из B в A10 Налить B15 Перелить из B в A60 Налить B65 Перелить из B в A74 Вылить из A04 Перелить из B в A40 Налить B45 Перелить из B в A72

Хотя в данном случае можно обойтись всего двумя переливаниями (2=7*1-5*1) ДействиеА=5лА=5лB=7л Налить B07 Перелить из B в A52 Для этого достаточно поменять сосуды местами.

Таким образом, для выявления более экономичного представления необходимо сравнить число переливаний в случае, когда с помощью меньшего сосуда наполняют больший, с числом переливаний в противном случае и выбрать наилучшее решение.