تابع بازگشتی (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 خواهد بود.
46
48
52
منبع: وب‌سایت 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 محاسبه شود.
1
در حالت کلی، با محاسبه (A(n، حل مسئله به جل یک زیرمسئله با اندازه خارج قسمت تقسیم n بر عدد 10 تبدیل می‌شود. این نتیجه‌گیری با رابطه زیر قابل بیان است:
\[ Sum(n) = A(n) + Sum (q) \qquad, \qquad Sum(0) = 0 \]
که منظور از q خارج قسمت تقسیم n بر عدد 10 است.
تابع Sum یک تابع بازگشتی است که در هر مرحله مقدار ورودی ده برابر کوچکتر می‌شود. چنین تابعی از مرتبه اجرای (O(log10n است که در مقایسه با روش محاسبه مستقیم بسیار کاراتر عمل می‌کند.
قطعه کد زیر به زبان برنامه‌نویسی ++C تابع Sum را پیاده‌سازی می‌کند:
long Sum(long n){
if(n == 0)
return 0;
long q = n / 10;
int r = n % 10;
return (Sum(q) + q * 45 + (r * (r + 1)) / 2);
}
برای مثال، مقدار خروجی با داده‌های خط سوم ورودی به این صورت است:
\[ 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 با استفاده از حلقه‌های تکرار و به صورت غیربازگشتی نیز قابل پیاده‌سازی است.