Форум программистов [Powered by Invision Power Board]

Цитата

Алгоритм Эвклида пытался понять, но не получается, помогите пожалуйста разобраться.

Код


Если три целых числа n, m, k связаны соотношением
N=M*K,
то m,k – делители n, а n – кратное m и k.
Теорема о делении с остатком: Для любых целых чисел a и b существуют единственные числа q и r, такие, что a=bq+r,   0 r<|b|, q – неполное частное, r – остаток.
Лемма 1: Если в равенстве m1+m2+…+mn=n1+n2+…+nn все слагаемые – целые числа и все, кроме последнего, делятся на целое k, то и отмеченное слагаемое должно делиться на k.

Общий делитель чисел m1,m2,…mt – это такое число Д, на которое делятся все перечисленные числа. НОД – наибольшее из них.

Алгоритм Евклида
НОД чисел a и b совпадает с последним отличным от нуля остатком в следующей цепочке равенств:

a = bq+r
b = rq1+r1
r = r1q2+r2
….
rk-1=rkqk+1+rk+1   НОД
rk=rk+1qk+2

1) Любой общий делитель a и b является делителем rk+1
В самом деле, согласно лемме 1, r делится на Д. Тогда r1 делится на Д. И т.д.

2) rk+1 является общим делителем a и b. 
В самом деле, из последних двух соотношений видно, что rk-1 делится на rk+1
3) rk+1 – натуральное число, которое делится на все общие делители a     и b. Значит, это и есть НОД a и b.
Эта цепочка всегда оборвётся, т.к. 0 ri<ri-1

Код


int Euclid()
{
GetDlgItemTextA(FindWindow(0,"TEST"), IDC_EDIT1, A , 20);
GetDlgItemTextA(FindWindow(0,"TEST"), IDC_EDIT6, B , 20);
int a=atoi(A);
int b=atoi(B);
int r=1;
while (r!=0)
{
r=a%b;
a=b;

 if(r!=0)b=r;
}
itoa (b, NOD, 10);
SetDlgItemTextA(FindWindow(0,"TEST"), IDC_EDIT12, NOD);
 return 0;
}

Код


Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. 
Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит 
множество пар (d,y), каждая из которых является решением уравнения в целых числах.

Цитата

но меня интересует именно расширеный алгоритм :

Цитата

Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1.
Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит
множество пар (d,y), каждая из которых является решением уравнения в целых числах.

Код


//---------------------------------------------------------------------------
int NOD_a_b(int a, int b, int& t, int& k)
{
   int  m;       // целочисленный коэффициент при делении
   int  r;       // остаток при делении
   int  k0, t0;  // текущие коэффициенты при подъеме (на выходе ответ)
   int  NOD;

   m = - a / b;  // с минусом
   r = a % b;
   if (r)
   {
      NOD = NOD_a_b(b, r, t, k);     // рекурсивный вызов
      t0 = k;
      k0 = t + k * m;
      t = t0;
      k = k0;
   }
   else
   {
      NOD = b;
      t = 0;
      k = 1;
   }
   return NOD;
}
//--------------------------------------------------------------------