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

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

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

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

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

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

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

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

?

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

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

Задача 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

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

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

Заметим, что нам потребовалось три раза налить 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 Для этого достаточно поменять сосуды местами.

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

Существует быстрый алгоритм нахождения наибольшего общего делителя, который благодаря своим особенностям, допускает более эффективную реализацию на компьютере, нежели рассмотренные ранее алгоритмы. 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;

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

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