اثبات کنید

[leyla]

با سلام
دوستان عزیز: :)

می خواهیم بزرگترین مقسوم علیه دو عدد را به وسیله الگوریتم اقلیدس بدست بیاوریم
اثبات کنید که بدترین حالت اجرای این الگوریتم زمانی است که دو عنصر ورودی الگوریتم دو عدد متوالی از دنباله فیبوناچی است.

[MSK]

:گیج: میشه بیشتر توضیح بدی؟

[leyla]

منظور از الگوریتم اقلیدس همان تقسیم نردبانی است که به وسیله آن بزرگترین مقسوم علیه را بدست می آوریم ومیخواهیم اثبات کنیم بدترین حالت اجرای این الگوریتم زمانی است که وروردی های ما دو عدد متوالی از دنباله فیبوناچی است

fib=0,1,1,2,3,5,8,13,...,n

[phantasm]

سلام;


امیدوارم انگلیسیت خوب باشه .
قسمت The Fibonacci Sequence and the Euclidean Algorithm رو بخون:

Euclid's Algorithm (http://www.emba.uvm.edu/~cooke/ecldalg.pdf)

[leyla]

دوست عزیز از کمکتان ممنونم :flower: :تشویق:
اگر امکان دارد قسمت آخر اثبات را توضیح دهید . :گیج:

[phantasm]

خواهش میکنم.

کجاش رو نفهمیدی؟توی این اثبات نشون داده که اعداد سری فیبوناچی از F6=F5(n)+1 به بعد بزرگتر از 10 ^ n میشن پس تعداد مراحل الگوریتم اقلیدس برای هر دو عدد متوالی فیبوناچی 5N میشه که از تعداد مراحل بین هر دو عدد دیگه ای بزرگتره ٬ اگه خوب به سری فیبوناچی نگاه کنید به وضوح میبینید که اگه هر دو عدد متوالی از این سری رو انتخاب کنید برای یافتن ب.م.م (greatest common divisor) به تعداد اعداد قبلشون الگوریتم اقلیدس باید اجرا بشه:


fibonacci:1,1, 2, 3, 5, 8, 13, 21, 34,55, 89,...




(89, 55)=(55, 34)=(34, 21)=(21, 13)=(13, 8)=(8, 5)=(5, 3)=(3, 2)=(2, 1)=(1, 1)=(1, 0)=1


پس چون تعداد مراحل اجرای الگوریتم اقلیدس به تعداد اعداد قبلی فیبوناچی بستگی داره با اثبات درجه رشد سری فیبوناچی ٬ رشد مراحل اجرای الگوریتم اقلیدس رو ثابت کردیم.
متاسفانه من سوادم زیاد قد نمیده و الا در اینباره بحث های تئوری زیبا و زیادی وجود داره.......

[mostafa612003]

باسلام-
این لینکی که دادید کار نمی کند؟
تابع بازگشتی این الگوریتم به چه صورت است؟
متشکرم

[mostafa612003]

؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟ ؟؟؟؟؟؟

[majid_b]

کامپایلر c++ رو از کجا میتونم دانلود کنم ؟؟