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