Форум программистов, компьютерный форум, киберфорум
Алгебра, теория чисел
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/18: Рейтинг темы: голосов - 18, средняя оценка - 4.67
4 / 4 / 0
Регистрация: 05.10.2013
Сообщений: 123
1

Алгоритм Эвклида

23.10.2013, 19:45. Показов 3712. Ответов 1

Как оценить сложность алгоритма Эвклида для поиска наибольшего общего делителя?
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.10.2013, 19:45
Ответы с готовыми решениями:

Вычислить выражение в поле, используя алгоритм Эвклида
найти 20 (в степени -1) в поле Z/ mod 73 используя алгоритм Эвклида

Пользуясь алгоритмом Эвклида подобрать Полиномы M1 (x) и M2 (x)
Пользуясь алгоритмом Эвклида подобрать Полиномы M1(x) и M2(x) так чтобы f1(x) M2(x)+f2(x)M1(x) =...

Алгоритм Эвклида
Такой вопрос. Мне нужно написать программу , которая находит НОД(наибольший общий делитель) для 3-х...

Алгоритм Эвклида
показать, что для произвольных целых чисел а и б, уравнение ах+бу=НОД(а,б) разрешимо в целых числах

1
Эксперт по математике/физике
4156 / 2059 / 424
Регистрация: 19.07.2009
Сообщений: 3,117
Записей в блоге: 24
23.10.2013, 23:41 2
Гугл нам даёт следующие две ссылки на первой странице:
http://mitrof3.narod.ru/crypto... .3.3.3.rtf
http://it.kgsu.ru/TI_7/salg_009.html

Читая, можно следующее выделить:
Оценим сверху количество рекурсивных вызовов функции GCD. Для этого выпишем последовательно соотношения, определяющие аргумент X. Предположим для определенности, что n > m (при обратном неравенстве первый вызов функции просто меняет аргументы местами, а при равенстве n = m процесс завершается за один шаг). В качестве параметра V сложности исходных данных целесообразно принять меньший из аргументов функции, т.е. V = m, так как именно с него начинаются операции деления (нахождения модулей) - если увеличить m на произвольно большое число, кратное m (например, m*101000), то это не изменит количества шагов. Следовательно, max(n,m) не является хорошим аргументом функции сложности.
Вывод средней оценки сложности алгоритма Евклида приведен в книге Д. Кнута (Т. 2, разд. 4.5.3). Однако, когда оценка худшего случая всего лишь логарифмическая, средняя оценка представляет, в основном, теоретический интерес (в данном случае она тоже логарифмическая, но с меньшим коэффициентом).
Оценка сводится к ряду Фибоначчи, её ассимптотика также приводится.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.10.2013, 23:41

алгоритм эвклида
как работает этот код? int gcd(int a, int b) { while(b) b^=a^=b^=a%=b; return a; }

Задание на алгоритм Эвклида
Заданы целочисельные массивы А(n), B(n).Построить массив С(n), каждый элемент которого является...

Алгоритм Эвклида. 10 пар чисел
Как сгенерировать 10 пар чисел, в промежутках от 0 до 100, чтобы потом применить алгоритм Эвклида к...

Алгоритм Эвклида (в чем ошибка)
вот программа Program prost_chisla; uses crt; const m=5000; var A:array of integer; ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru