حل مسئله ۱ اویلر به زبان پایتون: مجموع مضارب ۳ و ۵
مسأله ۱ اویلر: مضارب ۳ و ۵
اگر همه اعداد طبیعی زیر 10 را که مضرب 3 یا 5 هستند لیست کنیم ، 3 ، 5 ، 6 و 9 را به دست می آوریم. مجموع این ضربها 23 است.
مجموع همه مضرب های 3 یا 5 زیر 1000 را بیابید.
حل آسان و کند
اولین راه حلی که به ذهن میرسد این است که:
- ابتدا متغیری برای نگهداری مجموع اعداد در نظر بگیریم.
- حلقهای از صفر تا ۱۰۰۰ ایجاد کنیم.
- هر بار شمارنده حلقه را به عدد ۳ یا ۵ تقسیم کنیم و در صورتی که باقیمانده صفر شد، آن شمارنده را به مجموع اضافه کنیم.
کد این راه حل را میتوان به راحتی با یک خط (خط ۲) و یا به صورت کلاسیکی در یک حلقه(خط ۵ تا ۱۰) پیاده سازی کرد:
این برنامه برای رنجی که ما تعیین کردیم یعنی از ۱ تا ۱۰۰۰ خیلی سریع اجرا میشود، اما برای موارد بزرگتر مانند \(10^9\) بازدهی خوبی ندارد. بنابراین، ما باید راهی کارآمدتر برای محاسبه این مقدار بدون حلقه پیدا کنیم.
راه حل بدون حلقه و سریع
فردریش گاوس برای محاسبه مجموعه n عدد طبیعی فرمولی را ارائه کرد که این فرمول به قرار زیر است:
$$ \sum_{i}^{n}i = \frac{n(n+1)}{2} $$
به عنوان مثال، وقتی n = 10 مجموع همه اعداد طبیعی 1 تا 10 برابر است با:
$$ (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) = \frac{10\times 11}{2} = 55 $$
این نمونه ای است که این جمع بندی را توصیف می کند. میخواهم نحوه عملکرد این فرمول را طوری دیگری به شما نشان دهم. اعداد یک تا ۱۰ را در دو ردیف به صورت زیر بنویسید:
همانطور که مشاهده میکنید مجموعه هر ستون برابر با ۱۱ شده است و تعداد ستونها ۵تا میباشد یعنی نصف عدد n=10. پس مجموعه این اعداد برابر است با:
$$ = \frac{10}{2}\times 11 = 55 $$
دقت کنید که برای اینکه ستونها به همین شکل جفت بمانند اگر n یک عدد فرد بود از صفر شروع کنید. یعنی اگر n=11 بود اعداد را به این شکل زیر هم قرار میدهند:
در اینجا هم مجموعه هر ستون ۱۱ میشود اما با این تفاوت که این بار ۶ ستون داریم.
همین روش را میتوانیم برای اعدادی که بر یک عدد خاص مثل d قابل تقسیم هست را پیاده سازی کنیم. برای مثال فرض کنید که n = 33 ، d = 3. میخواهیم مجموع مضارب ۳ در عدد ۳۳ را نشان دهیم. از آنجایی که n فرد است، ما از صفر شروع می کنیم.
مشاهده میکنید که در اینجا نیز مجموع هر ستون برابر با ۳۳ شده است و ۶ ستون داریم. پس مجموع اعداد بخش پذیر بر ۳ از یک تا ۳۳ برابر است با: $ 6 \times 33 = 198 $
پس کمی فرمول گاوس را تغییر میدهیم تا بتوانیم به راحتی این مجموع را محاسبه کنیم:
$$ m = [\frac{n}{d}] $$
$$ \sum_{i=1}^{m}id = d\frac{m(m+1)}{2} $$
با استفاده از فرمول بالا میتوانیم مجموع اعداد بخش پذیر بر d را تا عدد n محاسبه کنیم. این کار در کد زیر با تابع sumn انجام میشود. به طور مثال برای محاسبه مجموع اعداد بخش پذیر بر ۳ و کوچکتر از ۱۰۰۰ کافی است که ورودی تابع ۹۹۹ و ۳ باشد تا مجموع بازگردانده شود. برای اعداد بخش پذیر بر ۵ نیز به همین صورت. برای هر دوی آنها کافی است که خروجی دو فراخوانی تابع را با هم جمع کنیم.
عددی مثل ۱۵ هم در اعداد بخش پذیر بر ۳ جمع شده است و هم در اعداد بخش پذیر بر ۵. پس باید این مقدارها را چون دوبار محاسبه شده اند از حاصل جمع کلی کم کنیم.
دیدید که این راه حل بسیار سریعتر از راه حل قبلی و بدون نیاز به حلقه است. راستی یادتون نره که باید از عدد مرز خود یکی کم کنید تا آنرا حذف کنیم. تمام این توضیحات با کدهای پایتون زیر تقدیم نگاهتان:
منتظر پیشنهادات و راهحلهای بهتر شما هستم.
دیدگاهتان را بنویسید