المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر

سوال دومProject Euler(همراه راه حل)

شنبه, ۱۶ دی ۱۳۹۱، ۰۱:۰۳ ب.ظ

متن سوال:

هر عدد در دنباله فیبوناچی از جمع دو عدد قبل از خودش ساخته شده است و این دنباله با اعداد 1 و 2 شروع می شود.ده عدد اول این دنباله عبارتنداز:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …


پیدا کنید جمع تمام اعداد زوج این دنباله را که کوچکتر از 4,000,000 هستند.

حل:

روش اول:برسی تک تک اعداد(Brute forcing)

در این حالت عدد بعدی دنباله را محاسبه می کنیم اگر کوچکتر از 4000000بود و بر دو بخش پذیر بود اون را با متغیری که جمع ها رو تو اون نگه می داریم جمع می کنیم.

long fib1 = 1;
long fib2 = 1;
long result = 0;
long summed = 0;
 
while (result < 4000000) {
    if ((result % 2) == 0) {
        summed += result;
    }
 
    result = fib1 + fib2;
    fib2 = fib1;
    fib1 = result;
}

همان طور که مشاهده می کنید در بخش سوم کد طریقه ی به دست اومدن عدد رو گذاشتم.

جواب برابر خواهد بود با:4613732

درست است که روش اول سریع است ولی راه های سریع تر دیگری نیز برای محاسبه ی  این عدد هست.

روش دوم:

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

پس اگر ما بتوانیم سه تا سه تا اعداد را به دست بیاوریم سرعت محاسبه خیلی بیشتر می شود.

همان طور که می دانید       Fn = Fn-1 + Fn-2

همچنین می دانیم          Fn-1 = Fn-2 + Fn-3     و     Fn-2 = Fn-3 + Fn-4

حال اگر به جایFn-1 و Fn-2 جایگزینشان یعنی Fn-2 + Fn-3 و Fn-3 + Fn-4 را قرار دهیم حاصل چنین خواهد بود  Fn-2 + Fn-3 + Fn-3 +Fn-4

اگر به جای Fn-2 جایگزینش را قرار دهیم حاصل برابر است با Fn-3 + Fn-4 + Fn-3 +Fn-3 +Fn-4

که خود این برابر است با  3Fn-3 + 2Fn-4

اگر یکی از Fn-4 را باز کنیم این عبارت به دست می آید  3Fn-3 + Fn-4 + Fn-5 + Fn-6

طبق گفته های بالا Fn-3=Fn-4 + Fn-5 پس اگر از Fn-4 + Fn-5 فاکتور بگیریم به جمله مورد نظر یعنی 4Fn-3 + Fn-6 می رسیم .

پس Fn=4Fn-3 + Fn-6

حالا می توانیم تمام جمله های زوج مورد نظر را حساب کنیم.

کد این حالت مساوی است با:

long fib3 = 2;

long fib6 = 0;

long result = 2;

long summed = 0;

 

while (result < 4000000) {

    summed += result;

 

    result = 4*fib3 + fib6;

    fib6 = fib3;

    fib3 = result;

}

نظرات (۰)

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