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

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

Восстановить пароль Регистрация
 
vitaliypro
1 / 1 / 0
Регистрация: 09.09.2013
Сообщений: 125
05.10.2013, 00:21     Расширенный алгоритм Евклида #1
Вот программа - - - - - - - - - -

ЗАДАНИЕ: Даны натуральные а и b, не равные 0 одновременно. Найти d = НОД (a,b) и такие целые x и y, что d = a*x + b*y.

КОД ПРОГРАММЫ:
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
#include <iostream>
 
using namespace std;
int x=1,y=0,d;
void euclid(int a, int b)
{
    int t;
    if (!b) // в случае, если b = 0, полагаем, что x = 1, y = 0;
    {
        d = a; x = 1; y = 0;
        return;
    }
    euclid(b, a%b); // рекурсивно вызываем функцию от b и остатка их деления
    t = y;
    y = x - (a/b) * y;
    x = t;
}
 
int main()
{
    int a,b;
    setlocale(LC_ALL,"rus");
    cout<<"Введите числа A и B"<<endl;
    cin>>a>>b;
    euclid(a,b);
    cout<<"НОД = "<<d<<endl;
    cout<<"Коэффициентами Безу будут x = "<<x<<" и y = "<<y<<endl;
    return 0;
}
Необходимо заменить на d = a/x + b*y. (меняется первая операция умножения на деление!)!
по идее a/x + b*y = a*x^(-1)+b*y. но все равно не получается.

помогите плиз.

Добавлено через 1 час 22 минуты
upup

Добавлено через 25 секунд
uuup
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2013, 00:21     Расширенный алгоритм Евклида
Посмотрите здесь:

Необычный алгоритм Евклида C++
C++ Алгоритм Евклида
Алгоритм Евклида + системы счисления C++
RSA, Расширенный алгоритм Евклида. Код на С++ C++
C++ алгоритм евклида
Алгоритм Евклида C++
Расширенный алгоритм Евклида C++
Алгоритм Евклида. Переведите с Паскаля на С++ C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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