Математика: Теория чисел.

Вычисление НОД и НОК.

• Алгоритм Евклида.
  
• Бинарный алгоритм Евклида.
  
• Алгоритм решения уравнения ax+by = 1
  
• Расширенный бинарный алгоритм Евклида:
  
  Даны x, y. Находит a, b, v: ax+by = v, где v - НОД(x, y). Также используется для нахождения обратного элемента по модулю( в Z_m).
• НОК.
  

Алгоритм Евклида.

1. Вычислим r - остаток от деления числа a на b, a = bq+r, 0 <= r < b.

2. Если r = 0, то b есть искомое число.

3. Если r =/= 0, то заменим пару чисел (a,b) парой (b,r)
и перейдем к шагу 1.

int NOD(int a,int b)
 {
    while(a!=0 && b!=0)
    {
       if(a>=b) a=a%b;
           else b=b%a;
    }
 return x+y; // Одно - ноль
 }
 

При вычислении наибольшего общего делителя (a,b) с помощью алгоритма Евклида будет выполнено не более 5p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b.

Бинарный алгоритм Евклида.

Этот алгоритм использует соотношения для НОД:

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

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

  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}  
  

Алгоритм решения уравнения ax+by = 1.

1.Определим матрицу E:

E =	( 1 0 ) ( 0 1 )

2. Вычислим r - остаток от деления числа a на b, a=bq+r, 0 <= r < b.

3. Если r=0, то второй столбец матрицы E даёт вектор ( x, y ) решений уравнения.

4. Если r =/= 0, то заменим матрицу E матрицей

E *	( 0  1 ) ( 1 -q )

5. Заменим пару чисел (a,b) на (b,r) и перейдем к шагу 1.

1. g := 1; 
2. While x И y ЧЕТНЫЕ 
    {
	 x := x/2; 
	 y := y/2; 
	 g := 2g;
	}
3. u := x; v := y; A := 1; B := 0; C := 0; D := 1;
4. While u ЧЕТНОЕ {
   4.1 u := u/2;
   4.2 If A == B == 0(mod 2) then A := A/2; B := B/2; 
           else A := (A+y)/2; B := (B-x)/2; 
	}
5. While v ЧЕТНОЕ {
   5.1 v := v/2; 
   5.2 If C == D == 0(mod 2) then C := C/2; D := D/2; 
           else C := (C+y)/2; D := (D-x)/2; 
	}
6. If u >= v then u := u-v; A := A-C; B := B-D; 
       else v := v-u; C := C-A; D := D-B; 
7. If u = 0 then a := C; b := D;  return (a, b, g*v); 
       else goto 4.

НОК.

НОК( a , b) = a*b / НОД(a, b)

Все вышеприведенные алгоритмы имеют сложность O( logn ).

Вверх по странице, к оглавлению и навигации.