Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
Другие темы раздела
Алгоритмы Составить алгоритм для последовательности чисел(не массив) http://www.cyberforum.ru/algorithms/thread170509.html
в последовательности целых чисел, завершающихся нулём, найти количество и сумму тех членов, которые делятся нацело на 5 и не делятся на 7 с помощью оператора while натолкните на идею...не знаю...
Алгоритмы Подскажите какую-нибудь книгу по алгоритмам и структурам данных, но чтобы алгоритмы были на С++
Подскажите какую-нибудь книгу по алгоритмам и структурам данных, но чтобы алгоритмы были на С++
Алгоритмы Алгоритм определения длин осей у элипса
Вообщем ситуация такая. Есть дырки от пуль примерно http://www.istockphoto.com/file_thumbview_approve/7594046/2/istockphoto_7594046-bullet-holes.jpg но это так, просто чтобы показать...
Алгоритмы основы алгоритмизации Помогите решить, пожалуйста!!!!!! http://saveimg.ru/show-image.php?id=c7b96701a98239c9a4f4fa0ef4550f13 http://saveimg.ru/show-image.php?id=0505c0e410d865526c6f04df920cebe1 Учиться только начал,... http://www.cyberforum.ru/algorithms/thread169849.html
Алгоритмы нормальные алгоритмы Маркова и рекурсивные функции http://www.cyberforum.ru/algorithms/thread169765.html
Пршу помощи.Задание: 1.Построить нормальный алгоритм Маркова,вычисляющий f=3x+1 ,предвариельно выбрав удобную систему счисления.(схема нормального алгоритма) 2.Построить словесный алгоритм для...
Алгоритмы составить блок схему к графику
необходимо составить блок-схему для графика,или написать на алгоритмическом языке
0-1 алгоритм Алгоритмы
Над рядочком 01 делаем следующее операции: * Копируем в конец рядочка самого себя (получаем 0101) * В второй половине рядка все 0 меняем на 1, а все 1 на 0 (получаем 0110) Над рядочком...
Алгоритмы Кол-во чисел в массиве Вот задача: Найдите количество чисел в массиве, совпадающих с заданным числом. Если можно с подробностями, как будет работать ваша прога с этой задачей. Решил бы сам, да после каникул я даже... http://www.cyberforum.ru/algorithms/thread168761.html
Алгоритмы Расчет угла поворота http://www.cyberforum.ru/algorithms/thread168384.html
Здравствуйте. Требуется найти угол поворота моста(Мостом на картинке обозначена линия).Мост может двигаться по часовой стрелке на 190 градусов и против часовой на 190 градусов.С обоих сторон моста...
Алгоритмы Какой способ лучше для решения данной системы дифуров? Привет!) У меня проблемка, не могу решить системы дифуров численно. Система: dx/dt=a1*x-b1*x*y dy/dt=-a2*x+b2*x*y где a1,a2,b1,b2 произвольные константы (пусть они равны еденице), начальные... http://www.cyberforum.ru/algorithms/thread168280.html
Mr.X
Эксперт С++
3193 / 1720 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
01.10.2010, 09:36 0

Алгоритм преобразования числа в модульное

01.10.2010, 09:36. Просмотров 1263. Ответов 4
Метки (Все метки)

Ответ

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
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
146
147
148
149
150
151
///////////////////////////////////////////////////////////////////////////////////////////
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
///////////////////////////////////////////////////////////////////////////////////////////
typedef int                 T_int;
typedef std::vector<T_int>  T_nums;
///////////////////////////////////////////////////////////////////////////////////////////
T_int  get_product(T_nums  nums)
{
    return std::accumulate(nums.begin(), nums.end(), 1, std::multiplies<T_int>());
}
///////////////////////////////////////////////////////////////////////////////////////////
T_int  inverse_from_mod(T_int  num,  T_int  mod)
{
    for(int i = 1; i < mod; ++i)
    {
        if(i * num % mod == 1)
        {
            return i;
        }
    }
}
///////////////////////////////////////////////////////////////////////////////////////////
T_int  get_x_from_modular_representation
    (
        T_nums  modular_representation,     
        T_nums  basic_nums
    )
{
    T_int  m = get_product(basic_nums);
    T_int  x = 0;
    T_nums  y_nums(basic_nums.size());
    T_nums  s_nums(basic_nums.size());
    T_nums  c_nums(basic_nums.size());
    for(size_t  i = 0; i < basic_nums.size(); ++i)
    {
        y_nums[i] = m / basic_nums[i];
        s_nums[i] = inverse_from_mod(y_nums[i], basic_nums[i]);
        c_nums[i] = modular_representation[i] * s_nums[i] % basic_nums[i];        
        x += c_nums[i] * y_nums[i];
    }
    return x % m;
}
///////////////////////////////////////////////////////////////////////////////////////////
std::ostream& operator<<(std::ostream&  os, const T_nums&  nums)
{
    for(size_t  i = 0; i < nums.size(); ++i)
    {
        std::cout << nums[i]
                  << ' ';
    }    
    return os;
}
///////////////////////////////////////////////////////////////////////////////////////////
T_nums  get_modular_representation(T_int  x, T_nums  basic_nums)
{
    T_nums  res;
    for(size_t  i = 0; i < basic_nums.size(); ++i)
    {
        res.push_back(x % basic_nums[i]);
    }
    return  res;
}
///////////////////////////////////////////////////////////////////////////////////////////
T_int  greatest_common_divisor(T_int  num_A, T_int  num_B)
{
    return num_B == 0 ? num_A : greatest_common_divisor(num_B, num_A % num_B);
}
///////////////////////////////////////////////////////////////////////////////////////////
bool  is_mutually_simple(T_int  basic_num, T_nums  basic_nums)
{
    for(size_t  i = 0; i < basic_nums.size(); ++i)
    {
        if(greatest_common_divisor(basic_num, basic_nums[i]) > 1)
        {
            return false;
        }
    }
    return true;
}
///////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int  n;
    do
    {
        std::cout << "Введите количество взаимно простых базисных чисел >= 1: ";    
        std::cin >> n;    
    }while(n < 1);
    T_nums  basic_nums;
    std::cout << "Введите "
              << n
              << " взаимно простых базисных чисел чисел:"
              << std::endl;
 
    int  basic_num;
    int i = 1;
    do
    {
        std::cout << "Введите "
                  << i 
                  << "-e базисное число: ";
        std::cin >> basic_num;
        if(is_mutually_simple(basic_num, basic_nums))
        {
            basic_nums.push_back(basic_num);
            ++i;
        }       
    }while(basic_nums.size() < n);
 
    int m = get_product(basic_nums);
 
    for(;;)
    {
        int x;
        do
        {
            std::cout << std::endl
                      << std::endl
                      << "Введите число 0 <= x < "
                      << m
                      << ": "
                      << std::endl
                      << "x = ";
 
            std::cin >> x;
        }while(x < 0 || m <= x);
        T_nums  modular_representation = get_modular_representation(x, basic_nums);
        std::cout << "Модульное представление числа "
                  << x 
                  << " для базисных чисел "
                  << std::endl
                  << basic_nums
                  << std::endl
                  << "имеет вид: "
                  << std::endl
                  << modular_representation                 
                  << std::endl
                  << "Число, восстановленное из этого "
                  << "модульно представления, равно "
                  << std::endl
                  << "x = "
                  << get_x_from_modular_representation
                         (modular_representation, basic_nums)                  
                  << std::endl
                  << std::endl;    
    }   
}


Вернуться к обсуждению:
Алгоритм преобразования числа в модульное
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.10.2010, 09:36
Готовые ответы и решения:

Алгоритм преобразования десятичного числа в вещественное
Здравствуйте помогите пожалуйста разобрать алгоритм, понимаю что в вещественном числе 32 разряда...

Составьте алгоритм нахождения значения числа m после преобразования
Натуральное трехзначное число m преобразовано следующим образом: последнюю цифру возвели в квадрат...

Составьте алгоритм нахождения значения числа m после преобразования
Натуральное трехзначное число m преобразовано следующим образом: последнюю цифру возвели в квадрат...

Выполнить программирование: модульное, без модульное
Буду премного благодарен если поможете с этими задачами.

Алгоритм преобразования строки
Добрый день! Прилагаю асм-функцию, которая работает со строкой, содержащей e-mail или его часть и...

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