2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 НОД
Сообщение13.02.2008, 10:18 
Аватара пользователя
Всем привет)
Все мы прекрасно знаем алгоритм Евклида для нахождения НОД`а.
Вот такой вопрос: как вывести формулу при кот-ой алгоритм работает максимально долго?
Или по-другому: как вывести формулу нахождения числа m, такого,что при заданном n, происходит наибольшее кол-во шагов для вывода НОД`a?
Первое что пришло мне в голову, написать прогу кот-ая меняет n и m, и выводит кол-во итераций при очередном m и n, а потом попытаться найти зависимость, мне это не помогло, могу выложить код программы, или результаты вычислений.
Всем заранее спасибо)

 
 
 
 Re: НОД
Сообщение13.02.2008, 10:22 
Аватара пользователя
По-моему, формулу вывести нельзя :?

 
 
 
 
Сообщение13.02.2008, 10:31 
Аватара пользователя
А вообще есть какие-нибудь идеи по этому поводу, незнаю, можно ли скажем математически доказать невозможность вывода этой формулы?..

 
 
 
 
Сообщение13.02.2008, 10:34 
Аватара пользователя
Вва вопрос давно исследован и на него получен точный ответ. См., например, http://rain.ifmo.ru/cat/view.php/theory/math/number-theory-2005

 
 
 
 
Сообщение13.02.2008, 10:40 
Аватара пользователя
Спасибо большое, я конечно понимаю, что там наверное дан ответ на мой вопрос, но ввиду своей не состоятельности в математике, можно меня как полного чайника носом ткнуть в ответ, плз)

 
 
 
 
Сообщение13.02.2008, 10:52 
Аватара пользователя
Цитирую: "Время работы алгоритма Евклида

Обозначим e(m, n) число шагов алгоритма Евклида, примененного к натуральным числам n и m. До сих пор наиболее известным результатом о функции e(m, n) остается найденная французским математиком Габриэлем Ламе (Gabriel Lamé, 1795–1870) в первой половине 19-го века (1844) оценка сверху:
e(m, n) ≤ [logφ51⁄2(max(m, n) + 1⁄2)] − 1, где φ = (1 + 51⁄2) ⁄ 2

Данная оценка является точной и достигается при соседних числах Фибоначчи: m = Fk+1, n = Fk.

Доказательство и различные интерпретации алгоритма Евклида см. [5] "

 
 
 
 
Сообщение13.02.2008, 10:54 
Аватара пользователя
Там большим жирным шрифтом написано: "Время работы алгоритма Евклида", почти что в начале страницы. Ну и дальше по тексту...

 
 
 
 
Сообщение13.02.2008, 11:04 
Аватара пользователя
На самом деле, в точности на Ваш вопрос:
Atij писал(а):
Или по-другому: как вывести формулу нахождения числа m, такого,что при заданном n, происходит наибольшее кол-во шагов для вывода НОД`a
указанная мной ссылка не отвечает. Она отвечает на Ваш вопрос:
Atij писал(а):
Вот такой вопрос: как вывести формулу при кот-ой алгоритм работает максимально долго?
и указывает, на каких парах чисел реализуется оценка сверху времени работы алгоритма.

 
 
 
 
Сообщение13.02.2008, 15:13 
Аватара пользователя
Всем большое спасибо, вопрос решён.

 
 
 
 
Сообщение01.03.2008, 13:08 
Аватара пользователя
Кстати, этот факт теоремой Ламе называется.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group