برنامه محاسبه مجموع اعداد از ۱ تا n – راهنمای کاربردی

در این مطلب، آموزش نوشتن برنامه محاسبه مجموع اعداد از ۱ تا n به همراه کد پیاده‌سازی روش‌های مذکور در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ‌پی» (PHP) ارائه شده است. فرض می‌شود که عدد n داده شده است. هدف، پیدا کردن مجموع همه اعداد از ۱ تا n است.

مثال:

Input: n = 5
Output: Sum of digits in numbers from 1 to 5 = 15

Input: n = 12
Output: Sum of digits in numbers from 1 to 12 = 51

Input: n = 328
Output: Sum of digits in numbers from 1 to 328 = 3241

روش اول برای محاسبه مجموع اعداد از ۱ تا n

یک راهکار ساده و پیش پا افتاده برای حل مساله بیان شده، شروع از ۱ تا n و محاسبه مجموع در x، با پیمایش همه ارقام x است. در زیر، روش پیاده‌سازی این مورد بیان شده است.

برنامه محاسبه مجموع اعداد از ۱ تا n در ++C

برنامه محاسبه مجموع اعداد از ۱ تا n در جاوا

برنامه محاسبه مجموع اعداد از ۱ تا n در پایتون ۳

برنامه محاسبه مجموع اعداد از ۱ تا n در #C

برنامه محاسبه مجموع اعداد از ۱ تا n در PHP

خروجی

خروجی قطعه کدهای بالا برای n = ۳۲۸ به صورت زیر است.

Sum of digits in numbers from 1 to 328 is 3241

روش دوم محاسبه مجموع اعداد از ۱ تا n

راهکار بالا، روش ساده‌ای است. در ادامه، یک روش موثرتر برای حل مساله مذکور ارائه می‌شود.

فیلم آموزش محاسبات عددی در پایتون Python در فرادرس

کلیک کنید

مثال‌های زیر در این راستا قابل توجه هستند.

sum(9) = 1 + 2 + 3 + 4 ........... + 9
       = 9*10/2 
       = 45

sum(99)  = 45 + (10 + 45) + (20 + 45) + ..... (90 + 45)
         = 45*10 + (10 + 20 + 30 ... 90)
         = 45*10 + 10(1 + 2 + ... 9)
         = 45*10 + 45*10
         = sum(9)*10 + 45*10 

sum(999) = sum(99)*10 + 45*100

به طور کلی، می‌توان (sum(10^d – 1 را با استفاده از رابطه زیر محاسبه کرد.

 sum(10d - 1) = sum(10d-1 - 1) * 10 + 45*(10d-1)

در کدهای ارائه شده در پایین، فرمول بالا با استفاده از «برنامه‌نویسی پویا» (Dynamic Programming) استفاده شده است، زیرا چند زیرمساله دارای هم‌پوشانی وجود دارد. فرمول بالا گام اصلی روش مورد استفاده است. در ادامه، الگوریتم کامل آمده است.

الگوریتم محاسبه مجموع اعداد از ۱ تا n

1. تعداد ارقام از ۱ تا n، منهای یکی را پیدا کن. این مقدار را d بنام. (برای ۳۲۸، مقدار d برابر با ۲ است.)
2. مجموع ارقام از ۱ تا 10^d - 1 را محاسبه کن. این مجموع را w بنام. برای ۳۲۸، مجموع اعداد از ۱ تا ۹۹ را با استفاده از فرمول بالا محاسبه کن. (برای ۳۲۸، مجموع ارقام از ۱ تا ۹۹ با استفاده از فرمول بالا محاسبه می‌شود.)
3. موثرترین رقم (Most significant digit | msd) در n را پیدا کن. (برای ۳۲۸، msd عدد ۳ است.)
4. مجموع کل، برابر با مجموع عبارات زیر است.
   • مجموع ارقام از ۱ تا «msd * 10d - 1». برای ۳۲۸، مجموع ارقام از ۱ تا ۲۹۹ است. (برای ۳۲۸، مقدار 3*sum(99) + (1 + 2)*100 محاسبه می‌شود. توجه به این نکته لازم است که (sum(299 برابر با (sum(99 به علاوه ارقام از ۱۰۰ تا ۱۹۹ به علاوه ارقام از ۲۰۰ تا ۲۹۹ است. مجموع ۱۰۰ تا ۱۹۹، برابر است با sum(99) + 1*100 و مجموع ۲۹۹ برابر است با sum(99) + 2*100. به طور کلی، این مجموع را می‌توان به صورت w*msd + (msd*(msd-1)/2)*10^d محاسبه کرد.
   • مجموع ارقام از msd * 10^d تا n را محاسبه کن. (برای ۳۲۸، مجموع ارقام از ۳۰۰ تا ۳۲۸ باید محاسبه شود. برای ۳۲۸، این مجموع به صورت 3*29 + فراخوانی بازگشتی (sum(28 محاسبه می‌شود. به طور کلی، این مجموع را می‌توان به صورت ((msd * (n % (msd*10d) + 1) + sum(n % (10d محاسبه کرد.)
5. در ادامه، پیاده‌سازی الگوریتم بالا ارائه شده است.

برنامه محاسبه مجموع اعداد از ۱ تا n در ++C

برنامه محاسبه مجموع اعداد از ۱ تا n در جاوا

برنامه محاسبه مجموع اعداد از ۱ تا n در پایتون ۳

برنامه محاسبه مجموع اعداد از ۱ تا n در #C

برنامه محاسبه مجموع اعداد از ۱ تا n در PHP

خروجی

خروجی قطعه کد بالا برای n = 328 به صورت زیر است.

Sum of digits in numbers from 1 to 328 is 3241

الگوریتم کارآمد، دارای یک مزیت دیگر نیز هست. بر اساس این مزیت، تنها یک بار نیاز به محاسبه []a است، حتی وقتی که چندین ورودی وجود داشته باشد.

روش سوم محاسبه مجموع ارقام از ۱ تا n

پیاده‌سازی بالا، پیچیدگی زمانی از مرتبه (O(d² دارد، زیرا هر فراخوانی بازگشتی، آرایه []dp را یکبار دیگر محاسبه می‌کند. اولین فراخوانی، (O(d را می‌گیرد، دومین فراخوانی (O(d-1 را می‌گیرد، سومین فراخوانی (O(d-2 را می‌گیرد و به همین صورت.

نیازی به محاسبه آرایه []dp در هر فراخوانی بازگشتی نیست. در زیر، پیاده‌سازی اصلاح شده که از مرتبه (O(d است در زبان‌های #C و جاوا ارائه شده است. در اینجا، d تعداد ارقام عدد ورودی است.

برنامه بهینه محاسبه مجموع اعداد از ۱ تا n در جاوا

برنامه بهینه محاسبه مجموع اعداد از ۱ تا n در #C

خروجی

Sum of digits in numbers from 1 to 328 is 3241

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

^^