Bài tập Thực toán tìm kiếm có đáp án
Xem toàn bộ quiz

Em và bạn hãy thực hiện trò chơi mô phỏng thuật toán tìm kiếm nhị phân theo hướng dẫn sau

4/8

Em và bạn hãy thực hiện trò chơi mô phỏng thuật toán tìm kiếm nhị phân theo hướng dẫn sau:

a) Chuẩn bị 10 thẻ, mỗi thẻ ghi một số khác nhau. Sắp xếp các thẻ số thành một dãy trên

 mặt bàn theo thứ tự giá trị tăng dần của số ghi trên thẻ. Đặt úp mặt ghi số để không nhìn

 thấy số ghi trên các thẻ.

b) Em đề nghị bạn thực hiện thuật toán tìm kiếm nhị phân để tìm một số do em đưa ra.

c) Hoán đổi vai trò, em thực hiện tìm kiếm theo đề nghị của bạn.

0/3000 ký tự
Giải thích

Các em tham khảo hướng dẫn sau:

Chuẩn bị 10 thẻ được đánh thứ từ từ A, B, C, D, E, F, G, H, K, L và sau thẻ đánh số tương ứng 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 xếp sắp theo thứ tự tăng dần.

a) Thẻ số tăng dần: Tìm số 8

Dãy thẻ số

1

2

3

4

5

6

7

8

9

10

Thứ tự

A

B

C

D

E

F

G

H

K

L

Hình 2: Thẻ số tăng dần

b)

Gọi số cần tìm là x = 8.

Bước 1. Lật thẻ ở vị trí E (E = 5).

Bước 2. So sánh số thấy vị trí E khác vị trí cần tìm (8 > 5) nên ta chỉ cần tìm ở nữa sau của dãy thẻ (gồm F, G, H, K, L).

Bước 3. Lật thẻ vị trí H (H = 8).

Bước 4. So sánh số thấy vị trí H bằng với kết quả cần tìm. Kết quả tìm thấy số 8 trong dãy ở vị trí H và kết thúc quá trình tìm kiếm.

c) Thay đổi vai trò

Gọi số cần tìm là x = 10.

Bước 1. Lật thẻ ở vị trí E (E = 5).

Bước 2. So sánh số thấy vị trí E khác vị trí cần tìm (10 > 5) nên ta chỉ cần tìm ở nữa sau của dãy thẻ (gồm F, G, H, K, L).

Bước 3. Lật thẻ vị trí H (H = 8).

Bước 4. So sánh số thấy vị trí H khác vị trí cần tìm (10 > 8). Nên ta chỉ cần tìm ở nữa sau của dãy thẻ (gồm K, L).

Bước 5. Ta lật ngẫu nhiên vị trí K hoặc L.

+ TH1: Lật thẻ vị trí K: So sánh số thấy vị trí K khác vị trí cần tìm (10 > 9). Tiếp theo ta lật thẻ còn lại, so sánh số thấy vị trí L bằng với kết quả cần tìm. Kết quả tìm thấy số 10 trong dãy ở vị trí L và kết thúc quá trình tìm kiếm.

+ TH2: Lật thẻ vị trí L: So sánh số thấy vị trí L bằng với kết quả cần tìm. Kết quả tìm thấy số 10 trong dãy ở vị trí L và kết thúc quá trình tìm kiếm.