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

решение уравнения - C++

Восстановить пароль Регистрация
 
solomid
1 / 1 / 0
Регистрация: 22.09.2011
Сообщений: 86
12.10.2011, 16:38     решение уравнения #1
доброго времени суток
Даны целые положительные числа a и b. Необходимо найти целые (не обязательно положительные) числа x и y, такие, что
ax+by = НОД(a,b).
Например: a=93, b=53; НОД(93,53)=1 ;93*4 + 53*(-7) = 1
НОД находит без проблем, а вот как реализовать подбор x и 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
#include "stdafx.h"
#include <iostream>
#include <stdio.h>
using namespace std;
 
int NOD(int a, int b)
{
    int c;
    while(b)
    {
        c = a%b;
        a=b;
        b=c;
    }
    return a;
}
int DIF(int x,int y)
{
//здесь что-то классное:)
}
int main(void)
{
    int a,b;
    cin >> a;
    cin >> b;
    cout << NOD(a,b) << DIF(x,y) << endl;
    return 0;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.10.2011, 16:38     решение уравнения
Посмотрите здесь:

C++ Решение уравнения
Решение численного уравнения C++
Решение уравнения C++
Решение уравнения C++
Решение куб. уравнения. C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Yurii_74
paladin
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
12.10.2011, 16:47     решение уравнения #2
Можно в лоб попробовать. x = 1, y = -1. sum = x*A + y*B. Затем, исходя из получившейся суммы, увеличивать x или уменьшать y, Повторять до получения требуемого результата (+НОД(A, B) или -НОД(A, B)).
aeshes
 Аватар для aeshes
437 / 200 / 13
Регистрация: 07.10.2011
Сообщений: 462
12.10.2011, 16:57     решение уравнения #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
вам нужен расширенный алгоритм Евклида
Yurii_74
paladin
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
12.10.2011, 17:04     решение уравнения #4
31242939 
1-1-117-3
2-11955
2-2-234-6
3-2782
3-3-351-9
4-3-39-1
5-32737
5-4-156-4
6-41564
6-5-273-7
7-5391
Это так, небольшой пример-подсказка.
Yandex
Объявления
12.10.2011, 17:04     решение уравнения
Ответ Создать тему
Опции темы

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