جلسهی 6: الگوریتم ۲ Algorithms 2
یک مسئله میتواند چند الگوریتم درست داشته باشد؛ معمولاً آن که قدمهای کمتری دارد بهتر است.
در این جلسه یاد میگیری
- بدانم یک مسئله میتواند چند الگوریتم درست داشته باشد.
- دو الگوریتم را با شمردن قدمهایشان مقایسه کنم.
- قدمهای اضافه را پیدا کنم و الگوریتم را کوتاهتر کنم.
درس
پارسا و امید هر دو از خانه به مدرسه میروند. پارسا از کوچهی پشتی میرود و امید از خیابان اصلی. هر دو میرسند! یک مسئله، دو راهحل.
در برنامهنویسی هم همین است: برای یک مسئله میشود چند الگوریتمِ درست نوشت. پس جواب تو لازم نیست دقیقاً مثل جواب دوستت باشد.
کدام بهتر است؟ قدمها را بشمار. اگر هر دو الگوریتم درست باشند، معمولاً آن که قدمهای کمتری دارد بهتر است: زودتر تمام میشود و جای کمتری برای اشتباه دارد.
برای کوتاه کردن، دنبال قدمهای بیفایده بگرد. ربات اگر «چپ» و بلافاصله «راست» بچرخد، انگار هیچ کاری نکرده است. سه بار «راست» هم همان یک بار «چپ» است!
برای حساب کردن ۵ × ۴ میشود پنج بار ۴ را جمع کرد، یا فقط یک بار ضرب کرد. هر دو ۲۰ میشود، ولی دومی خیلی کوتاهتر است.
اشتباه رایج: فکر کنیم «کوتاهتر» همیشه یعنی «بهتر». اول درست، بعد کوتاه! الگوریتمی که کوتاه است ولی ربات را به دیوار میزند، به هیچ دردی نمیخورد.
چالشها
- Two Ways to School (آسان)
- Straight to the Star (آسان)
- Add or Multiply? (متوسط)
- Around the Wall (متوسط)
- Make It Shorter (سخت)
- The Shortest Program (سخت)