Giải Tin học 7 Bài 5 (Cánh diều): Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp
Với soạn, giải bài tập Tin học lớp 7 Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp sách Cánh diều hay nhất, chi tiết sẽ giúp học sinh dễ dàng trả lời câu hỏi và làm bài tập Tin học 7 Bài 5.
Giải Tin học 7 Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp
Bài 1 trang 90 Tin học 7: Cho dãy số ban đầu:
Trả lời:
Dãy số ban đầu:
Mô tả thuật toán tìm kiếm tuần tự một số trong dãy số bằng cách trình bày diễn biến các bước thực hiện dưới bảng:
1. Tìm x = 5
|
Bước |
Thực hiện |
|
1 |
So sánh số ở đầu dãy với x: vì a1 = 8 nên chuyển sang xét số tiếp theo a2 |
|
2 |
So sánh số đang xét với x: vì a2 = 17 nên chuyển sang xét số tiếp theo a3 |
|
3 |
So sánh số đang xét với x: vì a3 = 23 nên chuyển sang xét số tiếp theo a4 |
|
4 |
So sánh số đang xét với x: vì a4 = 1 nên chuyển sang xét số tiếp theo a5 |
|
5 |
So sánh số đang xét với x: vì a5 = 12 nên chuyển sang xét số tiếp theo a6 |
|
6 |
So sánh số đang xét với x: vì a6 = 7 nên chuyển sang xét số tiếp theo a7 |
|
7 |
So sánh số đang xét với x: vì a7 = 5 = x nên kết luận: Tìm thấy x ở vị trí thứ 7 trong dãy, kế thúc thuật toán. |
2. Tìm x = 6
|
Bước |
Thực hiện |
|
1 |
So sánh số ở đầu dãy với x: vì a1 = 8 nên chuyển sang xét số tiếp theo a2 |
|
2 |
So sánh số đang xét với x: vì a2 = 17 nên chuyển sang xét số tiếp theo a3 |
|
3 |
So sánh số đang xét với x: vì a3 = 23 nên chuyển sang xét số tiếp theo a4 |
|
4 |
So sánh số đang xét với x: vì a4 = 1 nên chuyển sang xét số tiếp theo a5 |
|
5 |
So sánh số đang xét với x: vì a5 = 12 nên chuyển sang xét số tiếp theo a6 |
|
6 |
So sánh số đang xét với x: vì a6 = 7 nên chuyển sang xét số tiếp theo a7 |
|
7 |
So sánh số đang xét với x: vì a7 = 5 nên chuyển sang xét số tiếp theo a8 |
|
8 |
So sánh số đang xét với x: vì a8 = 1 nên chuyển sang xét số tiếp theo a9 |
|
9 |
So sánh số đang xét với x: vì a9 = 13 nên chuyển sang xét số tiếp theo a10 |
|
10 |
So sánh số đang xét với x: vì a10 = 10, dãy số kết thúc, kết luận: không tìm thấy x trong dãy số. |
Gợi ý: Dựa theo cách làm trong bài “Sắp xếp chọn”.
Trả lời:
Dãy số ban đầu:
Mô phỏng diễn biến các bước của thuật toán sắp xếp dãy số theo chiều không tăng (sắp xếp chọn):
|
Dãy (a) |
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
A9 |
a10 |
Giải thích |
|
Ban đầu |
8 |
17 |
23 |
1 |
12 |
7 |
5 |
1 |
13 |
10 |
Đổi chỗ 23 với a1 |
|
Sau B1 |
23 |
17 |
8 |
1 |
12 |
7 |
5 |
1 |
13 |
10 |
Đổi chỗ 13 với a3 |
|
Sau B2 |
23 |
17 |
13 |
1 |
12 |
7 |
5 |
1 |
8 |
10 |
Đổi chỗ 12 với a4 |
|
Sau B3 |
23 |
17 |
13 |
12 |
1 |
7 |
5 |
1 |
8 |
10 |
Đổi chỗ 10 với a5 |
|
Sau B4 |
23 |
17 |
13 |
12 |
10 |
7 |
5 |
1 |
8 |
1 |
Đổi chỗ 8 với a6 |
|
Sau B5 |
23 |
17 |
13 |
12 |
10 |
8 |
5 |
1 |
7 |
1 |
Đổi chỗ 7 với a7 |
|
Sau B6 |
23 |
17 |
13 |
12 |
10 |
8 |
7 |
1 |
5 |
1 |
Đổi chỗ 5 với a8 |
|
Kết quả |
23 |
17 |
13 |
12 |
10 |
8 |
7 |
5 |
1 |
1 |
|
Gợi ý: Dựa theo cách làm bài trong bài “Sắp xếp nổi bọt”.
Trả lời:
Dãy số ban đầu:
Mô phỏng diễn biến các bước của thuật toán sắp xếp nổi bọt để sắp xếp dãy số theo chiều không tăng:
1. Tìm x = 5
2. Tìm x = 6
Trả lời:
Tìm kiếm nhị phân trong dãy số sau khi thực hiện Bài 2, Bài 3:
|
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
a10 |
|
23 |
17 |
13 |
12 |
10 |
8 |
7 |
5 |
1 |
1 |
1. Tìm x = 5:
- Chia đôi lần 1: Phạm vi tìm kiếm từ a1 đến a10. Lấy a6 là số có vị trí giữa dãy. Vì x < a6 nên nửa đầu của dãy chắc chắn không có x=5.
- Chia đôi lần 2: Phạm vi tìm kiếm từ a7 đến a10. Lấy a8 là số có vị trí giữa dãy. Vì x = a8 Kết thúc thuật toán với kết quả: Tìm thấy x ở vị trí thứ 8.
2. Tìm x = 6:
- Chia đôi lần 1: Phạm vi tìm kiếm từ a1 đến a10. Lấy a6 là số có vị trí giữa dãy. Vì x < a6 nên nửa đầu của dãy chắc chắn không có x = 6.
- Chia đôi lần 2: Phạm vi tìm kiếm từ a7 đến a10. Lấy a8 là số có vị trí giữa dãy. Vì x < a8 nên nửa sau của dãy chắc chắn không chứa x = 6. Từ a6 đến a8 còn a7 chưa xét, vì x < a7. Kết thúc thuật toán với kết quả: Dãy trên không chứa x = 6.
Vận dụng
Trả lời:
Nếu được yêu cầu sắp xếp một dãy số, em lựa chọn thuật toán sắp xếp chọn hay sắp xếp nổi bọt còn tùy thuộc vào bộ dữ liệu đầu vào. Hai thuật toán này chỉ phù hợp với bộ dữ liệu nhỏ, không phù hợp khi thao tác dữ liệu lớn, tốn thời gian và không tối ưu.
Lý thuyết Tin Học 7 Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp
Bài 1. Cho dãy số ban đầu như sau:
Hãy mô phỏng thuật toán tìm kiếm tuần tự một số trong dãy số bằng cách trình bày diễn biến các bước thực hiện dưới dạng bảng.
a. Tìm x = 5.
b. Tìm x = 6.
Hướng dẫn
a. Tìm x = 5.
|
Bước |
Thực hiện |
|
1 |
So sánh số ở đầu dãy với x: Vì a1 = 8 ≠ x nên chuyển sang xét số tiếp theo a2 trong dãy. |
|
2 |
So sánh số đang xét với x: Vì a2 = 17 ≠ x nên chuyển sang xét số tiếp theo a3 trong dãy. |
|
3 |
So sánh số đang xét với x: Vì a3 = 23 ≠ x nên chuyển sang xét số tiếp theo a4 trong dãy. |
|
4 |
So sánh số đang xét với x: Vì a4 = 1 ≠ x nên chuyển sang xét số tiếp theo a5 trong dãy. |
|
5 |
So sánh số đang xét với x: Vì a5 = 12 ≠ x nên chuyển sang xét số tiếp theo a6 trong dãy. |
|
6 |
So sánh số đang xét với x: Vì a6 = 7 ≠ x nên chuyển sang xét số tiếp theo a7 trong dãy. |
|
7 |
So sánh số đang xét với x: Vì a7 = 5 = x. Kết luận: Tìm thấy x ở vị trí thứ bảy trong dãy; kết thúc thuật toán. |
b. Tìm x = 6.
|
Bước |
Thực hiện |
|
1 |
So sánh số ở đầu dãy với x: Vì a1 = 8 ≠ x nên chuyển sang xét số tiếp theo a2 trong dãy. |
|
2 |
So sánh số đang xét với x: Vì a2 = 17 ≠ x nên chuyển sang xét số tiếp theo a3 trong dãy. |
|
3 |
So sánh số đang xét với x: Vì a3 = 23 ≠ x nên chuyển sang xét số tiếp theo a4 trong dãy. |
|
4 |
So sánh số đang xét với x: Vì a4 = 1 ≠ x nên chuyển sang xét số tiếp theo a5 trong dãy. |
|
5 |
So sánh số đang xét với x: Vì a5 = 12 ≠ x nên chuyển sang xét số tiếp theo a6 trong dãy. |
|
6 |
So sánh số đang xét với x: Vì a6 = 7 ≠ x nên chuyển sang xét số tiếp theo a7 trong dãy. |
|
7 |
So sánh số đang xét với x: Vì a7 = 5 ≠ x nên chuyển sang xét số tiếp theo a8 trong dãy. |
|
8 |
So sánh số đang xét với x: Vì a8 = 1 ≠ x nên chuyển sang xét số tiếp theo a9 trong dãy. |
|
9 |
So sánh số đang xét với x: Vì a9 = 13 ≠ x nên chuyển sang xét số tiếp theo a10 trong dãy. |
|
10 |
So sánh số đang xét với x: Vì a10 = 10 ≠ x nên kết thúc dãy số. Kết luận: Không tìm thấy x = 6 trong dãy; kết thúc thuật toán. |
Bài 2. Cho dãy số ban đầu như Bài 1. Bằng cách trình bày thông tin dưới dạng bảng, hãy mô phỏng diễn biến các bước của thuật toán sắp xếp chọn để sắp xếp dãy số theo chiều không tăng.
Gợi ý: Dựa theo các làm bài trong Bài “Sắp xếp chọn”.
Hướng dẫn
|
Dãy |
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
a10 |
Giải thích |
|
Ban đầu |
8 |
17 |
23 |
1 |
12 |
7 |
5 |
1 |
13 |
10 |
Tiếp theo: đổi chỗ 23 và a1 |
|
Sau B1 |
23 |
17 |
8 |
1 |
12 |
7 |
5 |
1 |
13 |
10 |
Tiếp theo: Không đổi chỗ |
|
Sau B2 |
23 |
17 |
8 |
1 |
12 |
7 |
5 |
1 |
13 |
10 |
Tiếp theo: đổi chỗ 13 và a3 |
|
Sau B3 |
23 |
17 |
13 |
1 |
12 |
7 |
5 |
1 |
8 |
10 |
Tiếp theo: đổi chỗ 12 và a4 |
|
Sau B4 |
23 |
17 |
13 |
12 |
1 |
7 |
5 |
1 |
8 |
10 |
Tiếp theo: đổi chỗ 10 và a5 |
|
Sau B5 |
23 |
17 |
13 |
12 |
10 |
7 |
5 |
1 |
8 |
1 |
Tiếp theo: đổi chỗ 8 và a6 |
|
Sau B6 |
23 |
17 |
13 |
12 |
10 |
8 |
5 |
1 |
7 |
1 |
Tiếp theo: đổi chỗ 7 và a7 |
|
Sau B7 |
23 |
17 |
13 |
12 |
10 |
8 |
7 |
1 |
5 |
1 |
Tiếp theo: đổi chỗ 5 và a8 |
|
Sau B8 |
23 |
17 |
13 |
12 |
10 |
8 |
7 |
5 |
1 |
1 |
Tiếp theo: không đổi chỗ |
|
Sau B9 |
23 |
17 |
13 |
12 |
10 |
8 |
7 |
5 |
1 |
1 |
Tiếp theo: không đổi chỗ |
|
Dãy kết quả |
23 |
17 |
13 |
12 |
10 |
8 |
7 |
5 |
1 |
1 |
|
Bài 3. Cho dãy số ban đầu như Bài 1. Bằng cách trình bày thông tin dưới dạng bảng, hãy mô phỏng diễn biến các bước của thuật toán sắp xếp nổi bọt để sắp xếp dãy số theo chiều không tăng.
Gợi ý: Dựa theo các làm bài trong Bài “Sắp xếp nổi bọt”.
Hướng dẫn
Diễn biến các bước của thuật toán sắp xếp nổi bọt để sắp xếp dãy số theo chiều không tăng là:
Lượt thứ nhất:
Sau đó thực hiện các lượt đổi cho cho đến khi sắp xếp dãy số theo chiều giảm dần.
Bài 4. Hãy mô phỏng thuật toán tìm kiếm nhị phân trong dãy số đã sắp thứ tự là kết quả của Bài 2 và Bài 3.
|
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
a10 |
|
23 |
17 |
13 |
12 |
10 |
8 |
7 |
5 |
1 |
1 |
a. Tìm x = 5.
b. Tìm x = 6.
Hướng dẫn
a. Tìm x = 5.
Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a1 đến a10. Lấy a5 là số có vị trí giữa dãy; Vì x < a5 nên nửa đầu dãy chắc chắn không chứa x = 5, tiếp theo tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a6 đến a10.
Chia đôi lần 2: Phạm vi tìm kiếm là dãy từ a6 đến a10. Lấy a8 là số có vị trí giữa dãy. Vì x = a8 nên kết thúc thuật toán với kết quả: Tìm thấy x ở vị trí thứ tám.
b. Tìm x = 6.
Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a1 đến a10. Lấy a5 là số có vị trí giữa dãy; Vì x < a5 nên nửa đầu dãy chắc chắn không chứa x = 6, tiếp theo tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a6 đến a10.
Chia đôi lần 2: Phạm vi tìm kiếm là dãy từ a6 đến a10. Lấy a8 là số có vị trí giữa dãy. Vì x > a8 nên nửa sau dãy chắc chắn không chứa x = 6, tiếp theo tìm trong nửa đầu của dãy này. Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a5 đến a7.
Chia đôi lần 3: Phạm vi tìm kiếm là dãy từ a5 đến a7. Lấy a6 là số có vị trí giữa dãy. Vì x < a6 nên nửa đầu dãy chắc chắn không chứa x = 6, tiếp theo tìm trong nửa sau của dãy này. Như vậy, phạm vi tìm kiếm tiếp theo là a7.
Phạm vi tìm kiếm chỉ còn một số nhưng không tìm thấy x. Kết thúc thuật toán với kết quả: Không có x trong dãy.
Xem thêm lời giải bài tập Tin học lớp 7 Cánh diều hay, chi tiết khác:
Bài 1: Thiết bị vào - ra cơ bản cho máy tính cá nhân
Bài 3: Thực hành với các thiết bị vào – ra
Bài 4: Một số chức năng của hệ điều hành
Bài 5: Thực hành khám phá trình quản lí hệ thống tệp
Xem thêm Tin học lớp 7 Cánh diều hay, chi tiết khác:
Lý thuyết Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp
Xem thêm các chương trình khác:
- Giải sgk Toán 7 – Cánh Diều
- Giải sbt Toán 7 – Cánh Diều
- Lý thuyết Toán 7 – Cánh Diều
- Giải VBT Toán 7 – Cánh diều
- Soạn văn lớp 7 (hay nhất)– Cánh Diều
- Tác giả tác phẩm Ngữ văn lớp 7 – Cánh Diều
- Tóm tắt tác phẩm Ngữ văn lớp 7 – Cánh Diều
- Bố cục tác phẩm Ngữ văn lớp 7 – Cánh Diều
- Nội dung chính tác phẩm Ngữ văn lớp 7 – Cánh Diều
- Giải sbt Ngữ văn lớp 7 – Cánh Diều
- Văn mẫu lớp 7 – Cánh Diều
- Soạn văn lớp 7 (ngắn nhất) – Cánh Diều
- Giải VBT Ngữ văn lớp 7 – Cánh diều
- Giải sgk Tiếng Anh 7 - Explore English
- Giải sgk Tiếng Anh 7 – ilearn Smart World
- Trọn bộ Từ vựng Tiếng Anh 7 ilearn Smart World đầy đủ nhất
- Ngữ pháp Tiếng Anh 7 i-learn Smart World
- Bài tập Tiếng Anh 7 iLearn Smart World theo Unit có đáp án
- Giải sbt Tiếng Anh 7 - ilearn Smart World
- Giải sgk Lịch sử 7 – Cánh Diều
- Lý thuyết Lịch Sử 7 – Cánh Diều
- Giải sbt Lịch sử 7 – Cánh Diều
- Giải VBT Lịch sử 7 – Cánh diều
- Giải sgk Khoa học tự nhiên 7 – Cánh Diều
- Lý thuyết Khoa học tự nhiên 7 – Cánh Diều
- Giải sbt Khoa học tự nhiên 7 – Cánh Diều
- Giải sgk Địa lí 7 – Cánh Diều
- Lý thuyết Địa Lí 7 – Cánh Diều
- Giải sbt Địa lí 7 – Cánh Diều
- Giải VBT Địa lí 7 – Cánh diều
- Giải sgk Giáo dục công dân 7 – Cánh Diều
- Lý thuyết Giáo dục công dân 7 – Cánh Diều
- Giải sbt Giáo dục công dân 7 – Cánh Diều
- Giải sgk Hoạt động trải nghiệm 7 – Cánh Diều
- Giải sbt Hoạt động trải nghiệm 7 – Cánh Diều
- Giải sgk Công nghệ 7 – Cánh Diều
- Lý thuyết Công nghệ 7 – Cánh Diều
- Giải sbt Công nghệ 7 – Cánh Diều
- Giải sgk Giáo dục thể chất 7 – Cánh Diều
- Giải sgk Âm nhạc 7 – Cánh Diều