Giải Tin học 7 | No tags
Với soạn, giải bài tập Tin học 7 Bài 13: Thuật toán tìm kiếm sách Chân trời sáng tạo hay nhất, ngắn gọn sẽ giúp học sinh lớp 7 trả lời câu hỏi và làm bài tập Tin 7 Bài 13.
Video Giải Tin học 7 Bài 13: Thuật toán tìm kiếm - Cô Anh Thư (Giáo viên VietJack)
Khởi động trang 71 Bài 13 Tin học 7: Có 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ự
Lời giải bài tập Tin học 7 Bài 13: Thực toán tìm kiếm hay khác:
Khám phá 1 trang 72 Tin học 7: Các số ghi trên mỗi thẻ ở Hình 1 lần lượt là: 26, 14, 24, 18, 15, 21, 19, 25, 12. Em hãy tạo Bảng 1 và điền thông tin của mỗi lần lặp để tìm số 21 trong dãy theo thuật toán tìm kiếm tuần tự.
Bảng 1. Tìm số 21 trong dãy số bằng thuật toán tìm kiếm tuần tự
|
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 |
|
… |
… |
… |
… |
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 | |||
Lời giải bài tập Tin học 7 Bài 13: Thực toán tìm kiếm hay khác:
Khám phá 2 trang 72 Tin học 7: Lựa chọn phương án đúng.
Để 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.
Lời giải bài tập Tin học 7 Bài 13: Thực toán tìm kiếm hay khác:
Khám phá trang 74 Tin học 7: 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.
Trả lời:
Các em tham khảo hướng dẫn sau:
a) Chuẩn bị 10 thẻ được đánh số tương ứng 2, 3, 5, 7, 9, 13, 15, 18, 23, 25 xếp sắp theo thứ tự tăng dần. Đặt úp mặt ghi số để không nhìn thấy số ghi trên các thẻ.
b) Thẻ số tăng dần: Tìm số 18
|
Thứ tự |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
Số ghi trên thẻ |
2 |
3 |
5 |
7 |
9 |
13 |
15 |
18 |
23 |
25 |
Hình 2: Thẻ số tăng dần
Gọi số cần tìm là x = 18.
Bước 1. Lật thẻ ở vị trí giữa của dãy (thẻ thứ 5)
Bước 2. So sánh số cần tìm với số ghi trên thẻ số 5 là 9. Do 9 < 18 nên ta chỉ cần tìm ở nữa sau của dãy thẻ (gồm các thẻ thứ 6, 7, 8, 9, 10).
Bước 3. Lật thẻ vị trí ở giữa của nửa sau (thẻ thứ 7)
Bước 4. So sánh số cần tìm với số ghi trên thẻ số 5 là 18. Kết quả tìm thấy số 18 trong dãy ở vị trí thứ 7 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 = 5.
Bước 1. Lật thẻ ở vị trí giữa của dãy (thẻ thứ 5)
Bước 2. So sánh số cần tìm với số ghi trên thẻ số 5 là 9. Do 9 >5 nên ta chỉ cần tìm ở nữa trước của dãy thẻ (gồm các thẻ thứ 1, 2, 3, 4).
Bước 3. Lật thẻ vị trí ở giữa của nửa trước (thẻ thứ 2)
Bước 4. So sánh số cần tìm với số ghi trên thẻ số 2 là 3. Do 3 < 5 nên ta chỉ cần tìm ở nửa sau của dãy thẻ (gồm các thẻ thứ 3, 4).
Bước 5. Lật thẻ ở vị trí giữa của dãy (thẻ thứ 3)
Bước 4. So sánh số cần tìm với số ghi trên thẻ số 3 là 5. Kết quả tìm thấy số 5 trong dãy ở vị trí thứ 3 và kết thúc quá trình tìm kiếm.
Lời giải bài tập Tin học 7 Bài 13: Thực toán tìm kiếm hay khác:
Luyện tập 1 trang 75 Tin học 7: Hãy sử dụng thuật toán tìm kiếm tuần tự để tìm trong lớp em có bạn cùng tháng sinh với em hay không. Có thể sử dụng danh sách lớp có ghi thông tin ngày sinh hoặc hỏi trực tiếp. Lập Bảng 2 vào vở và ghi kết quả thực hiện (dòng 1 là ví dụ minh hoạ).
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. | |||
Lời giải bài tập Tin học 7 Bài 13: Thực toán tìm kiếm hay khác:
Luyện tập 2 trang 75 Tin học 7: Bảng 3 là danh sách hai số đầu biển số xe của một số tỉnh (tên tỉnh đã được sắp xếp theo thứ tự trong bảng chữ cái).
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)
- Lần lặp 1: Lật thẻ ở giữa dãy: Điện Biên. Do Lai Châu đứng sau Điện Biên nên ta tìm ở nửa sau của dãy gồm Gia Lai, Khánh Hoà, Lai Châu, Nam Định, Yên Bái.
- Lần lặp 2: Lật thẻ ở giữa dãy: Lai Châu = Lai Châu nên ta dừng thuật toán ở đây. Hai số đầu của tỉnh Lai Châu là 25
⇒ Có 2 lần lặp được thực hiện.
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) Không thể áp dụng được 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 đó vì danh sách hai số đầu của biển số xe chưa được sắp xếp.
Lời giải bài tập Tin học 7 Bài 13: Thực toán tìm kiếm hay khác:
Vận dụng 1 trang 75 Tin học 7: Em tìm một từ tiếng Anh trong cuốn từ điển theo cách nào? Tại sao em dùng cách đó?
Trả lời:
Các từ trong từ điển được sắp xếp theo thứ tự a, b, c. Do vậy, việc tìm một từ tiếng Anh trong từ điển nên áp dụng tìm kiếm nhị để tìm kiếm nhanh hơn.
Lời giải bài tập Tin học 7 Bài 13: Thực toán tìm kiếm hay khác:
Vận dụng 2 trang 75 Tin học 7: Hãy vận dụng thuật toán tìm kiếm nhị phân để xác định một bạn trong lớp được sinh vào ngày nào trong tháng với không quá 5 câu hỏi trắc nghiệm Đúng/Sai. Tương tự, để xác định một bạn được sinh vào tháng nào trong năm thì em cần dùng nhiều nhất bao nhiêu câu hỏi Đúng/Sai?
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.
Lời giải bài tập Tin học 7 Bài 13: Thực toán tìm kiếm hay khác:
Với tóm tắt lý thuyết Tin học lớp 7 Bài 13: Thuật toán tìm kiếm sách Chân trời sáng tạo hay nhất, ngắn gọn sẽ giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt môn Tin học 7.
Chỉ từ 100k mua trọn bộ lý thuyết Tin 7 Chân trời sáng tạo (cả năm) bản word trình bày đẹp mắt, dễ dàng chỉnh sửa:
Với 12 câu hỏi trắc nghiệm Tin học 7 Bài 13: Thuật toán tìm kiếm sách Chân trời sáng tạo có đáp án chi tiết đầy đủ các mức độ sẽ giúp học sinh ôn luyện trắc nghiệm Tin 7.
Chỉ từ 100k mua trọn bộ trắc nghiệm Tin 7 Chân trời sáng tạo (cả năm) có lời giải chi tiết, bản word trình bày đẹp mắt, dễ dàng chỉnh sửa: