Найти натуральные

@shomaav · Регистрация: 20.01.2010

Author24 — интернет-сервис помощи студентам

Найти натуральные числа x и y, для которых ax+by=НОД(а, b). Использовать алгоритм Евклида и свойства:
НОД(2a, 2b) = 2*НОД(a, b) ;
НОД(2a, b) = НОД(a, b) при b – нечетном. Построить график по найденным x и y.

@Twic · 21.01.2010, 22:21

для начала ! инфо
Бинарный алгоритм Евклида
Этот алгоритм использует соотношения для НОД:

НОД(2*a, 2*b) = 2*НОД(a,b)
НОД(2*a, b) = НОД(a,b) при нечетном b,

Он иллюстрируется следующей программой:

Pascal

m:= a; n:=b; d:=1;
  {НОД(a,b) = d * НОД(m,n)}
  while not ((m=0) or (n=0)) do begin
    if (m mod 2 = 0) and (n mod 2 = 0) then begin
      d:= d*2; m:= m div 2; n:= n div 2;
    end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
      m:= m div 2;
    end else if (m mod 2 = 1) and (n mod 2 = 0) then begin
      n:= n div 2;
    end else if (m mod 2=1) and (n mod 2=1) and (m>=n)then begin
      m:= m-n;
    end else if (m mod 2=1) and (n mod 2=1) and (m<=n)then begin
      n:= n-m;
    end;
  end;
  {m=0 => ответ=d*n; n=0 =>  ответ=d*m}

Более похоже :

Delphi

program Nod;
 
{$APPTYPE CONSOLE}
 
uses
SysUtils, Math;
 
function Z_GCD(a, b: Integer): Integer;
var
c: Integer;
begin
while b <> 0 do
begin
c := a mod b;
a := b;
b := c;
end;
Result := a;
end;
 
// Из книги Роберта Седжвика
// Рекурсивная реализация
function GCD(a, b: Integer): Integer;
begin
if b = 0 then
Result := a
else
Result := GCD(b, a mod b);
end;
 
begin
WriteLn(GCD(18, 45));
readln;
end.

@shomaav 0 / 0 / 0 Регистрация: 20.01.2010 Сообщений: 23
		1
	Найти натуральные 21.01.2010, 21:23. Показов 1160. Ответов 1 Метки нет (Все метки) Найти натуральные числа x и y, для которых ax+by=НОД(а, b). Использовать алгоритм Евклида и свойства: НОД(2a, 2b) = 2*НОД(a, b) ; НОД(2a, b) = НОД(a, b) при b – нечетном. Построить график по найденным x и y. 0

	21.01.2010, 22:21

Найти натуральные

Решение