Циклические алгоритмы. Алгоритм Евклида.

Т

Урок 45

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

Цель: - дать учащимся представление о циклических алгоритмах и возможностях их использования;

- познакомить с механизмом реализации Алгоритма Евклида на языке Паскаль

- построение трассировочной таблицы при решении циклических задач.

Повторение

1. Ответить на вопросы по § 12.6

- Назовите этапы решения задачи на ЭВМ

- Что означает термин «число перестановок»?

- Что такое факториал и какова его расчетная формула?

- Что такое цикл?

- Как работает цикл с предусловием?

- Запишите оператор цикла «пока» на Паскале.

2. Проверка д/з: № 7 к § 12.7

Слайд 8 (При объяснении нового материала используется презентация)

Алгоритм Евклида — это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.

Пусть M и N одновременно не равные нулю целые неотрицательные числа и пусть M ≥ N. Если M=N, то НОД(M, M)=M, а если M≠N, то для чисел M и N выполняется равенство

НОД(M, N) = НОД(M-N, N).

Например, пусть х=12, а у=18.

НОД(12,18) = НОД(12,6) = НОД(6,6).

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

Пример

Написать программу нахождения наибольшего общего делителя двух неотрицательных чисел.

Блок-схема алгоритма Евклида (Слайд 9)

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

Решение

Для решения данной задачи воспользуемся циклом с предусловием:

Program Evklid;

Var M, N: Integer;

Begin

Writeln ('Введите два числа');

Readln(M, N);

While M<>N do

Begin

If M>N Then M:=M – N Else N:=N-M;

End

Writeln('HOД=', M);

Readln;

End.

Для проверки правильности работы составленного алгоритма, составим трассировочную таблицу алгоритма для исходных данных M=32, N=24

Домашняя работа: вычислить сумму всех положительных целых чисел, не превышающих данного натурального числа N. (Слайд 10)

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

Затем все проверяют свое решение задачи «Алгоритм Евклида» на ПК.

Практическая работа оценивается.

Обычно оценка «5» - полностью самостоятельное решение задач; «4» - задачи решены, но с небольшими недоработками, устраненными с помощью учителя; «3» - воспроизводство, т.е. отладка и получение результата по готовой программе.

Правильность программ проверим путем тестирования на компьютере.

Практическая работа (Слайд 10)

1. №7 – домашнее задание (может быть проверено визуально в рабочих тетрадях)

2. №9 стр. 380

Выполнить на компьютере программу Evklid. Протестировать ее на значениях

M=32, N=24 (Ответ: 8); M=696, N=234 (Ответ: 6).

Домашнее задание: (Слайд 11)

§ 12.6, 12.7 (читать, отвечать на вопросы: №1-6 устно, № 8, 10, 11* письменно)

№8: Дано целое число Х и натуральное N. Составить алгоритм вычисления Х^N. Проверить алгоритм трассировкой. Написать программу на Паскале.

№10: Составить программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу:

НОД(А, В, С) = НОД(НОД(А,В),С).

№11*: Составить программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:

А×В = НОД(А,В) × НОК(А,В).

* - дополнительное задание, не являющееся обязательным.