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

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

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

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

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

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

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

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

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

9 ?

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

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

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

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

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

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

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

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

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

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

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

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

22 Рассмотрим случай, когда А=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

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

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