Расширенный алгоритм Евклида

@yurets17 · Регистрация: 07.10.2013

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

Здравствуйте, форумчане! Подскажите пожалуйста как реализовать такое задание(код самого алгоритма Евклида прилагается): Программа должна предусматривать ввод исходных данных: двух неотрицательных чисел, модуля и выдачу результата: обратной величины по модулю.

C++

#include <iostream>
#include <cmath>
using namespace std;
 
int ext_gcd(int a, int b, int& x, int& y){
   int q, r, x1, x2, y1, y2,d;
   if (b == 0) {
      d = a, x = 1, y = 0;
      return d;
   }
   x2 = 1, x1 = 0, y2 = 0, y1 = 1;
   while (b > 0) {
      q = a / b, r = a - q * b;
      x = x2 - q * x1, y = y2 - q * y1;
      a = b, b = r;
      x2 = x1, x1 = x, y2 = y1, y1 = y;
   }
   d = a, x = x2, y = y2;
   return fabs(d);
}
 
int main(){
 
        int a, b, x, y;
        char flag='y';
        cout << "Eta programma nahod NOD\n";
        while(flag=='y'||flag == 'Y'){
                cout << "Vvedite dannie\na = ";
                cin >> a;
                cout <<"b = ";
                cin >> b;
                cout << "NOD(" << a << "," << b << ")=" <<ext_gcd(a,b,x,y) << " (rashirenniy algoritm Evklida)"<<endl;
                cout << "Najmite [y] dlya povtora\n";
                cin >> flag;
        }
        return 0;
}

Добавлено через 1 минуту
насколько я понимаю, то мы должны каким-то образом возвращать х и у

@vasiatka · 26.02.2014, 01:15

Реализацию тяжко. А вот пояснить, что делать могу.
b - обратный к a по mod m, если a*b = 1 mod m
(a,m) - НОД чисел

При помощи алгоритма Эвклида можно найти НОД этих чисел.

Если (a,m)=d>1 (числа не взаимно простые), то a не имеет обратной величины по модулю m.

Если (a,m)=d=1, то при помоши расширенного алгоритма эвклида представляем НОД в виде
ax+my=d, где d = 1 (см. строкой выше)
Т.е. будет равенство
ax+my=1 mod m
Не трудно видеть, что my-делится на m, т.е. my=0 mod m
Тогда:
ax=1 mod m, т.е. найденное число x будет обратным элементом.

Теперь Расширенный алгоритм эвклида:
1. Прямой ход (Собственно обычный алгоритм эвклида). Приведу короткий пример, будем считать, что алгоритм закончит работу за 3 шага (справа пример на числах a=5, m=7).

Bash

                                    т.к. a<m меняем их местами
a=m*q1+r1                  7 = 5 * 1 + 2     
m=r1*q2+r2                 5 = 2 * 2 + 1
r1=r2*q3                      2 = 1 * 2
r2 - НОД                       1 - НОД

2. Обратный ход
Начинаем выражать остатки с конца (со второго снизу кравнения) и подставлять в уравнения выше

Bash

r2 = m - r1*q2                             1= 5 - 2*2
r1 = a - m*q1                               2 = 7 -  5* 1
=> r2 = m-(a-m*q1)*q2=            => 1 = 5 - (7-5*1)*2=
= a*(-q2)+m*(1+q1*q2)             =-7 * 1 + 5 * (1+1*2) = -7 +5 * 3

-q2 = a^-1 (обратный) 3 - обратный элемент к 5 по модулю 7: 3*5 = 14 + 1 mod 7 = 1 mod 7

@yurets17 · 26.02.2014, 18:55 **[ТС]**

vasiatka, так будет правильно или нет?

C++

#include <stdio.h>
void extended_euclid(long a, long b, long *x, long *y, long *d)
{
  long q, r, x1, x2, y1, y2;
  if (b == 0) {
    *d = a, *x = 1, *y = 0;
    return;
  }
  x2 = 1, x1 = 0, y2 = 0, y1 = 1;
  while (b > 0) {
    q = a / b, r = a - q * b;
    *x = x2 - q * x1, *y = y2 - q * y1;
    a = b, b = r;
    x2 = x1, x1 = *x, y2 = y1, y1 = *y;
  }
  *d = a, *x = x2, *y = y2;
}
long inverse(long a, long n)
{
  long d, x, y;
  extended_euclid(a, n, &x, &y, &d);
  if (d == 1) return x;
  return 0;
}
int main(void)
{
  long a = 5, n = 7;
  printf("Обратная от %ld по модулю %2ld равняется %ld\n", a, n, inverse(a, n));
  a = 2, n = 12;
  printf("Обратная от %ld по модулю %2ld равняется %ld\n", a, n, inverse(a, n));
  return 0;
}

@vasiatka · 26.02.2014, 21:35

Как я понял сам алгоритм ты взял тут http://www.cyberguru.ru/cpp-so... klida.html.
Только что нашел.
Вроде похоже.
Только если нод отличен от 1 возвращай отрицательное число.
Далее при выводе Если твоя функция вернула отрицательное число, то пиши обратного нет.

@sanekkkk · 20.12.2015, 09:54

yurets17, добрый день.так можно увидеть окончательный вариант?

@nmcf · 20.12.2015, 11:52

C++

struct arr3
{
    int a1, a2, a3;
};
 
// Возвращает набор из трёх чисел - {НОД(a,b), x, y}
// Требуется a,b > 0  и a >= b
arr3 MCD(int a, int b)
{
    arr3 U = {a, 1, 0}, V = {b, 0, 1};
    while (V.a1 != 0)
    {
        int q = U.a1 / V.a1;
        arr3 T = {U.a1 % V.a1, U.a2 - q * V.a2, U.a3 - q * V.a3};
        U = V;
        V = T;
    }
    return U;
}

@sanekkkk · 20.12.2015, 12:51

Я верно понял что это расширенный алгоритм евклида? Новичок в с++..можно с 10по 18строку коменты дать?

Добавлено через 10 минут
Спасибо за решение. Но суть задания в том чтобы алгоритм Поиска нод расписать,а не готовую функцию применить)

@nmcf · 20.12.2015, 13:40

В функции и есть решение. Расписывай.

@sanekkkk · 20.12.2015, 14:14

Можно объяснить с 10-ой по 18-ую строку???

@nmcf · 20.12.2015, 14:50

Ну это и есть алгоритм Евклида.

@sanekkkk · 20.12.2015, 17:45

не работает программа
кучу ошибок дает

@nmcf · 20.12.2015, 17:58

У меня же работает. Значит, не правильно используешь.

@sanekkkk · 20.12.2015, 18:06

/ ev4.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])

struct arr3
{
int a1, a2, a3;
};

// Возвращает набор из трёх чисел - {НОД(a,b), x, y}
// Требуется a,b > 0 и a >= b
arr3 MCD(int a, int b)
{
arr3 U = {a, 1, 0}, V = {b, 0, 1};
while (V.a1 != 0)
{
int q = U.a1 / V.a1 ;
arr3 T = {U.a1 % V.a1, U.a2 - q * V.a2, U.a3 - q * V.a3};
U = V;
V = T;
}
return U;
}

1>c:\users\александр\documents\visual studio 2010\projects\ev4\ev4\ev4.cpp(10): error C2143: синтаксическая ошибка: отсутствие ";" перед "<class-head>"

@Dimension · 20.12.2015, 18:29

херово наверное за 3 года так и не выучить структуру кода

@sanekkkk · 20.12.2015, 19:41

C++

include <iostream>
#include <cmath>
using namespace std;
 
int gcd(int a, int b) {
   int t;
   while (b) {
     t = a % b;
     a = b;
     b = t;        
   }
   return abs(a);
}
 
int ext_gcd(int a, int b, int& x, int& y)
{
   int q, r, x1, x2, y1, y2,d;
   if (b == 0) {
      d = a, x = 1, y = 0;
      return d;
   }
   x2 = 1, x1 = 0, y2 = 0, y1 = 1;
   while (b > 0) {
      q = a / b, r = a - q * b; 
      x = x2 - q * x1, y = y2 - q * y1; 
      a = b, b = r; 
      x2 = x1, x1 = x, y2 = y1, y1 = y;
   }
   d = a, x = x2, y = y2;
   return abs(d);
  
}
 
 
int main(){
    
    int a, b, x, y;
    char flag='y';
    cout << "Eta programma nahod NOD\n";
    while(flag=='y'||flag == 'Y'){
        cout << "Vvedite dannie\na = ";
        cin >> a;
        cout <<"b = ";
        cin >> b;
        cout << "NOD(" << a << "," << b << ")=" <<gcd(a,b) << " (algoritm Evklida)"<<endl;
        cout << "NOD(" << a << "," << b << ")=" <<ext_gcd(a,b,x,y) << " (rashirenniy algoritm Evklida)"<<endl;
        cout << "x = " << x << endl;
        cout << "y = " << y << endl;
        cout << "Obr po mod " << x <<endl;
        cout << "Najmite [y] dlya povtora\n";
        cin >> flag;
    }
    return 0;
}

Зачем здесь 2 условия while???разве нельзя ограничиться случаем когда больше 0?

@nmcf · 20.12.2015, 20:12

C++

struct arr3
{
    int a1, a2, a3;
};
 
arr3 MCD(int a, int b)
{
    arr3 U = {a, 1, 0}, V = {b, 0, 1};
    while (V.a1 != 0)
    {
        int q = U.a1 / V.a1;
        arr3 T = {U.a1 % V.a1, U.a2 - q * V.a2, U.a3 - q * V.a3};
        U = V;
        V = T;
    }
    return U;
}
 
int main()
{
    arr3 a;
    a = MCD(10, 5);
    cout << a.a1 << endl;
}

@vasiatka 65 / 64 / 33 Регистрация: 25.02.2014 Сообщений: 229
	26.02.2014, 21:35	4
	Как я понял сам алгоритм ты взял тут http://www.cyberguru.ru/cpp-so... klida.html. Только что нашел. Вроде похоже. Только если нод отличен от 1 возвращай отрицательное число. Далее при выводе Если твоя функция вернула отрицательное число, то пиши обратного нет. 0

@sanekkkk 1 / 1 / 0 Регистрация: 16.12.2012 Сообщений: 202 Записей в блоге: 3
	20.12.2015, 09:54	5
	yurets17, добрый день.так можно увидеть окончательный вариант? 0

@sanekkkk 1 / 1 / 0 Регистрация: 16.12.2012 Сообщений: 202 Записей в блоге: 3
	20.12.2015, 12:51	7
	Я верно понял что это расширенный алгоритм евклида? Новичок в с++..можно с 10по 18строку коменты дать? Добавлено через 10 минут Спасибо за решение. Но суть задания в том чтобы алгоритм Поиска нод расписать,а не готовую функцию применить) 0

@nmcf 7786 / 6554 / 2983 Регистрация: 14.04.2014 Сообщений: 28,628
	20.12.2015, 13:40	8
	В функции и есть решение. Расписывай. 0

@sanekkkk 1 / 1 / 0 Регистрация: 16.12.2012 Сообщений: 202 Записей в блоге: 3
	20.12.2015, 14:14	9
	Можно объяснить с 10-ой по 18-ую строку??? 0

@nmcf 7786 / 6554 / 2983 Регистрация: 14.04.2014 Сообщений: 28,628
	20.12.2015, 14:50	10
	Ну это и есть алгоритм Евклида. 0

@sanekkkk 1 / 1 / 0 Регистрация: 16.12.2012 Сообщений: 202 Записей в блоге: 3
	20.12.2015, 17:45	11
	не работает программа кучу ошибок дает 0

@nmcf 7786 / 6554 / 2983 Регистрация: 14.04.2014 Сообщений: 28,628
	20.12.2015, 17:58	12
	У меня же работает. Значит, не правильно используешь. 0

@sanekkkk 1 / 1 / 0 Регистрация: 16.12.2012 Сообщений: 202 Записей в блоге: 3
	20.12.2015, 18:06	13
	/ ev4.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" int _tmain(int argc, _TCHAR* argv[]) struct arr3 { int a1, a2, a3; }; // Возвращает набор из трёх чисел - {НОД(a,b), x, y} // Требуется a,b > 0 и a >= b arr3 MCD(int a, int b) { arr3 U = {a, 1, 0}, V = {b, 0, 1}; while (V.a1 != 0) { int q = U.a1 / V.a1 ; arr3 T = {U.a1 % V.a1, U.a2 - q * V.a2, U.a3 - q * V.a3}; U = V; V = T; } return U; } 1>c:\users\александр\documents\visual studio 2010\projects\ev4\ev4\ev4.cpp(10): error C2143: синтаксическая ошибка: отсутствие ";" перед "<class-head>" 0

@Dimension Dimension 594 / 462 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	20.12.2015, 18:29	14
	херово наверное за 3 года так и не выучить структуру кода 0

	20.12.2015, 20:12