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

Giải Hoạt động 2 trang 77 SGK Tin học 9

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

Đề 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 90°90°), *Rẽ trái* (quay 90°90°) 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 90°90°* 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 90°90°* 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 180°180°* (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 →\rightarrow phía trước →\rightarrow bên trái →\rightarrow 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ố

Thuật toán bám tường phải: ưu tiên rẽ phải → đi thẳng → rẽ trái → quay 180°; lặp lại cho đến khi thoát 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.