Алгоритм Евклида

Цель урока: познакомить учащихся с этапами решения расчетной задачи на компьютере; рассказать о программирование циклов с предусловием на Паскале; научить составлять программу нахождения наибольшего общего делителя (НОД) двух натуральных чисел.
Тип урока: объяснение нового материала.

Основные понятия: Цикл, блок-схема, трассировочная таблица, программа на АЯ и на Паскале.
Оборудование: ПК, трассировочные таблицы для КОЗ № 2, учебник «Информатика. Базовый курс. 9 класс»

Ход урока:

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

Проверка домашнего задания:
- Что такое цикл;

- Какими бывают циклы;

- Как описывается цикл на языке блок-схем, алгоритмическом языке.

Вводная беседа учителя: вы уже почувствовали себя настоящими программистами, составляя линейные и ветвящиеся программы на Паскале? Если ещё нет, то тогда у вас есть такая возможность. Сегодня, на примере конкретной задачи, мы научимся программировать циклы на языке Паскаль.

II. Объяснение нового материала:

Учитель рассказывает об этапах решения задач:

1. Постановка задачи. (Что дано и что требуется найти.)

2. Математическая формализация. (Математическая модель.)

3. Построение алгоритма. (Блок-схема и алгоритмический язык (АЯ).)

4. Составление программы на языке программирования. (Программирование.)

5. Отладка и тестирование программы. (Испытания работы программы и исправление обнаруженных ошибок.)

6. Проведение расчетов и анализ полученных результатов. (Использование программы в практических целях.)

Ребята получают следующие карточки с заданиями:

Карточка для учеников.

Определить НОД двух чисел.

1 этап. Постановка задачи.

Дано: N,M.

Найти: НОД(N,M).

2 этап. Построить математическую модель на основе словесной модели.

Алгоритм Евклида.

1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;

2) заменить большее число разностью большего и меньшего из чисел;

3) вернуться к выполнению п.1.

Пример
Дано: M = 32, N = 24. Найти: НОД(M,N).

Ответ: НОД(32,24) = 8.

3 этап. Описание алгоритма Евклида блок-схемой.

Структура алгоритма – цикл-пока с вложенным ветвлением. Цикл повторяется, пока M и N не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.

4,5 этап. Алгоритм на АЯ и программа на Паскале.
Вставить программы на АЯ и Паскале.

6 этап. Использование программы в практических целях

Задача 3: На ПК Вам необходимо испытать программу для данных, проверенных трассировочной таблицей: ( 27, 36 ); ( 48, 54 ); ( 54, 72 ); ( 78, 130); ( 153, 187 ). На каждую пару чисел Вам отводится 3 минуты. Значения должны совпасть с ответами тестирования трассировочных таблиц.

Модульный ответ: Правильные значения (9 ; 6 ; 18 ; 26 ; 17 ).

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

III. Домашнее задание: Всем: пар. 39,40 учебника.

По желанию: Задача: Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу: А*В = НОД(А,В)*НОК(А,В). Протестировать программу с помощью трассировочной таблицы для значений А= 12, В= 21. Ответом должно быть натуральное число. За каждый правильно выполненный этап программирования Модульный ответ: Программа проверяется на ПК в классе. Ответ теста: 84.