۲۰ امتحان نهایی / مهارت گسسته
انتخاب، شاخه، کنترل

شمارش حالت‌ها؛
فضای انتخاب را پیش از فرمول ببین

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

#احتمال

یک حالت را دقیق تعریف کن

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

مسئلهٔ کوچک‌تر بساز

با تعداد محدود، حالت‌ها را دستی فهرست یا درخت رسم کن. الگوی تکرار، وابستگی انتخاب‌ها و خطر دوباره‌شماری در نمونهٔ کوچک دیده می‌شود و مسیر تعمیم را نشان می‌دهد.

هر شاخه باید یک انتخاب کامل بسازد

درختی که بعضی شاخه‌ها زودتر تمام می‌شوند یا شرط متفاوت دارند، باید برچسب روشن داشته باشد؛ تعداد شاخه‌ها را بی‌دلیل یکسان فرض نکن.

«و» و «یا» را به ساختار تبدیل کن

بررسی کن انتخاب‌ها پشت سر هم انجام می‌شوند یا مسئله به حالت‌های جدا تقسیم شده است. سپس اصل مناسب را مطابق کتابت به کار ببر. واژهٔ متن فقط سرنخ است؛ همپوشانی حالت‌ها را هم کنترل کن.

محدودیت را زود اعمال کن

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

حالت‌بندی را با معیار یکتا انجام بده

یک ویژگی انتخاب کن که هر جواب دقیقاً در یکی از حالت‌ها قرار گیرد. توضیح بده حالت‌ها همدیگر را نمی‌پوشانند و همهٔ امکان‌ها را شامل می‌شوند؛ سپس شمارش هر بخش را جدا بنویس.

تکرار را با برچسب نمونه پیدا کن

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

فرمول را به انتخاب‌ها ترجمه کن

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

جواب را با کران ساده بسنج

نتیجه نباید از تعداد کل حالت‌های بدون محدودیت بیشتر شود. نمونهٔ کوچک و چند حالت مرزی را نیز بررسی کن. برای چارچوب درس از راهنمای گسسته و برای متن مسئله از مدل‌سازی ریاضی استفاده کن.