بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره
حمایت از وب‌گاه:
حمایت از این صفحه:
مسأله‌ی Simple Addition - الگوریتمستان
الگوریتمستان
1214.835.00
  »  

       

بررسی مسأله‌ی 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 خواهد بود.

      

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 با استفاده از حلقه‌های تکرار و به صورت غیربازگشتی نیز قابل پیاده‌سازی است.


این نوشته آخرین بار در تاریخ سه‌شنبه، ۸ دی ماه ۱۳۹۴ مورد بازنویسی نگارشی قرار گرفته است.
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left