2015-02-27
1500
Второй способ отличается от первого тем, что в основной части программы операция вычитания заменяется на операцию деления, а точнее на взятие остатка от деления большого числа на меньшее. Этот способ предпочтительнее предыдущего, так как он в большинстве случаев эффективнее и требует меньше времени.
За исключением условия выхода из цикла и операций в выражениях, блок-схема метода деления описывается аналогично методу вычитания (рис. 8.2).
Рисунок 8.2 – Блок-схема алгоритма Евклида. Метод деления
Достаточно то условие, при котором тело цикла будет выполняться до тех пор, пока обе переменных имеют значения отличные от нуля, поскольку, когда условие перестанет быть истинным, то из этого последует, что одно из теперешних значений является искомым наибольшим общим делителем. Да и потом, никак нельзя допустить следующей итерации, в которой будет предпринята попытка деления на нуль.
На конкретных примерах продемонстрируем работу каждого из видов реализации алгоритма. Начнем с того, в основе которого лежит операция взятия остатка от деления. Имеем два числа: 112 и 32. Первое больше второго – заменим его остатком от деления 112 на 32. Новая пара чисел включает 16 и 32. Второе больше, поэтому также заменим его остатком от деления 32 на 16, т. е. нулем. В результате получаем НОД=16:
| Начальные данные | ||
| Шаг 1 | ||
| Шаг 2 |
А теперь составим с теми же числами таблицу для алгоритма вычитанием:
| Начальные данные | ||
| Шаг 1 | ||
| Шаг 2 | ||
| Шаг 3 | ||
| Шаг 4 |
Приведенный пример продемонстрировал, как в частном случае, предпочтя деление (взятие остатка от деления) вычитанию, можно выиграть в быстродействии. Преимущество деления становится видно наиболее отчетливо после следующих рассуждений. Предположим, что A меньше B, а так как НОД двух целых чисел меньше или равен наименьшему из них, то и тут он меньше или равен A; поэтому оптимальным будет уже при первой операции заменить B числом меньшим или равным A. Далее, известно, что в одном случае большее число заменяется разностью его и меньшего числа, а в другом остатком от деления. При делении B на A (большее на меньшее), остаток не может превышать число, стоящее в знаменателе (т. е. A), следовательно, взятие остатка от деления гарантирует оптимальный исход. Но то же самое нельзя сказать в отношении операции вычитания, поскольку совсем необязательно, что сразу после выполнения первого вычитания, B станет меньше или равно A. К примеру, пусть A будет равняться 150, а B – 1100. Так, используя вычитание, мы в первом действии получим B равное 950, в то время как метод деления даст 50.
Код программы на C++ (деление):
int NOD(int A, int B) //алгоритм Евклида. Деление
{
while (A!=0 && B!=0)
if (A>B) A%=B;
else B%=A;
return A+B;
}
void main () //главная функция
{
int A, B;
cout<<"A > "; cin>>A;
cout<<"B > "; cin>>B;
cout<<"НОД("<<A<<", "<<B<<")="<<NOD(A, B);
}
Код программы на Pascal (деление):
var A, B: integer;
function NOD(a, B: integer): integer; {алгоритм Евклида. Деление}
begin
while (A<>0) and (B<>0) do
if A>B then A:=A mod B
else B:=B mod A;
NOD:=A+B
end;
begin {основной блок программы}
write('A > '); read(A);
write('B > '); read(B);
write('НОД(', A, ', ', B, ')=', NOD(A, B));
end.
