Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
DmitriiS
#1

Реализация Китайской теоремы об остатках - C++

18.11.2013, 22:56. Просмотров 1878. Ответов 1
Метки нет (Все метки)

Задача программы - найти X, исходя из трёх сравнений.
Код я написал, но никак не пойму, почему X принимает отрицательное, да и неправильное значение.
Проверьте, пожалуйста, если кому не лень)

C++ (Qt)
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
 
//Функция для вычисления НОД - проверка взаимно простых
unsigned int gcd(unsigned int a, unsigned int b)
{
    while (a && b)
        if (a >= b)
           a = a % b;
        else
           b = b % a;
    return a | b;
}
 
//Функция Эйлера
int euler(int n)
{
    int ans;
    ans = n;
    for (int i = 2; i*i <= n; i++)
        if (n % i == 0)
        {
            while (n % i == 0) n = n/i;
            ans = ans - ans / i;
        }
    if (n > 1) ans = ans - ans / n;
    return ans;
}
 
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    //x = a(mod m)
    int A, i, j, k, c, X;
    setlocale(LC_ALL, "Russian");
 
    //снимем нужные данные с клавиатуры
    cout << "Вы имеете систему уравнений вида:" << endl << "x = a[1] (mod m[1])" << endl << 
        "x = a[2] (mod m[2])" << endl << "..............." << endl << "x = a[k] (mod m[k])" << endl << "где i = 1, 2, ..., k." << endl;
    cout << "Программа создана для того, чтобы реализовывать Китайскую теорему об остатках," << endl << " т.е. находить число X по остаткам от деления на взаимно простые числа." << endl <<
        "Введите сначала число k - количество уравнений системы." << endl;
    cin >> k;
    if (cin.fail())
        do
        {
            cout << "---Error!---" << "Введите число!" << endl;
            cin.clear();
            cin.sync();
            cin >> k;
        }
        while (cin.fail());
 
    int *m = new int[k];
    int *a = new int[k];
    int *N = new int[k];
    int *M = new int[k];
    int *f = new int[k];
    memset(m, 0, sizeof(m));
    memset(a, 0, sizeof(a));
    memset(N, 0, sizeof(N));
    memset(M, 0, sizeof(M));
    memset(f, 0, sizeof(f));
 
    retry : ;//при ошибке возврат сюда
    for (int i=0; i<k; i++)//a[i] и m[i]
    {
        cout << "Введите числа m[" << i + 1 << "] и a[" << i + 1 << "] через пробел соответственно." << endl;
        cin >> m[i];
        if (cin.fail())
            do
            {
                cout << "---Error!---" << "Введите число!" << endl;
                cin.clear();
                cin.sync();
                cin >> m[i];
            }
            while (cin.fail());
 
        cin >> a[i];
        if (a[i] > m[i])
            do
            {
                cout << "a[i] должно быть меньше m[i]" << endl;
                cin.clear();
                cin.sync();
                cin >> a[i];
                if (cin.fail())
                    do
                    {
                        cout << "---Error!---" << "Введите число!" << endl;
                        cin.clear();
                        cin.sync();
                        cin >> a[i];
                    }
                    while (cin.fail());
            }
            while (a[i] > m[i]);
    }
 
    //проверим, взаимно ли просты элементы массива m
    for (int i=0; i < k; i++)
        for (int j=0; j < k; j++)
            if ((i != j) && (gcd(m[i], m[j]) != 1))
            {
                cout << "m[i] должны быть взаимно просты! Возврат к вводу m[i] и a[i]." << endl;
                goto retry;
            }
 
    //приступим, наконец к нахождению X
    A = 1;
    for (int i=0; i < k; i++)
        A = A * m[i];
    for (int i=0; i < k; i++)
        M[i] = A / m[i];
 
    for (int i=0; i < k; i++)
    {
        f[i] = euler(m[i]);
        //N[i] = exp(M[i] * log(f[i] - 1.0));
        c = N[i];
        for (int j=1; j <= f[i] - 1; j++)
            N[i] = N[i] * c;
        N[i] = N[i] % m[i];
    }
 
    //само значение X
    X = 0;
    for (int i=0; i < k; i++)
        X = X + a[i] * N[i] * M[i];
    
    cout << "Решение системы сравнений" << endl;
    for (int i=0; i < k; i++)
        cout << "X = " << a[i] << "(mod" << m[i] << ")" << endl;
    cout << "имеет вид:" << endl << "X = " << X << "(mod" << A << ")" << endl;
 
    delete[] m;
    delete[] a;
    delete[] N;
    delete[] M;
    delete[] f;
    system("pause");
    return 0;
}
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2013, 22:56
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Реализация Китайской теоремы об остатках (C++):

Код Китайской теоремы остатков - C++
Доброго времени суток. Помогите, пожалуйста. В учебнике Б.Штайера &quot;Прикладная криптография&quot; описывается код Китайской теоремы остатков на...

Реализация Теоремы Штурма - C++
Необходимо написать программу для нахождения количества действительных корней многочлена n-й степени (теорема Штурма) Добавлено через...

Китайская теорема об остатках - C++
товарищи есть у кого-то исходный код на Си который реализует данную теорему или может знаете где взять можно?? просто завтра нужно сдать, а...

Проверка теоремы Гольдбаха - C++
Дано четное число n&gt;2; проверить для этого числа гипотезу Гольдбаха. Эта гипотеза (по сегодняшний день не опровергнута и полностью не...

Бинарный поиск с соблюдением теоремы Пифагора - C++
Всем привет. На input подается число (s), которое является суммой чисел a, b, c, которые предстоит найти. Условие следующее: ...

Opencv. Применение дискретной теоремы Грина к изображению - C++
Пытаюсь реализовать алгоритм поиска ядра отпечатка пальца по этой статье. По формуле \begin{bmatrix}J_x(x,y)\\...

1
Belfegor
18.11.2013, 22:59     Реализация Китайской теоремы об остатках
  #2

Не по теме:

увидел метку, понял что goto, пошел дальше

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.11.2013, 22:59
Привет! Вот еще темы с ответами:

Схема разделения секрета на основе китайской теоремы об остатках. Литература - Криптография
Здравствуйте. Подскажите пожалуйста, что почитать попроще на эту тему. Уже наткнулся на статью в Вики и книгу Шнайера. Но там недостаточно...

Теорема об остатках - Pascal ABC
завтра сдать надо((

Китайская теорема об остатках - Математика
когда коэфф взаимно простые, решение понятно но вот , например 2x =1mod(4) 4x=1(mod2) без понятия, что тут будет происходить, и...

Планшеты страны китайской - Планшеты, ebook
Смотрю в сторону китайских планшетов. Очень интересуют эти устройства, но интересуют следующие вопросы: 1)Можно ли где нибудь купить...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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