الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
مسئله‌ی Column Addition - الگوریتمستان
الگوریتمستان
  »  

مسئله‌ی Column Addition

        بررسی مسئله‌ی Column Addition، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2017 سایت تهران
آنچه در این نوشته می‌خوانید:
   •  مسئله‌ی Column Addition
       »  مسئله
       »  ورودی برنامه
       »  خروجی برنامه
       »  حل مسئله

مسئله

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

رابطه‌ی جمع زدن دو عدد را در نظر بگیرید:

مسئله‌ی Column Addition

این عملیات در پس‌زمینه انجام می‌گیرد که کنترل آن خارج از اختیار ما است و خروجی آن لزوما نشانگر جمع صحیح نیست. اما می‌توانیم هر تعداد ستون دلخواه از آن را حذف کنیم تا به جمع درستی برسیم. به عنوان نمونه، در مثال زیر می‌توانیم با حذف ستون‌های دوم و چهارم به جمع درستی برسیم:

مسئله‌ی Column Addition

ماموریت شما یافتن حداقل تعداد ستون‌هایی است که با حذف آنها عبارت محاسباتی درست است.

ورودی برنامه

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

هر دسته ورودی برنامه با یک عدد مثبت $n$ نابیشتر از $1000$ آغاز می‌شود که بیانگر تعداد ستون‌های اعداد است و پس از آن سه سطر شامل سه عدد با آن تعداد رقم می‌آید. این اعداد به ترتیب دو عدد ورودی عملیات جمع چندستونی و عدد خروجی آن هستند. ورودی زمانی پایان می‌یابد که عدد صفر برای تعداد ستون‌ها ارسال شود.

3

123

456

579

5

12127

45618

51825

2

24

32

32

5

12299

12299

25598

0

خروجی برنامه

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

به ازای هر دسته ورودی تنها یک عدد در سطر مجزا چاپ شود که حداقل ستون‌های مورد نیاز برای حذف را نشان می‌دهد.

0

2

2

1

منبع: مسابقه‌ی برنامه‌نویسی ACM-ICPC منطقه‌ای سایت تهران 2017 - مسئله‌ی Column Addition

حل مسئله

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

هر انتخابی از ستون‌ها ممکن است ما را به جواب برساند. در واقع هدف ما انتخاب کوچکترین زیرمجموعه از مجموعه‌ی ستون‌ها است که با حدف آنها، حاصل جمع به درستی محاسبه شده باشد. ساده‌ترین راهکار ممکن برای حل مسئله آن است که تمام حالات ممکن برای حذف ستون‌ها را بررسی کنیم. هر مجموعه با $n$ عضو $2^n$ زیرمجموعه دارد. بنابراین اگر بخواهیم در این مسئله تمام زیر مجموعه‌های ممکن را بررسی کنیم، در بدترین حالت باید $2^{1000}$ زیرمجموعه پردازش کنیم که در عمل غیر ممکن است.

در این انتخاب‌ها باید این موضوع را نیز در نظر داشته باشیم که بود یا نبود یک ستون مستقل از سایر ستون‌ها نیست و رقم نقلی ستون قبل نیز در آن نقش داشته و وجود یا عدم وجود آن در رقم نقلی انتقالی به ستون بعدی اثر دارد. نکته‌ی دیگر آن است که وجود یا عدم وجود برخی ستون‌ها قطعی است. به عنوان نمونه، اگر دو عدد 2 و 5 جمع زده شده و خروجی 9 تولید شده باشد، این ستون حتما باید حذف شود؛ یا ستون‌هایی از سمت راست که با رقم نقلی صفر به درستی جمع زده شده‌اند، قطعا نباید حذف شوند (چرا؟). اما چنین پیش‌پردازش‌هایی لزوما جواب نهایی را تولید نکرده و ما همچنان نیاز به الگوریتم بهینه برای حل مسئله داریم. بهتر است این الگوریتم به گونه‌ای طراحی شود که حالت استثناء نداشته و متکی به پیش‌پردازش نباشیم. مثال زیر نمونه‌ای است که پیش‌پردازش‌های فوق روی آن اثری ندارند و کمکی به ما نمی‌کنند.

111119

111119

322228

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

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

در حل مسئله‌ی کوله‌پشتی صفر و یک با $n$ کالا و حداکثر بار قابل تحمل $W$، ماتریس $M$ با ابعاد $(n+1) \times (W+1)$ داریم که عدد عنصر $M_{ij}$ حداکثر ارزش قابل حمل در کوله‌پشتی از بین $i$ کالای اول با محدودیت مجموع وزن $j$ است. ماتریس خط به خط و خانه به خانه پر می‌شود تا به عنصر $M_{nW}$ برسیم که بهترین جواب ممکن را نشان می‌دهد. نقش داشتن یا نداشتن یک کالا در انتخاب بهینه نیز وابسته به انتخاب کالاهای قبلی و میزان وزن باقیمانده‌ی قابل تحمل کوله‌پشتی است. در مسئله‌ی حال حاضر نیز $n$ ستون داریم که باید تعدادی را برای باقی ماندن انتخاب کنیم و در نهایت حذف‌ها به نحوی باشد که علاوه بر درست بودن عملیات جمع ستون‌ها، رقم نقلی آخرین ستون نیز صفر باشد.

با توجه به آنکه  رقم نقلی ستون‌ها در این عملیات تنها یکی از دو عدد صفر یا یک است (چرا؟)، ماتریس $M$ برای این مسئله می‌تواند یک آرایه‌ی دو بعدی با ابعاد $ 2 \times (n + 1)$ باشد. عددی که در خانه‌ی M[i][j] نوشته می‌شود، بیانگر حداقل تعداد ستون‌های حذف شده از $j$ ستون اول اعداد (شمارش از سمت راست) با شرط تولید رقم نقلی $i$ است. ستون اول ماتریس $(j=0)$ بیانگر حالتی است که هیچ ستونی وارد عملیات پردازش نشده است. بدیهی است در این حالت رقم نقلی صفر است و چون ستونی نداریم، مقدار M[0][0] (کمترین ستون حذف شده تا این لحظه) صفر می‌شود. از سوی دیگر، امکان ندارد در چنین شرایطی رقم نقلی یک تولید شود. در این حالت انتخاب یا عدم انتخاب ستون مطرح نیست و در واقع با شرایطی مواجه هستیم که در کل باید کنار گذاشته شود. پس M[1][0] را $n$ قرار می‌دهیم. این عدد یا هر عدد بزرگتر از آن جریمه‌ای است که باعث می‌شود این حالت در طی محاسبات برای یافتن جواب بهینه به صورت خودکار حذف شود. چرا که حداکثر تعداد ستون‌های قابل حذف (بدترین جواب ممکن) همان $n$ است.

پس از مقداردهی ثابت ستون اول، سایر ستون ها یک به یک بر اساس قوانین زیر از روی مقادیر ستون قبلی پر می‌شوند. در ادامه منظور از $a$، $b$ و $c$ به ترتیب ارقام اول تا سوم یک ستون از عملیات جمع هستند.

1- مقدار M[0][j]: اگر ستون $j$ برای ماندن انتخاب نشود، تعداد M[0][j-1] ستون قبل از آن حذف شده که در نهایت رقم نقلی صفر تولید شده و با حذف این ستون باید یک واحد به آن اضافه شود. اگر این ستون انتخاب شود، سه حالت ممکن است اتفاق بیفتد. اگر $a + b$ برابر $c$ باشد، از ستون‌های قبلی باید حالتی را در نظر بگیریم که رقم نقلی صفر به این ستون رسیده باشد که با M[0][j-1] ارتباط دارد. اما اگر $a + b$ یک واحد کمتر از $c$ باشد، برای انتخاب باید رقم نقلی یک از ستون‌های قبلی به این ستون رسیده باشد که با M[1][j-1] مرتبط است. در غیر از این دو حالت، غیر ممکن است که جمع به درستی انجام شده و رقم نقلی صفر نیز به ستون بعدی منتقل شود. در این شرایط باید مقدار $n$ لحاظ شود. حال که وضعیت ستون در دو حالت انتخاب یا عدم انتخاب را بررسی کردیم، کمترین مقدار بین این دو عدد، مقداری است که در M[0][j] قرار داده می‌شود:

\[ M[0][j]= min(M[0][j-1] + 1, t) \]

\[t = \left\{\begin{matrix} M[0][j - 1] & & & if \; a + b = c\\ M[1][j - 1] & & & if \; a + b + 1 = c \\ n & & & Otherwise \end{matrix}\right. \]

2- مقدار M[1][j]: به همان ترتیب فوق، اگر ستون $j$ برای ماندن انتخاب نشود، تعداد M[1][j-1] ستون قبل از آن حذف شده که در نهایت رقم نقلی یک تولید شده و با حذف این ستون باید یک واحد به آن اضافه شود. اگر این ستون انتخاب شود، سه حالت ممکن است اتفاق بیفتد. اگر $a + b$ دو رقمی بوده و رقم یکان آن برابر $c$ باشد، از ستون‌های قبلی باید حالتی را در نظر بگیریم که رقم نقلی یک به این ستون رسیده باشد که با M[0][j-1] ارتباط دارد. اما اگر $a + b + 1$ دو رقمی بوده و رقم یکان آن برابر $c$ باشد، برای انتخاب باید رقم نقلی یک از ستون‌های قبلی به این ستون رسیده باشد که با M[1][j-1] مرتبط است. در غیر از این دو حالت، غیر ممکن است که جمع به درستی انجام شده و رقم نقلی یک نیز به ستون بعدی منتقل شود. در این شرایط باید مقدار $n$ لحاظ شود.

\[ M[1][j]= min(M[1][j-1] + 1, t)\]

\[t = \left\{\begin{matrix} M[0][j - 1] & & & if \; a + b > 9 \; and \; (a+b) \; \% \; 10 = c\\ M[1][j - 1] & & & if \; a + b + 1 > 9 \; and \; (a + b + 1) \; \% \; 10 \;= c \\ n & & & Otherwise \end{matrix}\right. \]

پس از اتمام عملیات پر کردن آرایه، مقدار M[0][n] پاسخ بهینه‌ی مورد نظر ما است (چرا؟). در ادامه ماتریس پر شده برای نمونه‌ی دوم ورودی برنامه و همینطور مثال نقض الگوریتم حریصانه آمده است.

مسئله‌ی Column Addition

بر اساس توضیحات و اینکه صرفا ماتریس با تعداد سطرهای ثابت را پر می‌کنیم، الگوریتم پیشنهادی از مرتبه‌ی پیچیدگی $O(n)$ است که نشان از کارایی مطلوب آن دارد.

به اشتراک‌گذاری نوشته
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
پیوندها برای مطالعه‌ی بیشتر
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

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

وبگاه:

متن پیام: *

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

 


• .320
دوشنبه، ۶ فروردین ماه ۱۳۹۷، ساعت ۱۹:۴۵

14


• .320
دوشنبه، ۶ فروردین ماه ۱۳۹۷، ساعت ۱۹:۴۵

14


الگوریتمستان در تلگرام

   

   

پیوند کوتاه: عمر نوشته:  ۲۵۳ روز
تعداد بازدید:  ۲۹۵۴ بازدید
تعداد امتیاز:  ۱ امتیاز
میانگین امتیاز:  ۵.۰۰  از  ۵.۰۰
»  سوالات تمرینی مسابقه‌ی برنامه‌نویسی ACM-ICPC 2018 (سری اول)
        سری اول سوالات تمرینی برای شرکت کنندگان مسابقه‌ی برنامه‌نویسی ACM-ICPC 2018
»  مسئله‌ی آتش‌سوزی در برره
        بررسی مسئله‌ی آتش در برره، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2017 سایت تهران
»  مسئله‌ی حداکثر مجموع
        بررسی مسئله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
»  مسئله‌ی Turn the Lights Off
        متن فارسی و روش حل مسئله‌ی Turn the Lights Off از سوالات وبسایت UVa Online Judge
»  مسئله‌ی Jolly Jumpers
        متن فارسی مسئله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مستندات دوره‌ی آمادگی مسابقات برنامه‌نویسی دانشگاه استنفورد
        مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
»  مسئله‌ی The Trip
        متن فارسی مسئله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مسئله‌ی 3n+1 Problem
        متن فارسی مسئله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مسئله‌ی Encrypted SMS
        متن فارسی مسئله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
»  مسئله‌ی Gholam's Simple Game
        متن فارسی مسئله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران
»  مسئله‌ی What Base Is This
        متن فارسی مسئله‌ی شماره‌ی 343 از UVa Online Judge، ار سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی
»  مسئله‌ی انتخابات
        بررسی مسئله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران
»  مسئله‌ی اعداد اردوش
        بررسی مسئله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی موجود در کتاب Programming Challenges و وبسایت UVa Online Judge
»  مسئله‌ی بشکه‌های آب
        بررسی مسئله‌ی بشکه‌های آب (Water Barrels)، از سوالات مسابقات برنامه‌نویسی بیان