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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
alexnightfall
0 / 0 / 0
Регистрация: 25.04.2014
Сообщений: 9
#1

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

05.05.2014, 17:48. Просмотров 366. Ответов 0
Метки нет (Все метки)

Помогите решить задачу

Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выведите через пробел НОД(a,b), x и y (какое-нибудь решение). Если решения не существует, то выведите слово Impossible. Входные данные - натуральные числа и не превышают по модулю 10000.


Ввод
1 2 3
Вывод
1 1 1
Ввод
10 6 8
Вывод
2 2 -2
Реализация
C++
1
2
3
4
5
6
7
8
9
10
11
12
 
int gcd (int a, int b, int & x, int & y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    int x1, y1;
    int d = gcd (b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}
Это рекурсивная функция, которая по-прежнему возвращает значение НОД от чисел a и b, но помимо этого — также искомые коэффициенты x и y в виде параметров функции, передающихся по ссылкам.

База рекурсии — случай a = 0. Тогда НОД равен b, и, очевидно, требуемые коэффициенты x и y равны 0 и 1 соответственно.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.05.2014, 17:48     Расширенный алгоритм Евклида
Посмотрите здесь:

Расширенный алгоритм Евклида - C++
Дело движется к реализации RSA, но уже на этом этапе возникли проблемы. Дело в том что у меня большие числа реализованы на массивах (под...

Расширенный алгоритм Евклида - C++
Здравствуйте, форумчане! Подскажите пожалуйста как реализовать такое задание(код самого алгоритма Евклида прилагается): Программа должна...

RSA, Расширенный алгоритм Евклида. Код на С++ - C++
Доброго времени суток ,форумчане) тут такой вопрос: есть Расширенный алгоритм Евклида. ( кто сможет простым языком разъяснить ,как...

Алгоритм Евклида - C++
Привет всем. Задача такова, надо написать программу на С++ для поиска Самого Малого Кратного (СМК) по алгоритму Евклида. Дано три...

Алгоритм Евклида - C++
Здравствуйте! Подскажите пожалуйста какие ошибки есть в алгоритме, который я составил? int gcd (int a, int b) { int t; if...

алгоритм евклида - C++
не могу выкупить ничего что происходит и как решить. вот мое задание : : : : Даны натуральные а и b, не равные 0 одновременно. Найти d =...

Визуализировать алгоритм Евклида - C++
Визуализировать алгоритм эвклида

Необычный алгоритм Евклида - C++
Помогите,пожалуйста!Написал програму,не могу найти ,где в ней ошбка.Условие:дано натуральное число n ичислаа1,а2,а3,...,аn,которые вводятся...

Алгоритм Евклида с использованием рекурсии - C++
Моя реализация алгоритма Евклида с использованием рекурсивной функции. //Program finds greatest common divisor of two natural numbers....

Реализовать обобщенный алгоритм Евклида - C++
Ребят,необходимо реализовать обобщенный алгоритм Евклида. Заранее благодарен! Добавлено через 3 минуты желательно с...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru