Уроки 50 - 51
§39. Ветвления и циклы

Содержание урока

Пример задачи

Исполнитель Раздвоитель

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

Выводы. Интеллект-карта

Вопросы и задания

Практическа работа № 30 «Ветвления и циклы»

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

Древнегреческий математик Евклид, живший в III веке до нашей эры, придумал замечательный алгоритм для вычисления наибольшего общего делителя (НОД) двух натуральных чисел. Этот алгоритм и сейчас используется, например в задачах шифрования. Напомним, что НОД — это наибольшее число, на которое два заданных числа делятся без остатка.

Алгоритм Евклида для натуральных чисел: заменять большее из двух заданных чисел на их разность до тех пор, пока числа не станут равны. Полученное число и есть их НОД.

Алгоритм Евклида можно записать более строго в виде последовательности шагов:

Вход: натуральные числа а, b.

Шаг 1. Если а = b, то перейти к шагу 7.

Шаг 2. Если а < b, то перейти к шагу 5.

Шаг 3. а := а - b.

Шаг 4. Перейти к шагу 1.

Шаг 5. b := b - а.

Шаг 6. Перейти к шагу 1.

Шаг 7. Стоп.

Результат: а.

Можно ли считать этот алгоритм циклическим? Почему?

Можно ли считать этот алгоритм разветвляющимся? Почему?

Нарисуйте в тетради блок-схему алгоритма Евклида. Найдите в этом алгоритме следование, ветвление и цикл.

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

Программу на алгоритмическом языке можно записать так:

алг Евклид

нач

цел а, b

ввод а, b

нц пока а<>b

если а<b то

b:=b-а

иначе

а:=а-b

все

кц

вывод а

кон

Условие a<>b обозначает «а не равно b», оно записывается с помощью двух знаков, «<» и «>», без пробела между ними¹⁾.

В этой программе вы увидели две новые команды алгоритмического языка, ввод и вывод. Они используются для ввода значений с клавиатуры и вывода результатов на экран, т. е. для диалога²⁾ компьютера с человеком. Такие программы называются диалоговыми.

Диалоговая программа — это программа, которая ведёт диалог с человеком.

Проверьте работу программы Евклид на компьютере.

---

¹⁾ Так сделали потому, что клавиши « ≠ » на клавиатуре нет.

²⁾ Диалог — это общение двух объектов, например компьютера и человека.

Следующая страница Выводы. Интеллект-карта

Cкачать материалы урока