Что такое алгоритм: различия между версиями
Содержимое удалено Содержимое добавлено
ЕссБот (обсуждение | вклад) м →Литература: простановка шаблона "по алфавиту" по запросу на Форуме с помощью AWB |
орфография, уточнение |
||
Строка 143:
Описание алгоритма:
#Если <math>a=b</math>, то НОД (наименьший общий делитель) <math>=a=b</math> и заканчиваем вычисления.
#Если <math>a>b</math>, то из <math>a</math> вычитаем <math>b</math> (<math>a \gets a-b</math>). Переходим к 1.
#Если же <math>b>a</math>, то из <math>b</math> вычитаем <math>a</math> (<math>b \gets b-a</math>). Переходим к 1.
Строка 168:
Инструкция <code>return a</code> означает «вернуть как результат вычислений объект <code>a</code>».
Покажем, что наш алгоритм
Действительно, НОД<math>(a,\;b)=\;</math>НОД<math>(a-b,\;b)</math> при <math>a>b</math>, поэтому, несмотря на то, что на каждом шаге меняется одно из чисел, значение НОД<math>(a,\;b)</math> остаётся неизменным. Максимальное из чисел <math>a</math> и <math>b</math> с каждым шагом уменьшается, и в какой-то момент они становятся равны друг другу и равны искомому значениюенпнпасв
| |||