مساله:
تابع
بازگشتی ( F( n با تعریف زیر مفروض است:
تابع
( S( p, q به این صورت تعریف شده است:
مقدار
( 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 ) x 3 + ( 0 + 1 + 2 + 3 + 4 + 5 ) = 3 x 45 + ( 5
x ( 5 + 1 ) ) / 2
در
حالت کلی، اگر برای هر عدد طبیعی n، متغیرهای q و r مقدار خارج قسمت و باقیمانده
تقسیم آن بر عدد 10 را نمایش دهند، میتوان نوشت:
A( n
) = 45 q + ( r ( 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 ) , 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 x 45 + ( 9 x 10 ) / 2 = ( Sum( 0 ) + 0 + ( 2
x 3 ) / 2 ) + 90 + 45 = ( 0 + 0 + 3 ) + 135 = 138
Sum(
40 ) = Sum( 4 ) + 4 x 45 + ( 0 x 1 ) / 2 = ( Sum( 0 ) + 0 + ( 4 x
5 ) / 2 ) + 180 + 0 = ( 0 + 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
با استفاده از حلقههای تکرار و به صورت غیربازگشتی نیز قابل پیادهسازی
است.