بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین Educational Codeforces Round 20

»    مسأله‌ی Encrypted SMS

»    ویدئوهای آموزشی کلاس Programming Challenges  

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مسأله‌ی 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(log 10 n  است که در مقایسه با روش محاسبه‌ی مستقیم بسیار کاراتر عمل می‌کند.

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


این نوشته آخرین بار در تاریخ پنجشنبه، ۱۰ فروردین ماه ۱۳۹۶ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        متن فارسی مسأله‌ی Encrypted SMS  از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
        معرفی کتاب آموزش الکترونیکی رایگان «ساختمان داده‌ها» به زبان فارسی با قابلیت دانلود
        متن فارسی مسأله‌ی Gholam's Simple Game  از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010 ‌ منطقه‌ای سایت تهران
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016  سایت تهران
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        بررسی مسأله‌ی اعداد اردوش (Erdos Numbers)  یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسأله‌ی شماره‌ی 343  از UVa Online Judge ، ار سوالات تمرینی کتاب Art of Programming Contest
        بررسی مسأله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
        ویدئوهای آموزشی کلاس Programming Challenges  شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی
        بررسی مسأله‌ی بشکه‌های آب (Water Barrels) ، از سوالات مسابقات برنامه‌نویسی بیان
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

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

وبگاه:

متن پیام: *

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