Программа по математике. Углубленное изучение.

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

Задачи:

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

Повторить: основные типы данных языка программирования 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; со следующим содержимым (текст процедуры написан на псевдокоде):

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

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

2=7x1-5x1

2=5x6-7x4

2=7x6-5x8

2=5x13-7x9…

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

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

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 мин.

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

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

Скачано с www.znanio.ru