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

Расширенный алгоритм Евклида - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Класс дельта http://www.cyberforum.ru/cpp-beginners/thread1105627.html
Создать класс дельта таким образом что бы каждый объект имел свой персональный номер (дескриптор объекта) и функцию которая возвращает его значение Добавлено через 21 час 18 минут #include <iostream> #include <conio.h> using namespace std; class Delta{ protected:
C++ Дано пятизначное натурально число. Если последняя цифра больше первой то их нужно поменять местами Помогите дополнить задачу.Дано пятизначное натурально число. Если последняя цифра больше первой то их нужно поменять местами. #include <stdio.h> #include <conio.h> main() } unsigned long int a,b,n; printf("n="); scanf("%li",&n); if(n>99999,b<10000)printf(Deistvie ne vipolnyaetsa"); else http://www.cyberforum.ru/cpp-beginners/thread1105625.html
C++ Как внести класс в пространство имён
Есть задача, которую решил, там надо было поработать в пространстве имён. В следующей необходимо было это всё переделать под класс, находящийся в пространстве имён. 2 файла сделал, а с пользовательским у меня косяк. cnsp.h #ifndef CNSP_H_ #define CNSP_H_ namespace SALES { class Sales { private: const int QUARTERS=4;
Как с помощью cin ввести нуль терминированную строку? C++
Как с помощью cin ввести "законченную" строчку, имеется в виду символ ноль. таким образов не вводится. какие есть варианты? cin >> ptr1; ptr1 = '\0';
C++ Замена подстроки в строке http://www.cyberforum.ru/cpp-beginners/thread1105582.html
Так как не нашел алгоритм стемминга для C++, то пришлось что-то придумывать самому. Так вот есть такой код int i; for(i = 0; i < ini.getUniSize(); ++i) // getUniSize() - извлекаем размер массива { while(sPos = str.find(ini.getUnions(i),0)) // getUnions(i) - извлекаем элемент массива с индексом i { str.replace(sPos, 0, ""); // заменяем его на пустую строку } }
C++ Выход из лабиринта. Убрать повторяющиеся шаги Доброго времени суток! Прошу помощи Есть программа выход из лабиринта. Там в переменную r записывается текущий шаг. Получается маршрут прописан по самой матрице. Не могу домыслить как убрать повторяющиеся шаги,например программа идет по матрице делает шаг, потом следущим шагом видет, что тупик и ищет другой шаги приэтом получается что к примеру у меня два раза шаг 10 записывается. Мне... подробнее

Показать сообщение отдельно
vasiatka
63 / 62 / 17
Регистрация: 25.02.2014
Сообщений: 229
26.02.2014, 01:15     Расширенный алгоритм Евклида
Реализацию тяжко. А вот пояснить, что делать могу.
b - обратный к a по mod m, если a*b = 1 mod m
(a,m) - НОД чисел

При помощи алгоритма Эвклида можно найти НОД этих чисел.

Если (a,m)=d>1 (числа не взаимно простые), то a не имеет обратной величины по модулю m.

Если (a,m)=d=1, то при помоши расширенного алгоритма эвклида представляем НОД в виде
ax+my=d, где d = 1 (см. строкой выше)
Т.е. будет равенство
ax+my=1 mod m
Не трудно видеть, что my-делится на m, т.е. my=0 mod m
Тогда:
ax=1 mod m, т.е. найденное число x будет обратным элементом.

Теперь Расширенный алгоритм эвклида:
1. Прямой ход (Собственно обычный алгоритм эвклида). Приведу короткий пример, будем считать, что алгоритм закончит работу за 3 шага (справа пример на числах a=5, m=7).
Bash
1
2
3
4
5
                                    т.к. a<m меняем их местами
a=m*q1+r1                  7 = 5 * 1 + 2     
m=r1*q2+r2                 5 = 2 * 2 + 1
r1=r2*q3                      2 = 1 * 2
r2 - НОД                       1 - НОД
2. Обратный ход
Начинаем выражать остатки с конца (со второго снизу кравнения) и подставлять в уравнения выше
Bash
1
2
3
4
r2 = m - r1*q2                             1= 5 - 2*2
r1 = a - m*q1                               2 = 7 -  5* 1
=> r2 = m-(a-m*q1)*q2=            => 1 = 5 - (7-5*1)*2=
= a*(-q2)+m*(1+q1*q2)             =-7 * 1 + 5 * (1+1*2) = -7 +5 * 3
-q2 = a^-1 (обратный) 3 - обратный элемент к 5 по модулю 7: 3*5 = 14 + 1 mod 7 = 1 mod 7
 
Текущее время: 23:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru