برنامه‌نویسیایستگاه ۹ از ۳۰
جستجو: بازی حدس عدد · برنامه‌نویسی، ایستگاه ۹
پرسشی که ایستگاه با آن شروع می‌شود
چطور می‌شود با فقط ۲۰ سؤالِ بله/خیر یک نفر را بینِ یک میلیون نفر پیدا کرد؟
معمولاً پایهٔ پنجمحدود ۵۳ دقیقه در ۳ جلسهٔ کوتاه
سرعت را تسلط تعیین می‌کند، نه سن.
فرزندتان در این ایستگاه چه یاد می‌گیرد
- جستجوی خطی
- جستجوی دودویی
- چرا نصف‌کردن این‌قدر قوی است
- تعداد سؤال‌ها و لگاریتم (کیفی)
درس‌های این ایستگاه
- یکی‌یکی گشتن: جستجوی خطی (حدود ۱۵ دقیقه)
- حدسِ وسط: جستجوی دودویی (حدود ۲۰ دقیقه)
- چرا نصف کردن این‌قدر قوی است؟ (حدود ۱۸ دقیقه)
ایده‌های کلیدی
جستجوی خطی و بدترین حالت
یکی‌یکی نگاه کن؛ روی هر فهرستی کار می‌کند. بدترین حالت = همه‌شان، حتی وقتی عدد اصلاً نیست.حدسِ وسط
(کوچک‌ترین ممکن + بزرگ‌ترین ممکن) ÷ ۲، رو به پایین. هر جواب نصف را کنار می‌گذارد؛ ولی فقط در فهرستِ مرتب.دو برابر و یکی بیشتر
با ۱، ۲، ۳، … حدس: ۱، ۳، ۷، ۱۵، ۳۱، ۶۳، ۱۲۷ عدد. ۱ تا ۱۰۰ ← ۷ حدس. بازه دو برابر شد؟ فقط یک حدس بیشتر.سؤالِ بله/خیر
وقتی فقط باید بفهمی کدام است: ۲، ۴، ۸، …. بیست سؤالِ نصف‌کن برای بیش از یک میلیون کافی است.
از درس‌های همین ایستگاه
یک مثال حل‌شده
همان‌طور که در درس دیده می‌شود، این‌جا با همهٔ قدم‌ها.
مسئله
دفترِ رضا ۳۲ صفحهٔ شماره‌دار دارد. خواهرِ کوچکش از یک صفحه به بعد، روی همهٔ صفحه‌ها ستاره کشیده؛ صفحه‌های قبل از آن ستاره ندارند. رضا اولین صفحهٔ ستاره‌دار را با کمترین ورق زدن پیدا می‌کند: هر بار صفحهٔ وسطِ بخشِ ممکن را باز می‌کند. اگر اولین صفحهٔ ستاره‌دار ۲۳ باشد، رضا کدام صفحه‌ها را به ترتیب باز می‌کند؟راه‌حل، قدم‌به‌قدم
در درس، قدم‌ها یکی‌یکی باز می‌شوند و فرزندتان پیش از هر قدم خودش حدس می‌زند.
- قدم ۱: فرقش با بازیِ حدسِ عدد: این‌جا جواب فقط «ستاره دارد» یا «ندارد» است. اگر صفحه‌ای ستاره داشت، اولین صفحهٔ ستاره‌دار همان است یا قبل از آن؛ اگر نداشت، بعد از آن است.
- قدم ۲: بخشِ ممکن ۱ تا ۳۲. وسط: (۱ + ۳۲) ÷ ۲ = ۱۶ و نیم ← ۱۶. ستاره ندارد، پس بخش می‌شود ۱۷ تا ۳۲.
- قدم ۳: وسط: (۱۷ + ۳۲) ÷ ۲ = ۲۴ و نیم ← ۲۴. ستاره دارد! ولی شاید اولی نباشد، پس ۲۴ در بخش می‌ماند: ۱۷ تا ۲۴.
- قدم ۴: وسط ۲۰: ندارد؛ بخش ۲۱ تا ۲۴. وسط ۲۲: ندارد؛ بخش ۲۳ تا ۲۴. وسط ۲۳: دارد؛ بخش ۲۳ تا ۲۳.
- قدم ۵: بخش یک صفحه شد: جواب ۲۳. رضا ۵ صفحه باز کرد: ۱۶، ۲۴، ۲۰، ۲۲ و ۲۳. اگر از صفحهٔ ۱ یکی‌یکی ورق می‌زد، ۲۳ صفحه را می‌دید. نکته: دیدنِ یک ستاره کار را تمام نمی‌کند؛ کار وقتی تمام است که بخشِ ممکن یک صفحه شود.
یک نمونهٔ کوچک
ابزار این ایستگاه را امتحان کنید
از درس «یکی‌یکی گشتن: جستجوی خطی»
نمونه در حال آماده شدن است…
پیش و پس از این ایستگاه
پیش‌نیازها
ایستگاه‌هایی که به این تکیه می‌کنند
- ایستگاه ۱۰: پشته، صف و معماهای بیبراس
- هوش مصنوعی،ایستگاه ۹: عامل هوشمند: هدف، نقشه، ابزار، بررسی
روش یادگیری فکرستان و همهٔ ایستگاه‌های این مسیر: برنامه‌نویسی برای کودکان
شروع با فکرستان
حساب را پدر یا مادر می‌سازد و رضایتش را همان‌جا ثبت می‌کند. فرزندتان با نام مستعار وارد می‌شود و با چند پرسش کوتاه، نقطهٔ شروعِ هر مسیر پیدا می‌شود.