2015-02-27
712
Найти НОД двух целых чисел немного проще используя операцию вычитания. Для этого потребуется следовать такому условию: если A = B, то НОД найден и он равен одному из чисел, иначе необходимо большее из двух чисел заменить разностью его и меньшего. В наиболее понятной форме данный метод описывается блок-схемой (рис. 8.1).
Рисунок 8.1 – Блок-схема алгоритма Евклида. Метод вычитания
Оперируя данной блок-схемой – составляя по ней программный код, вполне целесообразно включить в него оператор цикла с вложенным условным оператором ветвления, имеющим две ветви.
Код программы на C++ (вычитание):
int NOD(int A, int B) //алгоритм Евклида. Вычитание
{
while (A!=B)
if (A>B) A-=B;
else B-=A;
return A;
}
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<>B do
if A>B then A:=A-B
else B:=B-A;
NOD:=A;
end;
begin {основной блок программы}
write('A > '); read(A);
write('B > '); read(B);
write('НОД(', A, ', ', B, ')=', NOD(A, B));
end.
