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

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 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:

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ố.

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:

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

 

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 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á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:

                           

                            

Bài 4 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ừ a₁ đến a₁₀. Lấy a₆ là số có vị trí giữa dãy. Vì x < a₆ 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ừ a₇ đến a₁₀. Lấy a₈ là số có vị trí giữa dãy. Vì x = a₈  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ừ a₁ đến a₁₀. Lấy a₆ là số có vị trí giữa dãy. Vì x < a₆ 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ừ a₇ đến a₁₀. Lấy a₈ là số có vị trí giữa dãy. Vì x < a₈ nên nửa sau của dãy chắc chắn không chứa x = 6. Từ a₆ đến a₈ còn a₇ chưa xét, vì x < a₇. 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

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 sắp xếp nổi bọt? 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 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.

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 2: Các thiết bị vào

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