معمای ناگت‌های مک‌دونالد

۸ نظر برای معمای ناگت‌های مک‌دونالد

پرطرفدارترین دیدگاه به انتخاب متممی‌ها در این بحث

نویسنده‌ی دیدگاه : محمدرضا شعبانعلی



امیر جان. فکر کنم این روش خوبی که باهاش معما رو حل کردی، بشه با ادبیات الگوریتمی اسمش رو گذاشت greedy-backtracking (ترکیب الگوی حریصانه + عقب‌گرد).

البته در فضای الگوریتمی رایجه که وقتی می‌خوان کسی بهشون گیر نده که نامگذاری دقیق نیست، یه modified هم اولش اضافه می‌کنن. بنابراین میشه بگیم: modified greedy-backtracking.

چون اول خیلی تهاجمی تا آخرین نقطهٔ ممکن میری جلو. به دیوار که خوردی عقب‌گرد می‌کنی. و باز بعدش حملهٔ بعدی رو انجام می‌دی.

یه سوال مشابه دیگه در همین فضا که در بخش جواب معما هم اومده، پیدا کردن عدد فروبنیوسیه. بیکار شدی به اونم فکر کن.

فرض کنیم سه تا سایز بسته رو بهمون داده‌ان (این‌جا ۶ و ۹ و ۲۰) و ازمون می‌پرسن: بزرگ‌ترین عددی که نمیشه با ترکیب این‌ها سفارش داد چنده؟

در مورد ۶ و ۹ و ۲۰ جواب رو می‌دونیم (۴۳).

اما در مورد (۷ و ۱۱ و ۱۷) یا هر مجموعهٔ سه‌تایی دیگه مثلاً (۱۵ و ۲۸ و ۳۵) یا (۸ و ۱۵ و ۷۷) جواب چه‌جوری به دست میاد؟

معمولاً جزو تمرین‌های کلاس برنامه‌نویسی و الگوریتمه. سخت نیست. اما وقتی سخت می‌شه که اصرار داشته باشیم که سریع‌ترین الگوریتم ممکن رو در بیاریم و عددهای پایه هم بزرگ باشن.

 

 
تمرین‌ها و نظرات ثبت شده روی این درس صرفاً برای اعضای متمم نمایش داده می‌شود.
.