Giải SGK 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| Cánh diều

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 bao gồm đáp án chi tiết cho từng phần, từng mục trong SGK Tin học lớp 7, cho các em học sinh tham khảo luyện giải Tin học 7, chuẩn bị cho các bài học trên lớp được tốt hơn. Sau đây mời các bạn tham khảo chi tiết.

Bài 1 trang 90 Tin học lớp 7:
Cho dãy số ban đầu:
Hãy 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
2. Tìm x = 6
Trả lời:
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: a1 = 8 nên chuyển sang xét số tiếp
theo a2
Quảng cáo
2
So sánh số đang xét với x: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: a10 = 10, dãy số kết thúc, kết luận:
không tìm thấy x trong dãy số.
Bài 2 trang 90 Tin học lớp 7:
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 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.
Gợi ý: Dựa theo cách làm trong bài “Sắp xếp chọn”.
Trả lời:
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
Bài 3 trang 90 Tin học lớp 7:
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 phỏng diễn biến các bước của thuật toán Thực hành phỏng các
thuật toán tìm kiếm, sắp xếp để sắp xếp dãy số theo chiều không tăng.
Gợi ý: Dựa theo cách làm bài trong bài “Thực hành phỏng các thuật toán
tìm kiếm, sắp xếp”.
Trả lời:
ời:
Dãy (a)
a
6
a
7
a
10
Giải thích
Ban
đầu
7
5
10
Tiếp theo so sánh a
1
a
2,
a
2
>
a
2
đổi chổ a
1
a
2
Sau
bước 1
7
5
10
Tiếp theo so sánh a
2
a
3
, a
3
>
a
2
đổi chổ a
2
a
3
Sau
bước 2
7
5
10
Tiếp theo so sánh a
3
a
4
, a
3
>
a
4
giữ nguyên vị trí
Sau
bước 3
7
5
10
Tiếp theo so sánh a
4
a
5
, a
5
>
a
4
đổi chổ a
4
a
5
Sau
bước 4
7
5
10
Tiếp theo so sánh a
5
a
6
, a
6
>
a
5
đổi chổ a
5
a
6
Sau
bước 5
1
5
10
Tiếp theo so sánh a
6
a
7
, a
7
>
a
6
đổi chổ a
6
a
7
Sau
bước 6
5
1
10
Tiếp theo so sánh a
7
a
8
, a
7
=
a
8
giữ nguyên vị trí
Sau
bước 7
5
1
10
Tiếp theo so sánh a
8
a
9
, a
9
>
a
8
đổi chổ a
8
a
9
Sau
bước 8
5
1
10
Tiếp theo so sánh a
9
a
10
, a
10
>
a
9
đổi chổ a
9
a
10
Sau
bước 9
5
1
1
Tiếp theo ta quay lại lại bước 1và
thực hiện vòng lặp tương tự.
Dãy kết
quả
8
7
1
Bài 5 trang 90 Tin học lớp 7:
Hãy phỏng thuật toán tìm kiếm nhị phân trong dãy số đã sắp thứ tự kết
quả của Bài 2 Bài 3.
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 số vị trí giữa dãy.
x < a6 nên nửa đầu của dãy chắc chắn không x=5.
- Chia đôi lần 2: Phạm vi tìm kiếm từ a7 đến a10. Lấy a8 số vị trí giữa dãy.
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 số vị trí giữa dãy.
x < a6 nên nửa đầu của dãy chắc chắn không x = 6.
- Chia đôi lần 2: Phạm vi tìm kiếm từ a7 đến a10. Lấy a8 số vị trí giữa dãy.
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, 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 trang 90 Tin học lớp 7:
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 Thực hành phỏng các thuật toán tìm kiếm, sắp xếp? Giải thích tại sao?
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 Thực hành phỏng các thuật toán tìm kiếm, sắp xếp 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 không tối ưu.
| 1/5

Preview text:

Bài 1 trang 90 Tin học lớp 7:
Cho dãy số ban đầu:
Hãy 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 2. Tìm x = 6 Trả lời:
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 Quảng cáo 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ố.

Bài 2 trang 90 Tin học lớp 7:
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 dãy số theo chiều không tăng.
Gợi ý: Dựa theo cách làm trong bài “Sắp xếp chọn”. Trả lời:
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
Bài 3 trang 90 Tin học lớp 7:
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 Thực hành mô phỏng các
thuật toán tìm kiếm, sắp xếp để sắp xếp dãy số theo chiều không tăng.
Gợi ý: Dựa theo cách làm bài trong bài “Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp”. Trả lời: ời:

Dãy (a) a1 a2 a3 a4 a5 a a a8 a9 a10 Giải thích 6 7 Ban
8 17 23 1 12 7 5 1 13 10 Tiếp theo so sánh a1 và a2, a2> đầu
a2đổi chổ a1 và a2 Sau
17 8 23 1 12 7 5 1 13 10 Tiếp theo so sánh a2 và a3, a3> bước 1
a2đổi chổ a2 và a3 Sau
17 23 8 1 12 7 5 1 13 10 Tiếp theo so sánh a3 và a4, a3> bước 2
a4giữ nguyên vị trí Sau
17 23 8 1 12 7 5 1 13 10 Tiếp theo so sánh a4 và a5, a5> bước 3
a4đổi chổ a4 và a5 Sau
17 23 8 12 1 7 5 1 13 10 Tiếp theo so sánh a5 và a6, a6> bước 4
a5đổi chổ a5 và a6 Sau
17 23 8 12 7 1 5 1 13 10 Tiếp theo so sánh a6 và a7, a7> bước 5
a6đổi chổ a6 và a7 Sau
17 23 8 12 7 5 1 1 13 10 Tiếp theo so sánh a7 và a8, a7= bước 6
a8giữ nguyên vị trí Sau
17 23 8 12 7 5 1 1 13 10 Tiếp theo so sánh a8 và a9, a9> bước 7
a8đổi chổ a8 và a9 Sau
17 23 8 12 7 5 1 13 1 10 Tiếp theo so sánh a9 và a10, a10> bước 8
a9đổi chổ a9 và a10 Sau
17 23 8 12 7 5 1 13 10 1
Tiếp theo ta quay lại lại bước 1và bước 9
thực hiện vòng lặp tương tự.
Dãy kết 23 17 13 12 10 8 7 5 1 1 quả
Bài 5 trang 90 Tin học lớp 7:
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. 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 trang 90 Tin học lớp 7:
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 Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp? Giải thích tại sao? 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 Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp 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.