حل مسأله ۲ اویلر با پایتون: اعداد زوج فیبوناتچی
مسأله ۲ اویلر:
هر عبارت جدید در دنباله فیبوناتچی، از جمع دو عبارت قبلی با یکدیگر ایجاد می شود. برای مثال با شروع از 1 و 2 ، 10 عبارت اول عبارتند از: 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34 ، 55 ، 89 ،…
مجموع تمام عبارات زوج کمتر از چهار میلیون را بیابید.
حل
دنباله فیبوناتچی به طور رسمی با عبارت بازگشتی زیر تعریف میشود:
$$ F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2} $$
جملاتی از دنباله که توسط این جمله عمومی ایجاد میشوند عبارتند از:
$$ \{ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, … \} $$
هدف این مسأله محاسبه مجموع اعداد زوج از این دنباله با یک حد بالای مشخص میباشد.
یک راه حل خودمانی و ساده
این راه حل برای جواب داده به مسأله اویلر کفایت میکند و به این صورت است که:
- جملات دنباله تولید شود
- با تقسیم بر ۲ تعیین کنیم که جمله زوج است یا فرد
- به متغیر مجموع افزوده شود.
کد زیر نحوه انجام این کار را نشان میدهد:
یک راه حل کارآمدتر با دنباله فیبوناچی تعمیم یافته
جملات زوج دنباله فیبوناتچی به صورت زیر است:
$$ \{0, 2,, 8, 34, 144, 610, … \} $$
این جملات خود تشکیل یک دنباله بازگشتی به صورت زیر را میدهند:
$$ G_0 = 0, G_1 = 2, G_n = 4G_{n-1} + G_{n-2} $$
حال با این دنباله به راحتی میتوان جملات زوج دنباله فیبوناتچی را پیدا کرد؛ از طرفی نیازی به محاسبات جملات فرد که تعداد آنها کم هم نیست، صرفنظر کرد. پس کد پایتون این راه حل را در ادامه تقدیمتان میکنم:
همیشه در سایت وبپای سعی میکنم که ابتدا راهحلی ساده را تقدیم کنم و سپس یک راهحل کمی بهتر را. ممنون میشم اگر شما هم راه حل بهتر از اینها سراغ دارید در بخش دیدگاهها مطرح بفرمایید.
دیدگاهتان را بنویسید