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

Задачи:

Образовательные

• Повторить: основные типы данных языка программирования Turbo Pascal; структуру программы на языке программирования Turbo Pascal; операцию присваивания; основные алгоритмически конструкции; алгоритм Евклида.
• Рассмотреть применение алгоритма Евклида при решении различных задач (задача о разрезании прямоугольника, кузнечик, водолей).
• Познакомить с быстрым алгоритмом нахождения наибольшего общего делителя.

Воспитательные

• Продолжить воспитывать у ребят: уважение друг к другу; умение слушать ответ товарища.
• Продолжить формировать у учащихся: аккуратность пи работе с записями в тетради; умение работать в коллективе; пунктуальность.
• Продолжить знакомство с вузовскими формами организации учебных занятий.

Развивающие

• Продолжить формирование умений: решать задачи; высказывать умозаключения; делать логические заключения на основе имеющихся знаний; владеть основными алгоритмическими конструкциями и использовать их для построения алгоритмов; производить численные расчеты на компьютере с использованием стандартных функций; использовать стандартные алгоритмы для решения учебных задач; работать с источниками печатной информации.
• Продолжить развитие: логического мышления; памяти и внимания; самостоятельности в суждениях и работе.

Программное обеспечение:

• OS Windows 2000/XP,
• Алгоритмика 5-7,
• TurboPascal

Методическое оснащение:

• презентация (Приложение 4),
• программы по теме на языке программирования Turbo Pascal (Приложение 1).

Ход учебного занятия

Семинар базируется на материале предыдущей лекции, и посвящается отработке знаний. Семинар организую так: на экран проецирую задания А и Б, ученики знакомятся с ними и выбирают себе программу для работы. Затем они начинают читать учебник и записи в тетрадях, советуются друг с другом, консультируются с учителем. После этого проблема обсуждается и дается новое задание. В конце урока учащиеся выполняют самостоятельную работу.

I. Организационный момент

Время: 1 мин.

Цели данного этапа: психологический настрой класса.

Метод: объяснение

Приветствие, установление дисциплины. Объявление темы и плана учебного занятия, а так же его цели для учащихся.

План.

Задача №1

Задача №2

Задача №3

Более эффективная (для компьютера) версия алгоритма Евклида

II. Информация учителя о домашнем задании.

Время: 1 мин.

Цель данного этапа: пояснить содержание домашнего задания.

Метод: объяснение с элементами беседы

Индивидуальные задания по задачнику.

Для учащихся, успешно программирующих на языке программирования Turbo Pascal, предлагается ознакомиться с программами из приложения (Приложение1)

III. Подготовка к активному и осознанному усвоению нового учебного материала. Этап постановки доминирующей цели учебного занятия.

Время: 1 мин.

Цель данного этапа: подготовка учащихся к восприятию нового учебного материала

Метод: беседа

IV. Усвоение новых знаний.

Цель данного этапа: усвоение нового учебного материала

1. Постановка первой задачи

Время: 1 мин.

Метод: Беседа

Учитель разъясняет условие задачи, при этом использует метод “беседа” (см. презентацию).

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

Учащиеся: Максимальный квадрат, который мы можем вырезать из этого прямоугольника равен 5? 5.

Учитель. А какова будет величина прямоугольника, когда мы отрежем от него квадрат?

Учащиеся. Оставшийся прямоугольника будет размером 4? 5.

Учитель. Какой максимальный квадрат мы можем вырезать из прямоугольника 4? 5?

Учащиеся. 4? 4…и т.д.

Учитель. На сколько же квадратов нам удалось разделить этот прямоугольник?

Учащиеся. Прямоугольник 9? 5 нам удалось разделить на шесть квадратов.

2. Самостоятельная работа учащихся

Время: 2 мин.

Метод: Практический

После этого учащиеся самостоятельно составляют алгоритм решения задачи и записывают его на языке программирования (т.е работают по программам А и Б; каждый выбирает программу действий сам).

3. Обсуждение результатов самостоятельной работы

Время: 2 мин.

Метод: Беседа

Ребята делятся своими алгоритмами решения задачи. После этого учитель обобщает все сказанное учащимися и проговаривает алгоритм решения задачи.

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

Учитель. Рассмотрим прямоугольник 63? 77. Для того, чтобы дать ответ на поставленную задачу мы вычтем из большей стороны меньшую и полученной разностью заменим значение большей стороны. Получим прямоугольник 63? 14. С этими сторонами, согласно нашему алгоритму будем проделывать ту же самую процедуру, и так до тех пор, пока не получим две одинаковые стороны.

Интересно, что число 7 является НОД пары чисел 63 и 77, и нашли мы его, вычитая каждый раз из больше стороны меньшую и заменяя ее значение их разностью, а это ведь и есть алгоритм Евклида (с которым вы познакомились на прошлом занятии) алгоритм нахождения наибольшего общего делителя пары чисел!

Давайте вспомним, как же мы доказали правильность этого алгоритма?

Учащиеся. При доказательстве алгоритма Евклида мы заметили, что если числа m и n, делятся на b, то и их разность делится на b. Следовательно, указанная операция над набором чисел сохраняет общие делители набора. Таким образом, на каждом шаге алгоритма множество общих делителей не меняется. Далее мы учитывали, что при указанных преобразованиях числа набора остаются неотрицательными. Действительно, вычитая из положительного числа меньшее (или равное ему), мы получим неотрицательное число. Поэтому операцию вычитания можно осуществлять до тех пор, пока в наборе есть хотя бы два положительных числа. И, наконец, процесс обязательно закончится, так как после каждого вычитания сумма чисел набора уменьшается. В то же время эта сумма всегда есть положительное целое число, следовательно, алгоритм не может длиться бесконечно (очевидно, что число шагов не превышает суммы чисел исходного набора).

4. Постановка второй задачи

Время:1 мин.

Метод: Беседа

5. Самостоятельная работа учащихся

Время: 4 мин.

Метод: Практический

После этого учащиеся самостоятельно составляют алгоритм решения задачи и записывают его на языке программирования (т.е работают по программам А и Б; каждый выбирает программу действий сам).

6. Обсуждение результатов самостоятельной работы

Время: 4 мин.

Метод: Беседа

Ребята делятся своими алгоритмами решения задачи. После этого учитель обобщает все сказанное учащимися и проговаривает алгоритм решения задачи. В процессе обсуждения выяснятся, что кузнечик может побывать только в координатах, кратных наибольшему общему делителю шагов k и l(вперед k, назад l).

Затем ребята предлагают свои варианты записи данного алгоритма (Приложение2).

7. Постановка третьей задачи

Время: 1 мин.

Метод: Беседа

8. Самостоятельная работа учащихся

Время: 4 мин.

Метод: Практический

Учащиеся самостоятельно составляют алгоритм решения задачи и записывают его на языке программирования (т.е работают по программам А и Б; каждый выбирает программу действий сам).

9. Обсуждение результатов самостоятельной работы

Время: 4 мин.

Метод: Беседа

Ребята делятся своими алгоритмами решения задачи, и новой для них информацией.

После этого учитель обобщает все сказанное учащимися и проговаривает алгоритм решения задачи. (В процессе обсуждения выяснятся, что с помощью заданных сосудов можно отмерить только количество литров, кратное наибольшему общему делителю емкостей сосудов!)

Пусть, например, сосуды имеют емкости 5 и 7 литров соответственно, а получить требуется 1 литр. Методом проб и ошибок можно нащупать следующую последовательность из 8 шагов (она проиллюстрирована рисунком  и демонстрируется с использованием интерактивного задачника Алгоритмика 2.0 ).

Стоит заметить, что все вышеперечисленные переливания укладываются в несложную схему. Определим вначале процедуру с названием Налить_до_краев_A; со следующим содержимым (текст процедуры написан на псевдокоде):

procedure Налить_до_краев_A;

BEGIN

налить B;

while not(A полный) do перелить из A в B;

END.

Тогда основная программа будет иметь следующую структуру:

BEGIN

{основной цикл}

while ((B<>требуемое) and (A<>требуемое)) do

begin

Налить_до_краев_A;

Вылить_из_A;

Перелить_из_B_в_A;

end;

END.

При выполнении основного цикла while в сосуде B поочередно остается 3, 1, 4, 2, 0... литров воды (все числа, меньшие B). Если НОД(A,B)?1, то некоторые из чисел будут пропущены, останутся только числа, кратные НОД(A,B). Для A=10 и B=6 последовательность имеет вид 0, 2, 4, 0 ...

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

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

Все предыдущее рассмотрение никак не затрагивает вопрос о минимальности количества переливаний.

Рассмотрим ситуацию, когда A=7 л, B=5 л, требуется получить 2 литра. Вышеприведенная схема позволяет получить результат за 18 переливаний (2=5x6-7x4) (см. таблицу).

Хотя в данном случае можно обойтись всего двумя переливаниями (2=7*1-5*1):

Для этого достаточно поменять сосуды местами (см. таблицу).

Вообще говоря, существует бесконечно много представлений числа, кратного НОД данных чисел, в виде суммы чисел, кратных данным. Для рассмотренных выше A=7 и B=5 это, например, представления

2=7x1-5x1

2=5x6-7x4

2=7x6-5x8

2=5x13-7x9…

Оказывается, зная одно из этих представлений, можно получить все остальные.

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

10. Постановка четвертой задачи

Время: 1 мин.

Метод: беседа

Программа А	Программа Б
Познакомиться по учебным пособиям с более эффективной (для компьютера) версией алгоритма Евклида записанной на псевдоязыке.	Познакомиться по учебным пособиям с более эффективной (для компьютера) версией алгоритма Евклида записанной на языке программирования TurboPascal.

11. Самостоятельная работа учащихся

Время: 5 мин.

Метод: практический

Учащиеся знакомятся с алгоритм решения задачи (т.е работают по программам А и Б; каждый выбирает программу действий сам).

12. Обсуждение результатов самостоятельной работы

Время: 3 мин.

Метод: беседа

Ребята делятся своими алгоритмами решения задачи, и новой для них информацией.

После этого учитель обобщает все сказанное учащимися (пошагово разбирается алгоритм решения).

Долгое время описанный алгоритм Евклида был самым эффективным способом отыскания наибольшего общего делителя, однако с появлением электронно-вычислительных машин ситуация изменилась (алгоритм Евклида, вроде бы :-), появился задолго до вычислительных машин). Учет особенностей выполнения арифметических операций компьютером позволил построить более эффективную (для компьютера) версию алгоритма Евклида.

Действительно, для оценки трудоемкости алгоритма логично будет не просто считать общее число операций, но и учитывать время, которое требуется для выполнения этих операций. Так, например, операция умножения включает в качестве промежуточных операций несколько сложений, а операция деления – несколько умножений и вычитаний. В вычислительных машинах реализована так называемая двоичная арифметика. В этой арифметике очень легко умножать и делить числа на 2. Это достигается простым сдвигом цифр (подобно тому, как в десятичной арифметике простым добавлением и удалением нуля осуществляется умножение и деление на 10). Существует быстрый алгоритм нахождения наибольшего общего делителя, который благодаря своим особенностям допускает более эффективную реализацию на компьютере, нежели описанные выше алгоритмы.

Справедливы соотношения

НОД(2a,2b)=2? НОД(a,b); НОД(2a, b)=НОД(a,b) при нечетном b

Записанный на “псевдо” языке программирования алгоритм см. в приложении (Приложение3)

Паскалевский вариант этого алгоритма представлен ниже.

d:=1;

while ((a<>0) and (b<>0)) do

begin

if (not(Odd(a) or Odd(b)))

then begin d:= d*2; 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<=b)) then b:= b-a;

end;

if (a=0) then nod1:= d*b else nod1:= d*a;

После ознакомления учащихся с учебным материалом следует его обсуждение (пошаговое рассмотрение работы программы при различных значениях переменных a и b)

V. Закрепление новых знаний

Время: 4 мин.

Метод: практический

Цель данного этапа: применение знаний на практике и формирование практических умений и навыков.

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

Решение.

Чтобы разрезать прямоугольник на минимальное число равновеликих квадратов, длина этих квадратов должна быть максимально возможной, а длина и ширина прямоугольника должны нацело делиться на длину квадрата. Значит, длина квадрата равна d=НОД(n, m). Число вертикальных разрезов (см. рис) равно (n div d)-1, а число горизонтальных разрезов, соответственно равно (m div d)-1. Таким образом, для того, чтобы разрезать прямоугольник m? n на равновеликие квадраты максимальной площади нужно провести ((n+m) div d)-2 прямолинейных разрезов.

VI. Подведение итогов

Время: 1 мин.

Цель данного этапа: Подвести итоги урока

Учитель подводит итог работы класса и отдельных учащихся, называет отличившихся, выставляет оценки.

Литература:

1. Патрушев Г. О. Основы программирования: учебное пособие. Часть I – Красноярск: РИО КГПУ, 2001. – 260 с.
2. А. К. Звонкин, А. Г. Кулаков, С. К. Ландо, А. Л. Семенов, А. Х. Шень. Алгоритмика 5-7:Учебник и задачник для общеобразовательных учебных заведений-М: Дрофа, 1996, 1997