Бинарный алгоритм вычисления НОД, как понятно из названия, находит наибольший общий делитель, а именно НОД двух целых чисел. В эффективности данный алгоритм превосходит метод Евклида, что связано с использованием сдвигов, то есть операций деления на степень 2-ки, в нашем случае на 2.
Компьютеру проще поделить (умножить) на 2, 4, 8 и т.д., чем на какое-либо другое число. Но в тоже время бинарный алгоритм уступает алгоритму Евклида в простоте реализации. Для дальнейшего усвоения материала следует ознакомиться со свойствами, которыми обладает НОД двух чисел A и B. Потребуются не все свойства, а только три следующих тождества:
НОД(2A, 2B+1) = НОД(A, 2B+1)
НОД(-A, B) = НОД(A, B)
Теперь рассмотрим этапы работы алгоритма. Они основываются на приведенных свойствах наибольшего общего делителя.
- инициализируем переменную k значением 1. Ее задача – подсчитывать «несоразмерность», полученную в результате деления. В то время как A и Bсокращаются вдвое, она будет увеличиваться вдвое;
- пока A и B одновременно не равны нулю, выполняем
- если A и B – четные числа, то делим надвое каждое из них: A←A/2, B←B/2, а k увеличивать вдвое: k←k*2, до тех пор, пока хотя бы одно из чисел A или B не станет нечетным;
- если A – четное, а B – нечетное, то делим A, пока возможно деление без остатка;
- если B – четное, а A – нечетное, то делим B, пока возможно деление без остатка;
- если A≥B, то заменим A разностью A и B, иначе B заменим разностью Bи A.
- после выхода из 2-ого пункта, остается вернуть в качестве результата произведение B и k: НОД(A, B)=B*k.
Код программы на C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include "stdafx.h" #include <iostream> using namespace std; //бинарный алгоритм вычисления НОД int NOD(int A, int B) { int k=1; while ((A!=0) && (B!=0)) { while ((A%2==0) && (B%2==0)) { A/=2; B/=2; k*=2; } while (A%2==0) A/=2; while (B%2==0) B/=2; if (A>=B) A-=B; else B-=A; } return B*k; } //главная функция void main() { setlocale(LC_ALL,"Rus"); int A, B; cout<<"A > "; cin>>A; cout<<"B > "; cin>>B; cout<<"НОД("<<A<<", "<<B<<")="<<NOD(A, B); system("pause>>void"); } |
Код программы на Pascal:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
program BinaryNOD; uses crt; var A, B: integer; {бинарный алгоритм вычисления НОД} function NOD(A, B: integer): integer; var k: integer; begin k:=1; while (A<>0) and (B<>0) do begin while (A mod 2=0) and (B mod 2=0) do begin A:=A div 2; B:=B div 2; k:=k*2; end; while A mod 2=0 do A:=A div 2; while B mod 2=0 do B:=B div 2; if A>=B then A:=A-B else B:=B-A; end; NOD:=B*k; end; {основной блок программы} begin write('A > '); read(A); write('B > '); read(B); write('НОД(', A, ', ', B, '): ', NOD(A, B)); end. |
Похожие записи: