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


Т

Урок 45

ема: «Циклические алгоритмы.

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


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

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

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


Повторение


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

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

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

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

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

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

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


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


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


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


Пусть M и N одновременно не равные нулю целые неотрицательные числа и пусть MN. Если M=N, то НОД(M, M)=M, а если MN, то для чисел 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


Шаг

Операция

M

N

Условие

Ввод M

32



Ввод N


24


M ≠ N



3224, да

M>N



32>24, да

M:=M-N

8



M ≠ N



824, да

M>N



8>24, нет

N:=N-M


16


M ≠ N



8≠16, да

M>N



8>16, нет

N:=N-M


8


MN



88, нет

Вывод M

8



Конец







Домашняя работа: вычислить сумму всех положительных целых чисел, не превышающих данного натурального числа 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*: Составить программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:

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



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


Полный текст материала Циклические алгоритмы. Алгоритм Евклида. смотрите в скачиваемом файле.
На странице приведен фрагмент.
Автор: Криворотова Лариса Николаевна  klarisa
19.11.2009 2 8673 1982

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



А вы знали?

Интересные инструкции по ПК

Лучшие материалы сайта для вас
Оставьте отзыв к материалу:
Всего: 2
avatar
1 [Материал] некрасова • 11:25, 11.12.2009
спасибо
[Материал]
avatar
2 klarisa • 19:35, 18.12.2009
Очень рада, если вам пригодилось
[Материал]