سوال دوم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;
}