Sách giáo khoa Tin học 9

Giải Luyện tập trang 78 SGK Tin học 9

Bài 14. Giải quyết vấn đề   Đã kiểm chéo

Đề bài

Em hãy mô tả thuật toán bám tường bên trái để tìm đường thoát khỏi mê cung.

Lời giải

Phân tích bài toán (thuật toán bám tường bên trái)

- Đầu vào: Một mê cung có lối vào và lối ra; người (hoặc rô-bốt) đang đứng ở vị trí xuất phát và quay mặt về một hướng.
- Đầu ra: Đường đi từ lối vào đến lối ra.
- Ý tưởng: Luôn luôn giữ bàn tay trái áp sát vào tường bên trái và cứ thế đi dọc theo tường. Nhờ không bao giờ rời tay khỏi tường, ta sẽ lần theo toàn bộ mặt tường đó và chắc chắn đi tới lối ra (với mê cung mà các bức tường nối liền thành một khối, không có "ốc đảo" tường tách rời ở giữa).

Mô tả thuật toán (các bước thực hiện)

1. Bắt đầu: đứng ở lối vào, áp bàn tay trái lên bức tường bên trái.
2. Xét tình huống tại vị trí hiện tại và xử lí theo thứ tự ưu tiên sau:
- Bước 1 — Ưu tiên rẽ trái: Nếu bên trái không có tường (có lối đi) thì rẽ trái rồi bước lên một bước.
- Bước 2 — Nếu không rẽ trái được: Nếu phía trước không có tường thì đi thẳng lên một bước.
- Bước 3 — Nếu phía trước cũng có tường: rẽ phải (quay sang phải) rồi quay lại xét từ Bước 1. Trường hợp cả trái, trước và phải đều bị tường chặn (ngõ cụt) thì quay ngược lại 180° và đi ra.
3. Lặp lại bước 2 cho đến khi tới được lối ra thì dừng.

Lưu ý: Mấu chốt của thuật toán là *luôn bám lấy tường bên trái*, tức là ở mỗi ô luôn thử rẽ trái trước, rồi mới đi thẳng, rồi mới rẽ phải. Cách làm này giúp ta đi men theo đúng một mặt tường liên tục nên không bị đi vòng lặp vô tận và sẽ tìm được đường thoát. (Nếu đổi thành luôn giữ tay phải áp tường thì ta có thuật toán *bám tường bên phải*, cũng cho kết quả tương tự.)

Đáp số

Luôn giữ tay trái áp sát tường, mỗi bước ưu tiên: rẽ trái → đi thẳng → rẽ phải (ngõ cụt thì quay lại), lặp cho tới khi ra khỏi mê cung

Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.