Вот пример нахождения наибольшего общего
Пример 2
Вот пример нахождения наибольшего общего делителя нескольких чисел.
GCD[Fibonacci[945],Fibonacci[901,Fibonacci[450]] 1134903170
Раз уж мы заговорили о числах Фибоначчи, значит, мы не можем обойти случаи, которые традиционно считаются "наихудшими" для алгоритмов нахождения наибольшего общего делителя.
"Наихудшие" случаи для алгоритмов нахождения наибольшего общего делителя
"Наихудшим" случаем для классического алгоритма Евклида нахождения наибольшего общего делителя считается случай соседних чисел Фибоначчи. Чтобы оценить быстродействие, попытаемся, например, определить, при каком n будет заметна задержка при вычислении GCD[Fibonacci [n+2] (Fibonacci[n+1]]. Возьмем, например, следующую программу.
Do[Print[n,":",GCD[Fibonacci[n+2],Fibonacci[n+1]]],(n, 10000}]
Увы! Алгоритм, реализованный в системе Mathematica, столь эффективен, что даже на весьма посредственном ПК эта программа выполняется без каких бы то ни было задержек. Если же программу модифицировать так: Do[Print[n,":",GCD[Fibonacci[2An+2], Fibonacci[2An+1]]],{n,10000}] ,то задержка будет весьма ощутимой уже при n = 25. Но не забывайте, что 225 + 2 =33554434, а число Fibonacci[2^25+2] имеет 7012462 цифры! Так что алгоритм, реализованный в системе Mathematica, справляется с классическим "наихудшим" случаем не просто вполне удовлетворительно, а блестяще! Правда, известны алгоритмы, для которых наихудший случай представляют числа u = аn +аn-1, и v= аn-1, где
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий