جلسهی 18: فرایندها و الگوریتمها Procedures and Algorithms
در المپیاد بدون کد، الگوریتم را با کلمهها مینویسند: قدمبهقدم اجرا کن، جدولِ مقدارها را نگه دار، و دنبال میانبُر و چیزی که ثابت میماند بگرد.
در این جلسه یاد میگیری
- یک الگوریتمِ نوشتهشده با کلمه را قدمبهقدم و با جدول اجرا میکنی.
- تعداد دفعههای تکرارِ یک حلقه را بدون اجرای تکتک حساب میکنی.
- میفهمی یک فرایند کِی تمام میشود و کِی تا ابد ادامه پیدا میکند.
درس
الگوریتم یعنی دستورهای دقیق و قدمبهقدم. در سؤالهای المپیاد، الگوریتم را با کلمه یا شمارهی مرحله مینویسند. بهترین ابزار یک جدول است: هر سطر یک قدم، هر ستون یک متغیر. مثال:
۱. x را ۱ قرار بده.
۲. چهار بار انجام بده: x را برابرِ ۲x + ۱ قرار بده.
۳. x را چاپ کن.
جدول: ۱ ← ۳ ← ۷ ← ۱۵ ← ۳۱. چاپ میشود ۳۱.
حلقههای تودرتو: «برای i از ۱ تا ۴: برای j از ۱ تا i: s را یکی زیاد کن» یعنی s روی هم ۱ + ۲ + ۳ + ۴ = ۱۰ بار زیاد میشود. بهجای اجرای تکتک، بپرس: «هر چیز چند بار شمرده میشود؟» این همان ترفندِ شمارش است.
تمام میشود یا نه؟ «تا وقتی a و b برابر نیستند، بزرگتر را منهای کوچکتر کن» همیشه تمام میشود، چون عددها مثبت میمانند و جمعشان هر بار کم میشود. و جوابش بزرگترین مقسومعلیه مشترک (ب.م.م) است: (۸۴، ۳۶) ← (۴۸، ۳۶) ← (۱۲، ۳۶) ← (۱۲، ۲۴) ← (۱۲، ۱۲): ۴ قدم، جواب ۱۲.
برای اینکه ثابت کنی یک فرایند تمام میشود، دنبال عددی بگرد که هر قدم کم میشود ولی نمیتواند تا ابد کم شود.
اشتباه رایج: یک قدم را جا انداختن یا یک قدم را دو بار حساب کردن. وقتی حلقه «تا وقتی» دارد، شرط را «قبل از» هر دور چک کن؛ و حواست باشد شمارش از ۰ شروع میشود یا ۱.
چالشها
- Doubling Plus One (آسان)
- Adding the Odd Ones (آسان)
- Subtract Until Equal (متوسط)
- Half or Triple Plus One (متوسط)
- When Does It Stop? (سخت)
- Jumping Through a List (سخت)