Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Геттеры создают объекты https://www.cyberforum.ru/ cpp-beginners/ thread1011443.html
Пытаюсь из класса вытащить поле map class AutoShop { map<int, Manager> mapManagers; map<int, Client> mapClients; map<int, AutoConfiguration> mapAutoConfigurations; template <class T>...
C++ прога для графикы
какая нужна программа для написания графики в С++?
C++ Создать одномерный массив, заполнить его случайными значениями, отсортировать массив по убыванию https://www.cyberforum.ru/ cpp-beginners/ thread1011431.html
создать одномерный массив, заполнить его случайными значениями, отсортировать массив по убыванию. получилось вот что: #include <iostream> #include <stdlib.h> #include <time.h> #include...
C++ Преобразование объектов одного класса в объекты другого Есть сей код.Тут я пытаюсь осуществить преобразование объекта класса myCl к классу myCl2. Код вызывает завершение работы компилятора. В чем может быть проблема ? #include <iostream> using... https://www.cyberforum.ru/ cpp-beginners/ thread1011426.html
C++ Удалить все цифровые символы из строки
Из строки нужно удалить все цифровые символы. Наработки пока такие: char* pIn = pTmp; char* pOut = pTmp; while (*pIn != '\0') { if (isdigit(*pIn)) while (isdigit(*pIn) && *pIn)...
C++ Почему не работает if-else Привет, форумчане! Значицца, так, дано задание (опущу ненужное) задать диапазон массива от 1 до 20. >Если да, то выполнять следующее действие. >Если нет, писать "Error. Write again." "If"... https://www.cyberforum.ru/ cpp-beginners/ thread1011418.html
C++ Прокоминтируйте строки задачи Всем привет, я тут пытаюсь освоить классы, у книге которой я пользуюсь приведен пример, но я его не совсем понимаю, пркоминтируйте все строчки пожалуйста. Ниже код задачи. #include <iostream>... https://www.cyberforum.ru/ cpp-beginners/ thread1011414.html C++ Обработка матриц
помогите решить проблему, не могу понять, как сделать так, чтобы вводить размер матрицы с клавиатуры: вот мой код: #include <iostream.h> #include <stdio.h> #include <math.h> #include...
C++ Составить блок-схему программы https://www.cyberforum.ru/ cpp-beginners/ thread1011411.html
Доброго времени суток. Запутался в циклах. Помогите составить, если не сложно. #include "stdafx.h" #include <iostream> #include <time.h> #include <math.h> using namespace std; int main()...
C++ Массив целых чисел. Рассмотреть отрезки последовательности, состоящие из степеней пятерки https://www.cyberforum.ru/ cpp-beginners/ thread1011405.html
Добрый день, у меня вот есть код на паскале, нужно перевести на с++. Не очень понятно, что там в функции выходит, и какие параметры мы передаем.. Условие: Даны натуральное число n, целые числа...
C++ Прогрмма по поиску кратчайших путей в графе
Всю голову поломал,но вот что-то толком не получается(((Нужна программа по поиску кратчайших путей в графе на основе теории нечетких множеств!
C++ Написать программу, которая считывает текст из файла и выводит на экран все его предложения в обратном порядке. https://www.cyberforum.ru/ cpp-beginners/ thread1011401.html
Написать программу, которая считывает текст из файла и выводит на экран все его предложения в обратном порядке. Умоляю...помогите((((
DmitriiS
0

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

18.11.2013, 22:56. Показов 9656. Ответов 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;
}


Вернуться к обсуждению:
Реализация Китайской теоремы об остатках C++
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.11.2013, 22:56
Готовые ответы и решения:

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

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

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

Найти решение системы сравнений по китайской теореме об остатках
Здравствуйте! Решаю одну задачу, где нужно в кольце целых чисел найти x из системы сравнений по...

1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.11.2013, 22:56

Доказательство гипотезы (теоремы) Эндрю Била в контексте "Полного доказательства великой теоремы Ферма методом деления"
УДК 512.1 Доказательство гипотезы Эндрю Била Ведерников Сергей Иванович –...

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

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

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

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