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

Решение линейных сравнений по модулю a*x = b (mod m) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.81
grenada
0 / 0 / 0
Регистрация: 02.01.2014
Сообщений: 2
02.01.2014, 05:26     Решение линейных сравнений по модулю a*x = b (mod m) #1
помогите для курсовой написать программу для решения линейных сравнений по модулю (a*x = b (mod m)) и систем таких сравнений.

http://en.wikipedia.org/wiki/Simulta...ar_congruences

с чего начать?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.01.2014, 05:26     Решение линейных сравнений по модулю a*x = b (mod m)
Посмотрите здесь:

C++ Решение линейных алгоритмов
C++ Решение системы линейных уравнений.
C++ Решение системы линейных уравнений
Решение систем линейных уравнений C++
Решение системы линейных алгебраических уравнений C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
iifat
2179 / 1332 / 96
Регистрация: 05.06.2011
Сообщений: 3,690
02.01.2014, 05:47     Решение линейных сравнений по модулю a*x = b (mod m) #2
Начинать надо с внимательного прочтения приведённой тобой ссылки.
Alexdemath
 Аватар для Alexdemath
125 / 122 / 6
Регистрация: 11.04.2010
Сообщений: 253
02.01.2014, 17:29     Решение линейных сравнений по модулю a*x = b (mod m) #3
Здесь http://www.np.ac.rs/index.php/yu/preuzimanjasve/vol4br2/1005-modification-of-euclidian-algorithm есть псевдокод для решения линейных сравнений. Немного подправить и модулярные системы будет решать.

А начинать нужно с теор.части: разобраться с допустимыми значениями для коэффициентов a_i, b_i и модулей m_i, в какой форме может быть ответ.
NurlashKO
 Аватар для NurlashKO
87 / 87 / 14
Регистрация: 07.10.2012
Сообщений: 145
02.01.2014, 18:30     Решение линейных сравнений по модулю a*x = b (mod m) #4
http://e-maxx.ru/algo/diofant_1_equatio
Alexdemath
02.01.2014, 18:42
  #5

Не по теме:

NurlashKO, сцылку подправь.

NurlashKO
 Аватар для NurlashKO
87 / 87 / 14
Регистрация: 07.10.2012
Сообщений: 145
02.01.2014, 18:48     Решение линейных сравнений по модулю a*x = b (mod m) #6
Цитата Сообщение от Alexdemath Посмотреть сообщение
Не по теме:
NurlashKO, сцылку подправь.
До, простите
http://e-maxx.ru/algo/diofant_1_equation

Вот код если понадобится...
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
#include <cstdio>
#include <iostream>
#include <cmath>
 
using namespace std;
 
int a, b, m, x, y, g;
 
int gcd(int a, int b, int &x, int &y)
{
    if (!a)
    {
        x = 0, y = 1;
        return b;
    }
    int xl, yl;
    int d = gcd(b % a, a, xl, yl);
    x = yl - (b / a) * xl;
    y = xl;
    return d;
}
 
int find_any_solution(int a, int b, int c, int &x, int &y, int &g)
{
    if (a == 0 && b == 0)
    {                   
        x = 0;
        return c == 0;
    }
    g = gcd(abs(a + 0.0), abs(b + 0.0), x, y);
    if (c % g != 0)
        return false;
    x *= c / g;
    y *= c / g;
    if (a < 0)
        x *= -1;
    if (b < 0)
        y *= -1;
    return true;
}
        
int main()
{
    cin >> a >> b >> m;
 
    if (find_any_solution(a, m, b, x, y, g))
        cout << x << endl;
    else
        cout << "No solution" << endl;
}
Alexdemath
 Аватар для Alexdemath
125 / 122 / 6
Регистрация: 11.04.2010
Сообщений: 253
02.01.2014, 19:20     Решение линейных сравнений по модулю a*x = b (mod m) #7
Вроде, получилось и для одиночных линейных сравнения, и для систем таких сравнений

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
#include <iostream>
#include <cmath>
using namespace std;
 
int solveCongruences(int A[], int B[], int M[], int n)
{   
    int x = 0, mod = 1;
 
    for (int i = 0; i < n; i++)
     { int r1 = A[i]*mod, r2 = M[i], x1 = 1, x2 = 0, r = 1;
       while (r != 0)
        { int q = (int)floor((double)r1/r2), t = x1-q*x2;
          x1 = x2; x2 = t; r = r1-q*r2; r1 = r2; r2 = r;
        }
       int b = B[i]-A[i]*x;
       if (b % r1 != 0){ cout << "Не имеет решений"; return 0; }
       x += mod * b * x1/r1;
       mod *= M[i]/r1; 
     }
 
    if (x < 0 || x >= mod) x -= mod * (int)floor((double)x/mod);
 
    cout << "x = " << x << " (mod " << mod << ")";
    return 0;
}
Пример вызова этой функции для решения системы сранений
http://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}2x\equiv 2\quad (\operatorname{mod}\quad 6),\\ 3x\equiv 2\quad (\operatorname{mod}\quad 7),\\2x\equiv 4\quad (\operatorname{mod}\quad 8)\end{cases}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
    setlocale(0,"rus");
 
    int A[] = {2,3,2}, B[] = {2,2,4}, M[] = {6,7,8}, n = 3;
 
    cout << "Решение " << (n==1 ? "сравнения" : "системы сравнений")
         << " по модулю:\n\n";
 
    for (int i = 0; i < n; i++) 
     { cout << "  " << A[i] << "x = " << B[i] << " (mod " << M[i] << ")\n"; }
 
    cout << "\nОтвет: ";
 
    solveCongruences(A, B, M, n);
     
    system("pause > null");
    return 0;
}
grenada
0 / 0 / 0
Регистрация: 02.01.2014
Сообщений: 2
02.01.2014, 20:32  [ТС]     Решение линейных сравнений по модулю a*x = b (mod m) #8
Цитата Сообщение от NurlashKO Посмотреть сообщение
Вот код если понадобится...
почти всё понятно.
сорри, как его использовать для решения систем сравнений?

Цитата Сообщение от Alexdemath Посмотреть сообщение
Вроде, получилось и для одиночных линейных сравнения, и для систем таких сравнений

мало что понимаю
можно прокомментировать последовательность действий?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.01.2014, 21:07     Решение линейных сравнений по модулю a*x = b (mod m)
Еще ссылки по теме:

C++ Решение системы линейных уравнений
C++ Численное решение системы линейных уравнений
Решение линейных уравнений вида ax = b C++

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

Или воспользуйтесь поиском по форуму:
Alexdemath
 Аватар для Alexdemath
125 / 122 / 6
Регистрация: 11.04.2010
Сообщений: 253
02.01.2014, 21:07     Решение линейных сравнений по модулю a*x = b (mod m) #9
Цитата Сообщение от grenada Посмотреть сообщение
можно прокомментировать последовательность действий?
Для начала разберись с мат. частью (хотя бы термины), тогда будет смысл писать комментарии в проге. Ссылка на статью в Википедии у вас есть, ссылку на базовый псевдокод я скинул.

Комменты будут в стиле "класс вычетов для сравнения по мин. возможному модулю" и т.д. и т.п. Так что, пока не выкуришь мат. часть для своего задания, нет смысла их писать.
Yandex
Объявления
02.01.2014, 21:07     Решение линейных сравнений по модулю a*x = b (mod m)
Ответ Создать тему
Опции темы

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