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

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

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

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 На языке программирования TurboPascal, это запишется следующим образом: If (m>n) then m:=(m-n) else n:=(n-m); Подобную операцию нам необходимо будет произвести не один раз! До каких же пор мы будем делить прямоугольник на квадраты максимального размера?

9 ?

10 Прямоугольник m n мы будем делить до тех пор, пока m не станет равна n! While (mn) do begin If (m>n) then m:=(m-n) else n:=(n-m); end; Как же посчитать количество квадратов, на которые мы разрежем таким образом прямоугольник?

11 i:=1; while (mn) do begin if (m>n) then m:=(m-n) else n:=(n-m); i:=i+1; end;

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

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

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

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

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

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

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

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

20 Определим процедуру Налить_до_краев_А на псевдокоде: Procedure Налить_до_краев_А; Begin while not (А полный) do Begin Налить_В; Перелить_из_В_в_А; End;

21 Тогда основная программа будет иметь следующую структуру: BEGIN While (Bтребуемое) and Aтребуемое) do begin Налить_до_краев_А; Вылить_из_ А; Перелить_из_В_в_А; end; END.

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

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

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

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

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

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

28 Существует быстрый алгоритм нахождения наибольшего общего делителя, который благодаря своим особенностям, допускает более эффективную реализацию на компьютере, нежели рассмотренные ранее алгоритмы. d:=1; While оба числа a и b четные do begin a:=a div 2; b:=b div 2; end; While оба числа a и b отличны от нуля do begin If одно из a,b отличны от нуля do begin if одно из a, b четное then поделить его на 2 else заменить большее из а,b их разностью end; NOD:=(ненулевое из a, b)*d end;

29 d:=1; While a0 and b0 do begin If not odd(a) and odd(b) then begin a:=a div 2; b:=b div 2; end else if not odd(a) and odd(b) then a:=a div 2 else if odd(a) and not odd(b) then b:=b div 2 else if (odd(a) and odd(b) and (a>=b) then a:=a-b else if odd(a) and odd(b) and (a

30 Домашнее задание Какое минимальное число (k>0) прямолинейных разрезов нужно произвести, чтобы разрезать прямоугольник m n на равновеликие квадраты максимальной площади?