بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 13: استقرا: از کوچک به بزرگ Induction and Step-by-Step Counting

اگر مسئله‌ی کوچک را بلدی و می‌دانی چطور از هر اندازه به اندازه‌ی بعدی بروی، همه‌ی اندازه‌ها را بلدی. برج هانوی، کاشی‌کاریِ نوارها، و خط‌هایی که صفحه را می‌بُرند.

در این جلسه یاد می‌گیری

درس

برج هانوی: همه‌ی حلقه‌ها را از میله‌ی اول به میله‌ی آخر ببر. هر بار فقط یک حلقه، و هیچ‌وقت حلقه‌ی بزرگ روی کوچک. با ۳ حلقه کمترین تعداد حرکت چند است؟

فکر استقرایی: برای جابه‌جا کردنِ n حلقه، باید ⁦n − ۱⁩ حلقه‌ی بالایی را کنار بگذاری (روی میله‌ی وسط)، بزرگ‌ترین را ببری، و آن ⁦n − ۱⁩ حلقه را دوباره رویش بگذاری. اگر ⁦T(n)⁩ کمترین تعداد حرکت باشد:
⁦T(n) = T(n − ۱) + ۱ + T(n − ۱) = ۲T(n − ۱) + ۱⁩
⁦T(۱) = ۱⁩، ⁦T(۲) = ۳⁩، ⁦T(۳) = ۷⁩، ⁦T(۴) = ۱۵ …⁩ یعنی ⁦۲ⁿ − ۱⁩.

استقرا مثل یک ردیف دومینوست: ۱) پایه: دومینوی اول می‌افتد (حالت کوچک درست است). ۲) قدم: هر دومینو که بیفتد، بعدی را می‌اندازد (اگر برای n درست باشد، برای ⁦n + ۱⁩ هم درست است). پس همه می‌افتند! در مرحله‌ی اول معمولاً کافی است الگو را پیدا کنی؛ در مرحله‌ی دوم باید پایه و قدم را بنویسی (فاز ۵).

کاشی‌کاریِ نوار: یک نوارِ ⁦۲ × n⁩ را با دومینو بپوش. به ستون آخر نگاه کن: یا یک دومینوی ایستاده آن را پر کرده (بقیه یک نوار ⁦۲ × (n − ۱)⁩ است)، یا دو دومینوی خوابیده دو ستون آخر را پر کرده‌اند (بقیه ⁦۲ × (n − ۲)⁩). پس:
⁦a(n) = a(n − ۱) + a(n − ۲)⁩
⁦a(۱) = ۱⁩، ⁦a(۲) = ۲⁩، ⁦a(۳) = ۳⁩، ⁦a(۴) = ۵ …⁩ همان فیبوناچیِ قورباغه! صفحه‌ی ⁦۲ × ۴⁩ را امتحان کن:

یک الگوی معروف دیگر: n خط در صفحه که هیچ دو تایی موازی نیستند و هیچ سه تایی از یک نقطه نمی‌گذرند. خط n‌ام با ⁦n − ۱⁩ خطِ قبلی برخورد دارد، پس از n ناحیه رد می‌شود و هر کدام را دو تکه می‌کند: n ناحیه‌ی تازه.
⁦R(n) = R(n − ۱) + n⁩، با ⁦R(۰) = ۱⁩. پس ⁦R(n) = ۱ + (۱ + ۲ + … + n)⁩.
اشتباه رایج: از روی ۳ عدد اول حدس زدن بدون فهمیدنِ «چرا». مثلاً ۱، ۲، ۴ را ببینی و بگویی بعدی ۸ است، در حالی که ⁦R(۳) = ۷⁩.

چالش‌ها

  1. Four Disks (آسان)
  2. A 2 by 5 Strip (آسان)
  3. Five Lines (متوسط)
  4. No Two Neighbours (متوسط)
  5. Hanoi with a Rule (سخت)
  6. Dominoes and Squares (سخت)

← جلسه‌ی 12: رنگ‌آمیزی: یک استدلالِ رنگی جلسه‌ی 14: راستگوها و دروغگوها →