مسئله‌ی Simple Addition

بررسی مسئله‌ی Simple Addition از سوالات آمادگی مسابقات برنامه‌نویسی

آنچه در این نوشته می‌خوانید:

   •  مسئله‌ی Simple Addition
       »  مسئله
       »  ورودی برنامه
       »  خروجی برنامه
       »  حل مسئله

مسئله

تابع بازگشتی (F(n با تعریف زیر مفروض است:

\[ F(n)= \left\{\begin{matrix} n \% 10 & & & if \; (n\%10) > 0\\ 0 & & & if \; n = 0 \\ F(n/10) & & & Otherwise \end{matrix}\right. \]

تابع (S(p, q به این صورت تعریف شده است:

\[ S(p,q)=\sum_{i=p}^{q} F(i) \]

مقدار (S(p, q را به ازای مقادیر ورودی p و q محاسبه کنید.

ورودی برنامه

[بازگشت به فهرست]

ورودی برنامه شامل چندین خط است. در هر خط اعداد نامنفی p و q با شرط p ≤ q قرار دارند که در متغیرهای 32 بیتی قابل ذخیره‌سازی هستند.

انتهای ورودی با دو عدد منفی مشخص می‌شود که نباید به عنوان ورودی مسئله پردازش شوند.

1 10

10 20

30 40

-1 -1

خروجی برنامه

[بازگشت به فهرست]

به ازای هر خط ورودی، یک خط خروجی شامل مقدار (S(p, q خواهد بود.

منبع: وب‌سایت UVa Online Judge - مسئله‌ی Simple Addition

حل مسئله

[بازگشت به فهرست]

با توجه به گستره‌ی مقدار p و q، راه حل مستقیم و محاسبه‌ی مقادیر با استفاده از دو تعریف فوق زمان‌بَر بوده و نمی‌تواند پاسخ مسئله باشد. پس روی عملکرد دو تابع (F(n و (S(p, q تمرکز می‌کنیم.

تابع (F(n به ازای n = 0 مقدار صفر را دارد. به ازای هر عدد طبیعی n، اگر باقیمانده‌ی تقسیم n بر عدد 10 غیرصفر باشد، مقدار باقیمانده را باز می‌گرداند. در غیر این صورت خود تابع با مقدار n / 10 فراخوانی می‌شود. این عمل یعنی این که اگر یکان عدد n غیرصفر باشد، آن یکان به عنوان خروجی تولید شده و در غیر اینصورت تابع با حذف این عدد صفر از محل یکان، مجددا فراخوانی می‌شود. به عنوان مثال:

\[F(23913) = 3 \]

\[F(74133800) = F(7413380) = F(741338) = 8 \]

پس می‌توان گفت (F(n کم‌ارزشترین رقم غیرصفر - یا اولین رقم غیر صفر از سمت راست - عدد n را باز می‌گرداند.

عملکرد تابع (S(p, q مشخص است. اما نکته اینجا است که خروجی تابع (F(n همواره یک عدد یک رقمی است که با قانون خاصی به صورت شبه‌تناوبی تکرار می‌شود. دنباله‌ی زیر، خروجی تابع F به ازای اعداد n = 1 تا n = 35 را نشان می‌دهد:

1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 3, 1, 2, 3, 4, 5

همانگونه که مشاهده می‌شود، اعداد با ترتیب خاصی پشت سر هم تولید شده‌اند. علت این مسئله کاملا مشخص است. اعداد متوالی، یکان‌های متناوبی تولید می‌کنند. اگر این یکان صفر باشد، به رقم بعدی رجوع می‌شود که خود آن ارقام نیز به صورت صعودی افزایش یافته و مجددا به صورت متناوب تکرار می‌شوند.

در مثال فوق، اگر رقم یکان مقدار ورودی تابع (یعنی n) را نمایش داده شود، دنباله‌ی زیر تولید می‌شود:

1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5

در این دنباله، زیردنباله‌ی اعداد صفر تا 9 سه بار تکرار شده و در انتها اعداد صفر تا پنج ظاهر شده‌اند. مجموع این اعداد را با می‌توان به صورت زیر نوشت:

\[ A(35) = (0 + 1 + 2 + 3 + . . . + 9) \times 3 + (0 + 1 + 2 + 3 + 4 + 5) = 3 \times 45 + \frac{5 \times (5 +1)}{2} \]

در حالت کلی، اگر برای هر عدد طبیعی n، متغیرهای q و r مقدار خارج قسمت و باقیمانده‌ی تقسیم آن بر عدد 10 را نمایش دهند، می‌توان نوشت:

\[ A(n) = 45 q + \frac{r \times (r + 1)}{2} \]

تابع (A(n مجموع یکان‌های اعداد صفر تا n را محاسبه می‌کند. چنین تابعی کمک می‌کند تا مقدار (S(0, n را محاسبه کنیم. تابع (Sum(n را مقدار (S(0, n در نظر می‌گیریم. برای محاسبه‌ی (S(p, q کافی است مقدار عبارت (Sum(q) - Sum(p - 1 را محاسبه کنیم (چرا؟).

قسمتی از مقدار (Sum(n با استفاده از (A(n و جمع زدن یکان‌ها به دست آمد. اما قسمتی از اعداد یکان صفر دارند. برای چنین اعدادی باید دهگان و یا در صورت نیاز ارقام بالاتر بررسی شوند. در مثال فوق، اعداد 10، 20 و 30 ارقام 1 و 2 و 3 را به مجموع اضافه می‌کنند و نتیجه می‌شود:

\[Sum(35) = A(35) + 1 + 2 + 3 \]

این جمع در واقع محاسبه‌ی تابع Sum به ازای خارج قسمت تقسیم 35 بر 10 هستند. در چنین حالتی دنباله‌ی یکان‌های اعداد یک تا سه تولید می‌شوند:

1, 2, 3

این دنباله به ازای n = 125 به صورت زیر است:

1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2

که برای اعداد 10، 20، 30، ...، 100، 110 و 120 تولید شده‌اند. مجموع این ارقام همان (A(12است. هدف ما نیز اضافه کردن این مجموع به (A(125 است. چنین دنباله‌ای یک زیرمسئله از نوع مسئله‌ی اصلی با اندازه‌ی خارج قسمت تقسیم 125 بر 10 است. خود این دنباله نیز شامل رقم صفر است که نشان می‌دهد باز هم باید زیرمسئله با اندازه‌ی خارج قسمت عدد 12 بر عدد 10 محاسبه شود.

در حالت کلی، با محاسبه‌ی (A(n، حل مسئله به جل یک زیرمسئله با اندازه‌ی خارج قسمت تقسیم n بر عدد 10 تبدیل می‌شود. این نتیجه‌گیری با رابطه‌ی زیر قابل بیان است:

\[ Sum(n) = A(n) + Sum (q) \qquad, \qquad Sum(0) = 0 \]

که منظور از q خارج قسمت تقسیم n بر عدد 10 است.

تابع Sum یک تابع بازگشتی است که در هر مرحله‌ی مقدار ورودی ده برابر کوچکتر می‌شود. چنین تابعی از مرتبه‌ی اجرای (O(log₁₀n است که در مقایسه با روش محاسبه‌ی مستقیم بسیار کاراتر عمل می‌کند.

قطعه کد زیر به زبان برنامه‌نویسی ++C تابع Sum را پیاده‌سازی می‌کند:

1 long Sum(long n){
2   if(n == 0)
3     return 0;
4   long q = n / 10;
5   int r = n % 10;
6   return (Sum(q) +  q * 45  + (r * (r + 1)) / 2);
7 }

برای مثال، مقدار خروجی با داده‌های خط سوم ورودی به این صورت است:

\[ Sum(29) = Sum(2) + 2 \times 45 + \frac{9 \times 10}{2} = (Sum(0) + 0 + \frac{2\times 3}{2}) + 90 + 45 = (3) + 135 = 138 \]

\[ Sum(40) = Sum(4) + 4 \times 45 +\frac{ 0 \times 1 }{ 2 } = (Sum(0) + 0 + \frac{4 \times 5 }{ 2}) + 180 + 0 = (10) + 180 = 190 \]

\[ S(30, 40) = Sum(40) - Sum(29) = 190 - 138 = 52 \]

به بیان دیگر:

\[Sum(29) = A(29) + A(2) \]

\[Sum(40) = A(40) + A(4) \]

یا:

\[Sum(125) = A(125) + A(12) + A(1) \]

توجه: تابع Sum با استفاده از حلقه‌های تکرار و به صورت غیربازگشتی نیز قابل پیاده‌سازی است.

1	long Sum(long n){
2	if(n == 0)
3	return 0;
4	long q = n / 10;
5	int r = n % 10;
6	return (Sum(q) + q * 45 + (r * (r + 1)) / 2);
7	}