درس گرفتن از اشتباه‌ها

برنامه‌نویس پرکار هم به‌جای حل مساله به‌شیوه ذهنی، یک مساله برنامه‌نویسی مطرح کرده است که ورودی آن به این صورت است:

اولین خط ورودی‌ها شامل int t است که تعداد حالات مختلف آزمایش را به ما می‌دهد.

اولین خط از هر حالت تست شامل N?X?1000)int N) که تعداد دانه‌هایی است که پیدا شده است.

هر کدام از N خط‌های بعدی شامل دو تا int است که رنگ‌های یک دانه را تشریح می‌کند. رنگ‌ها به‌صورت 1 تا 50 ارائه می‌شوند.

برای هر حالت آزمایش، شماره حالت آزمون را در خروجی چاپ کنید (همان‌طور که در جواب نمونه آورده شده). اگر گردآوری دوباره دانه‌ها غیرممکن بود، جمله تعدادی از دانه‌ها احتمالا گم شده است را چاپ کنید. در غیر این صورت N خط که هر کدام با تک دانه‌ای که شرح داده شده برای 1 ? i ? N- 1 را چاپ کنید. دومین عدد int در هر خط باید با اولین int خط بعدی یکی باشد. همچنین در آخرین خط عدد int دومی باید با عدد int خط اول یکی باشد. (یک خط خالی بین دو حالت متوالی جواب‌هایتان چاپ کنید.)

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

2

5

1 2

2 3

3 4

4 5

5 6

5

2 1

2 2

3 4

3 1

2 4

Case #1

some beads may be lost

Case #2

2 1

1 3

3 4

4 2

2 2

اما روش حل مساله! برای حل این مساله ممکن است راه‌های مختلفی وجود داشته باشد ما یکی از راه‌های موجود که با توجه به مساله‌ای که سه هفته پیش مطرح کردیم (یعنی مساله وزیران)، در همان مقاله توضیح دادیم که برای حل مساله از روش پسگرد (BackTracking) استفاده کرده‌ایم یعنی عملی را انجام می‌دهیم تا زمانی که درست باشد، وقتی به یک جواب غلط رسیدیم به حالت درست بعدی که در مرحله قبل وجود دارد بررسی می‌کنیم، بسیار خب از همین روش برای حل این مساله استفاده می‌کنیم.

خب اول یک سری شرط را بررسی می‌کنیم تا ببینیم این مساله با داده‌های بیان شده در صورت مساله حل می‌شود یا نه؟

اولین شرط این است که چون گردنبد به‌صورت حلقه‌ است و اگر مهره‌ای با رنگ آبی-قرمز به عنوان اولین مهره انتخاب شود باید حداقل یک مهره وجود داشته باشد که به‌صورت قرمز-* باشد، یعنی حداقل مهره‌ای وجود داشته باشد که با رنگ قرمز شروع شود (مهره‌ها به‌صورت یک زوج مرتب هستند)، همان‌طور که در روش پسگرد توضیح داده شده است، اول باید یک درخت رسم کنیم، ریشه درخت یکی از مهره‌های ماست که یک زوج مرتب است که به‌صورت «Tuple«int,int تعریف شده، در سطح بعدی باید مهر‌ه‌هایی انتخاب شوند که در شرط زیر صادق باشند:

if (tuple1.Item2 == tuple2.Item1)

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

امیربهاالدین سبط‌الشیخ