سوال ۲۵ پروجکت اویلر - عدد فیبوناتچی ۱۰۰۰ رقمی

سوال 25 پروجکت اویلر با نام اولین عدد فیبوناتچی 1000 رقمی را به همراه جواب برای المپیاد ریاضی و کامپیوتر در ادامه مطلب مشاهده کنید.

---

اولین عدد فیبوناتچی ۱۰۰۰ رقمی

میدانیم که هر عدد فیبوناتچی از جمع دو عدد قبلی بدست می آید که رابطه ی بازگشتی آن به صورت زیر می‌شود:

F_n = F_n1 + F_n2, F₁ = 1 and F₂ = 1

حال F12 را در نظر بگیرید.حاصل F₁₂ = 144 می‌باشد.F₁₂ دوازدهمین عدد فیبوناتچی و از طرفی اولین عدد ۳ زقمی فیبوناتچی است.

سوال:اولین عدد فیبوناتچی که تعداد ارقام آن ۱۰۰۰ است٬چندمین عدد از دنباله‌ی فیبوناتچی است؟

---

پاسخ سوال

روش اول (Brute Force)«مخصوص المپیاد کامپیوتر»:

این روش به بیل زدن معروف است D: .این روش اعداد فیبوناتچی را تا جایی ادامه می‌دهد و جمع می‌کند که به ۱۰۰۰ رقم برسد!(البته ماکه نمی‌توانیم عدد را به صورت عادی بدست بیاوریم.چون Long Long شصت و چهار رقم است.)

کد:http://tny.cz/e9869ac4

روش دوم (Aljebra)«مخصوص المپیاد ریاضی‌ها»:

این روش مخصوص المپیاد ریاضی هاست و از نابرابری و لگاریتم گرفتن برای رسیدن به جواب استفاده می کند.اگر المپیاد کامپیوتری ها هم بلد باشند،ضرری ندارد.پس شروع می کنم:

می‌دانیم که عدد طلایی برابر است با :

 

خوب.فرمول فیبوناتچی به شکل زیر است:

از فرمول بالا نتیجه زیر را میگیریم:

n*log(phi) - 0.5*log(5) ≥ 999
n*log(phi) ≥ 999 + 0.5*log(5) = 999.349

n ≥ 999.349/log(phi) = 999.349/0.2090

با حل نابرابری به عدد ۴۷۸۲ می‌رسیم.

---

موفق باشید.

سپهر محمدی - کد٬کد و بازهم کد