Giải Hoạt động 2 trang 77 SGK Tin học 9
Đề bài
Thuật toán bám tường
Thuật toán bám tường là một trong những giải pháp thoát khỏi mê cung. Trong thuật toán, robot di chuyển sao cho bức tường luôn ở một phía của nó (chẳng hạn phía bên phải). Em hãy mô tả thuật toán xác định hướng di chuyển của robot. Biết rằng robot chỉ thực hiện được những động tác sau:
Lời giải
## Thuật toán bám tường (bám tường bên phải)
Phân tích: Robot thoát mê cung bằng cách luôn giữ bức tường ở phía bên phải của mình. Muốn vậy, tại mỗi ô robot *ưu tiên áp sát về bên phải nhất có thể*: nếu rẽ phải được thì rẽ phải, không thì đi thẳng, không thì rẽ trái, cùng đường thì quay lại. Cứ đi theo quy tắc này thì robot men hết một mặt tường và cuối cùng ra tới lối thoát.
Giả sử robot làm được các động tác: *Tiến một ô*, *Rẽ phải* (quay ), *Rẽ trái* (quay ) và *Kiểm tra* xem phía trước / bên phải / bên trái có tường hay không.
Mô tả thuật toán (lặp lại cho đến khi robot ra khỏi mê cung):
- Bước 1 — Xét bên phải. Nếu bên phải không có tường thì: *Rẽ phải * rồi *Tiến một ô*; quay lại Bước 1.
- Bước 2 — Xét phía trước (khi bên phải đã có tường). Nếu phía trước không có tường thì: *Tiến một ô* (giữ nguyên hướng); quay lại Bước 1.
- Bước 3 — Xét bên trái (khi phải và trước đều có tường). Nếu bên trái không có tường thì: *Rẽ trái * rồi *Tiến một ô*; quay lại Bước 1.
- Bước 4 — Ngõ cụt (cả ba phía đều có tường). *Quay * (rẽ phải hai lần) để đi ngược lại; quay lại Bước 1.
Sơ đồ (giả mã):
```
Lặp cho đến khi ra khỏi mê cung:
Nếu bên phải trống thì: Rẽ phải → Tiến
Ngược lại nếu phía trước trống thì: Tiến
Ngược lại nếu bên trái trống thì: Rẽ trái → Tiến
Ngược lại: Quay 180°
```
Thứ tự ưu tiên: bên phải phía trước bên trái quay lui.
Giải thích tính đúng: Việc luôn xét bên phải trước (Bước 1) bảo đảm tường không bao giờ "tuột" khỏi phía phải của robot; khi đang có tường bám thì robot đi dọc theo nó (Bước 2); gặp góc thì rẽ trái để vòng theo tường (Bước 3); gặp ngõ cụt thì quay lại (Bước 4). Nhờ kiên trì bám một phía của tường, với mê cung mà các bức tường nối liền và lối ra thông với tường bên phải, robot chắc chắn men hết tường và thoát ra ngoài.
Đáp số
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.