جلوه هایی از المپیاد کامپیوتر

Aspects of Olympiad in Informatics | A O I

جلوه هایی از المپیاد کامپیوتر

Aspects of Olympiad in Informatics | A O I

Clock second-hand Clock minute-hand Clock hour-hand
جلوه هایی از المپیاد کامپیوتر
چهارشنبه, ۲۶ تیر ۱۳۹۲، ۰۴:۳۱ ب.ظ

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

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


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

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

Fn = Fn−1 + Fn−2, F1 = 1 and F2 = 1

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

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


پاسخ سوال

روش اول (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

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


موفق باشید.

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

موافقین ۳ مخالفین ۱ ۹۲/۰۴/۲۶

نظرات (۸)

  سلام
شما رو به بازدید از وب" شیخ شهید " دعوت میکنیم
لطفا با نظر های خود کمک کنید تا کار کوچکی برای شناخت این استاد بزرگ انجام شود
باتشکر

.: پرتال متفکر شهید استاد مرتضی مطهری :. 
سلام
می خواستم بدونم چی جوری این همه بازدید کننده دارین
ممنون می شم به وبلاگم جوابو ارسال کنین
من برق می خونم با ریاضی هم آشنایی زیادی دارم ولی نه این جور مسائل. اون بخشایی که کاربردی تره مثل معادلات دیفرانسیل ،دستگاههای مختصات استوانه ای و کروی ، انتگرالهای چند گانه، لاپلاس و بسل و فوریه و....
صرفا جهت اطلاع گفتم!!
پاسخ:
این جور مسائل مسائل المپیادین و با درس عادی فرق دارن و هرکسی اینها رو بلد نیست.
۰۹ مرداد ۹۲ ، ۲۱:۵۶ امیر محمد دهقان
Inja webloge olamyad computere ya adabi?!
پاسخ:
سپهر:من برای بازدید کننده های مطلبم احترام قائلم و این احترام یعنی اینکه مطالب رو واضح و روشن بنویسم (و البته بدون غلط املایی) و اصلا دوست ندارم بابت اینکار کسی از من انتقاد کنه.چون این انتقاد کاملا الکیه.اینقدر هم جوابی که برات مینوییم رو پاک نکن .چون از نویسنده ها حذف میشی.
۰۳ مرداد ۹۲ ، ۱۱:۱۴ سید سعید باباییان

***سلام همسنگری...
از بنده ی کمترین قبول کن...
با چهار تا پست بروز شده...
این بار هم با احترام منتظرم...***

+ یازهرا(سلام الله علیها) 
۰۳ مرداد ۹۲ ، ۰۴:۲۸ سیّدمیلاد موسوی
چه نیکوست کودکی که از شیر پاک بزرگ بانویی هم چون زهرا (علیها السلام) نوشیده باشد و در دامان پرمهر بزرگ مردی چون علی (علیه السلام) پرورش یابد و بر دوش آموزگار بزرگ بشر پیامبر اکرم (صلی الله علیه و آله) راه زندگی پیموده باشد ...
+ کودکی از گهر آسمان
    باما همراه باشید ...
۲۸ تیر ۹۲ ، ۲۱:۴۳ عرفان ابوالحسنی
سلام خدمت شما ماه مبارک رمضان بر شما مبارک
بـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــروز شدیم

گر که در این رمضان یار شدی،یادم کن

با خدا محرم اسرار شدی،یادم کن

در سحر ذکر نما در دل خود نام مرا

به دعا لحظه افطار شدی،یادم کن

پاسخ:
Ok
۲۷ تیر ۹۲ ، ۲۱:۵۶ سید سعید باباییان
***سلام همسنگری...
از بنده ی کمترین قبول کن...
با دو تا پست بروز شده...
این بار هم با احترام منتظرم...***

+ یازهرا(سلام الله علیها) 
۲۶ تیر ۹۲ ، ۱۷:۰۴ محمد حسین خانی کوثرخیزی
سلام
من ریاضی محض میخونم
کمکی خواستی بگو :)
پاسخ:
سپهر: سلام. ممنون

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">