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

جلسه‌ی 18: فرایندها و الگوریتم‌ها Procedures and Algorithms

در المپیاد بدون کد، الگوریتم را با کلمه‌ها می‌نویسند: قدم‌به‌قدم اجرا کن، جدولِ مقدارها را نگه دار، و دنبال میان‌بُر و چیزی که ثابت می‌ماند بگرد.

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

درس

الگوریتم یعنی دستورهای دقیق و قدم‌به‌قدم. در سؤال‌های المپیاد، الگوریتم را با کلمه یا شماره‌ی مرحله می‌نویسند. بهترین ابزار یک جدول است: هر سطر یک قدم، هر ستون یک متغیر. مثال:
۱. x را ۱ قرار بده.
۲. چهار بار انجام بده: x را برابرِ ⁦۲x + ۱⁩ قرار بده.
۳. x را چاپ کن.
جدول: ⁦۱ ← ۳ ← ۷ ← ۱۵ ← ۳۱⁩. چاپ می‌شود ۳۱.

حلقه‌های تودرتو: «برای i از ۱ تا ۴: برای j از ۱ تا i: s را یکی زیاد کن» یعنی s روی هم ⁦۱ + ۲ + ۳ + ۴ = ۱۰⁩ بار زیاد می‌شود. به‌جای اجرای تک‌تک، بپرس: «هر چیز چند بار شمرده می‌شود؟» این همان ترفندِ شمارش است.

تمام می‌شود یا نه؟ «تا وقتی a و b برابر نیستند، بزرگ‌تر را منهای کوچک‌تر کن» همیشه تمام می‌شود، چون عددها مثبت می‌مانند و جمعشان هر بار کم می‌شود. و جوابش بزرگ‌ترین مقسوم‌علیه مشترک (ب.م.م) است: (۸۴، ۳۶) ← (۴۸، ۳۶) ← (۱۲، ۳۶) ← (۱۲، ۲۴) ← (۱۲، ۱۲): ۴ قدم، جواب ۱۲.
برای این‌که ثابت کنی یک فرایند تمام می‌شود، دنبال عددی بگرد که هر قدم کم می‌شود ولی نمی‌تواند تا ابد کم شود.

اشتباه رایج: یک قدم را جا انداختن یا یک قدم را دو بار حساب کردن. وقتی حلقه «تا وقتی» دارد، شرط را «قبل از» هر دور چک کن؛ و حواست باشد شمارش از ۰ شروع می‌شود یا ۱.

چالش‌ها

  1. Doubling Plus One (آسان)
  2. Adding the Odd Ones (آسان)
  3. Subtract Until Equal (متوسط)
  4. Half or Triple Plus One (متوسط)
  5. When Does It Stop? (سخت)
  6. Jumping Through a List (سخت)

← جلسه‌ی 17: تقارن و جفت‌سازی جلسه‌ی 19: ترازو و وزن کردن →