Алгоритмы

Полную Развилку. 
Рис.36. Алгоритм Остаток 
 
Пример 2. Записать алгоритм Евклида нахождения наибольшего общего 
делителя (НОД) двух натуральных чисел а, b в виде блок-схемы, используя алгоритм 
«Остаток» как вспомогательный. 
Из математики известно, что алгоритм Евклида для двух натуральных чисел а, b 
основан на двух утверждениях: 
1) Если число а нацело делится на b, то НОД(а, b) = b; 
2) Если а не делится нацело на b, причем а > b, то НОД(а, b) = НОД(b, r), где r – 
остаток от деления а на b. 
Блок-схема алгоритма Евклида приведена ниже на Рис.37, алгоритм «НОД(a,b,d),
является рекурсивным, так как он обращается сам к себе, именно по этой причине он 
получил заголовок. 
Да 
начало 
«Остаток(a,b, r)»
a>b 
r:=a-b 
конец 
r:=b-a 
Нет 
Да 
a:=r 
b:=r 
r
r
Да 
Нет 
Нет 

---

Алгоритмы 
Т. Н. Горностаева 
http://izd-mn.com/
45 
Алгоритм является структурой Следование,  состоящей из двух блоков: 
 1 блок - вспомогательный алгоритм «Остаток»; 
 2 блок – структура Полная Развилка с условием r = 0; на ее обеих ветвях 
находятся структуры Полная Развилка с одним и тем же условием a > b. В левой 
Развилке алгоритм «НОД» обращается сам к себе, но уже с новыми значениями 
параметров. 

Рис.37. Блок-схема вычисления НОД 
Из приведенных примеров следует вывод, что рекурсия сводит общую задачу 
к более простой задаче того же класса. 
 
Контрольные задания и вопросы к теме 
 
1. Какой алгоритм называется рекурсивным? 
2. Используя блок-схему Рис.37, вычислить НОД (24,6). Какое количество 
команд пришлось использовать в этом алгоритме? 
3. Используя блок-схему Рис.37, вычислить НОД (21,6). Какое количество 
команд пришлось использовать в этом алгоритме? 

---