Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 43, средняя оценка - 4.70
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
26.02.2014, 00:00     Расширенный алгоритм Евклида #1
Здравствуйте, форумчане! Подскажите пожалуйста как реализовать такое задание(код самого алгоритма Евклида прилагается): Программа должна предусматривать ввод исходных данных: двух неотрицательных чисел, модуля и выдачу результата: обратной величины по модулю.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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
63 / 62 / 17
Регистрация: 25.02.2014
Сообщений: 229
26.02.2014, 01:15     Расширенный алгоритм Евклида #2
Реализацию тяжко. А вот пояснить, что делать могу.
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
1
2
3
4
5
                                    т.к. 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
1
2
3
4
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
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
26.02.2014, 18:55  [ТС]     Расширенный алгоритм Евклида #3
vasiatka, так будет правильно или нет?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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
63 / 62 / 17
Регистрация: 25.02.2014
Сообщений: 229
26.02.2014, 21:35     Расширенный алгоритм Евклида #4
Как я понял сам алгоритм ты взял тут http://www.cyberguru.ru/cpp-sources/...m-evklida.html.
Только что нашел.
Вроде похоже.
Только если нод отличен от 1 возвращай отрицательное число.
Далее при выводе Если твоя функция вернула отрицательное число, то пиши обратного нет.
sanekkkk
1 / 1 / 0
Регистрация: 16.12.2012
Сообщений: 60
Записей в блоге: 3
20.12.2015, 09:54     Расширенный алгоритм Евклида #5
yurets17, добрый день.так можно увидеть окончательный вариант?
nmcf
4297 / 3718 / 1251
Регистрация: 14.04.2014
Сообщений: 14,540
20.12.2015, 11:52     Расширенный алгоритм Евклида #6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
1 / 1 / 0
Регистрация: 16.12.2012
Сообщений: 60
Записей в блоге: 3
20.12.2015, 12:51     Расширенный алгоритм Евклида #7
Я верно понял что это расширенный алгоритм евклида? Новичок в с++..можно с 10по 18строку коменты дать?

Добавлено через 10 минут
Спасибо за решение. Но суть задания в том чтобы алгоритм Поиска нод расписать,а не готовую функцию применить)
nmcf
4297 / 3718 / 1251
Регистрация: 14.04.2014
Сообщений: 14,540
20.12.2015, 13:40     Расширенный алгоритм Евклида #8
В функции и есть решение. Расписывай.
sanekkkk
1 / 1 / 0
Регистрация: 16.12.2012
Сообщений: 60
Записей в блоге: 3
20.12.2015, 14:14     Расширенный алгоритм Евклида #9
Можно объяснить с 10-ой по 18-ую строку???
nmcf
4297 / 3718 / 1251
Регистрация: 14.04.2014
Сообщений: 14,540
20.12.2015, 14:50     Расширенный алгоритм Евклида #10
Ну это и есть алгоритм Евклида.
sanekkkk
1 / 1 / 0
Регистрация: 16.12.2012
Сообщений: 60
Записей в блоге: 3
20.12.2015, 17:45     Расширенный алгоритм Евклида #11
не работает программа
кучу ошибок дает
nmcf
4297 / 3718 / 1251
Регистрация: 14.04.2014
Сообщений: 14,540
20.12.2015, 17:58     Расширенный алгоритм Евклида #12
У меня же работает. Значит, не правильно используешь.
sanekkkk
1 / 1 / 0
Регистрация: 16.12.2012
Сообщений: 60
Записей в блоге: 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>"
Dimension
Dimension
547 / 428 / 132
Регистрация: 08.04.2014
Сообщений: 1,693
Завершенные тесты: 1
20.12.2015, 18:29     Расширенный алгоритм Евклида #14
херово наверное за 3 года так и не выучить структуру кода
sanekkkk
1 / 1 / 0
Регистрация: 16.12.2012
Сообщений: 60
Записей в блоге: 3
20.12.2015, 19:41     Расширенный алгоритм Евклида #15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2015, 20:12     Расширенный алгоритм Евклида
Еще ссылки по теме:

C++ алгоритм евклида
Алгоритм Евклида C++
Алгоритм Евклида. Переведите с Паскаля на С++ C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
nmcf
4297 / 3718 / 1251
Регистрация: 14.04.2014
Сообщений: 14,540
20.12.2015, 20:12     Расширенный алгоритм Евклида #16
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
}
Yandex
Объявления
20.12.2015, 20:12     Расширенный алгоритм Евклида
Ответ Создать тему
Опции темы

Текущее время: 11:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru