Xem toàn bộ tài liệu Lớp 7 – Chân Trời Sáng Tạo: tại đây

Bài 13 Tin học lớp 7: Ccó 9 thẻ số, mỗi thẻ được ghi số ở một mặt và mặt còn lại không ghi gì. Đặt úp các thẻ số trên mặt bàn và xếp thành một dãy như Hình 1.

Hình 1: Các thẻ được ghi số ở mặt úp

Em hãy trao đổi với bạn để thực hiện tìm một số bất kì có trong dãy số ghi trên các thẻ ở Hình 1 hay không.

Trả lời:

Em có thể tìm một thẻ bất kì theo yêu cầu trong dãy số trên (Hình 1) bằng cách lặt từng thẻ số.

1. Thuật toán tìm kiếm tuần tự

Khám phá 1 trang 72 Tin học lớp 7:

Trả lời:

Lần lặp	Số ghi trên thẻ	Đúng số cần tìm?	Đã hết số thẻ
1	26	Sai	Sai
2	14	Sai	Sai
3	24	Sai	Sai
4	18	Sai	Sai
5	15	Sai	Sai
6	21	Đúng	Sai
Vậy khi lặp lần thứ 6 ta đã tìm được số cần tìm. Kết thúc quá trình tìm kiếm

Khám phá 2 trang 72 Tin học lớp 7:

Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, ta thực hiện:

A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.

B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.

C. Sắp xếp dãy số theo thứ tự tăng dần.

D. So sánh số cần tìm với số ở giữa dãy số.

Trả lời:

Đáp án: B

Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, ta thực hiện so sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.

Khám phá trang 74 Tin học lớp 7:

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.

Trả lời:

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.

Luyện tập 1 trang 75 Tin học lớp 7:

Trả lời:

Giả sử tháng sinh của em là tháng 3. Em sẽ đi hỏi tháng sinh của các bạn và ghi vào bảng thống kê:

Lần lặp	Tháng sinh của bạn	Cùng tháng sinh với em	Đã hết danh sách/ đã hỏi hết các bạn
1	4	Sai	Sai
2	2	Sai	Sai
3	1	Sai	Sai
4	5	Sai	Sai
5	6	Sai	Sai
6	8	Sai	Sai
7	12	Sai	Sai
8	11	Sai	Sai
9	3	Đúng	Sai
Sau lần lặp thứ 9 đã có bạn cùng tháng sinh với em. Kết thúc tìm kiếm.

Luyện tập 2 trang 75 Tin học lớp 7:

a) Áp dụng thuật toán tìm kiếm tuần tự để tìm ra tỉnh có hai số đầu của biển số xe là 25. Cho biết em đã thực hiện bao nhiêu lần lặp.

b) Áp dụng thuật toán tìm kiếm nhị phân để tìm hai số đầu tiên của biển số xe của tỉnh Lai Châu. Cho biết em đã thực hiện bao nhiêu lần lặp.

c) Số lần lặp em thực hiện ở câu a ít hơn hay ở câu b ít hơn? Tại sao?

d) Có thể áp dụng thuật toán tìm kiếm nhị phân để tìm ra tỉnh khi biết hai số đầu của biển

  số xe của tỉnh đó hay không? Tại sao?

Trả lời:

a)  Biển số xe cần tìm là 25.

Lần lặp	Biển số xe tỉnh	Cùng biển số xe	Danh sách tìm kết toàn bộ bảng
1	67	Sai	Sai
2	72	Sai	Sai
3	77	Sai	Sai
4	69	Sai	Sai
5	27	Sai	Sai
6	81	Sai	Sai
7	79	Sai	Sai
8	25	Đúng	Sai
Sau 8 lần lặp đã tìm được kết quả. Kết thúc tìm kiếm.

b) 

Bước 1. Sắp xếp biển số xe theo thứ tự tăng dần hoặc giảm dần.

Bảng. Biển số xe tăng dần

Bước 2.  Lật thẻ số ở giữa của dãy (thẻ thứ 5). So sánh số cần tìm là 25 trên thẻ vừa lật là 67. Do 25 < 67 nên chỉ cần tìm ở nửa đầu của dãy thẻ (gồm 1, 2, 3, 4) 

Bước 4. Lật thẻ số ở giữa của dãy (thẻ thứ 2). So sánh số cần tìm là 25 trên thẻ vừa lật là 21. Do 25 > 21 nên số cần tìm ở nửa sau của dãy thẻ (vị trí số 3, 4).

Bước 5. Lật thẻ vị trí số 3. So sánh số cần tìm là 25 trên thẻ vừa lật là 25. Do 25 = 25 nên đưa ra thông báo đã tìm thấy kết quả. Kết thúc quá trình tìm kiếm.

c) Số lần lặp lại ở câu b ít hơn câu a. Vì tìm kiếm nhị phân chia nhỏ mảng tìm kiếm nên số lần lặp ít hơn.

d) Ta có thể dùng thuật toán tìm kiếm nhị phân để tìm ra tỉnh khi biết hai số đầu của biển số xe. Vì khi thực hiện tìm kiếm ta sẽ chia nhỏ mảng số và tìm được số cần tìm.

Vận dụng 1 trang 75 Tin học lớp 7:

Trả lời:

Các bước tra từ điển:

Bước 1. Sắp xếp từ ngữ theo thứ tự tăng dần theo bảng chữ cái.

Bước 2. Chọn chữ cái bắt đầu của từ tiếng anh để tìm kiếm.

Bước 3. Chia nhỏ danh sách tìm kiếm và tìm chữ tiếng anh.

Vì: Khi thực hiện cách này giúp cho quá trình tìm kiếm nhanh hơn.

Vận dụng 2 trang 75 Tin học lớp 7:

Trả lời:

Câu hỏi đặt ra cho bạn để xác định ngày sinh trong tháng:

Ví dụ: Bạn của em sinh ngày 5. (Em sẽ sử dụng câu hỏi đúng hoặc sai vào từng lựa chọn Lớn hơn hay Nhỏ hơn).

Câu hỏi 1: Bạn sinh vào ngày nhỏ hơn 15 (hay lớn hơn 15). 

Câu hỏi 2: Ngày sinh của bạn nhỏ hơn 7 (hay lớn hơn 7). 

Câu hỏi 3: Ngày sinh của bạn nhỏ hơn 4 (hay lớn hơn 4).

Câu hỏi 4: Ngày sinh của bạn bằng 5 hay lớn hơn 5. Khi đó ta sẽ được kết quả.

Tương tự: Để xác định bạn sinh vào tháng nào trong năm em sẽ dùng 4 câu hỏi đúng sai.