Bài 5. Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp

Thực hành mô phỏng thuật toán tìm kiếm, sắp xếp trang 90 SGK Tin Học lớp 7 – Cánh Diều, mời các em tham khảo cùng Bumbii.

Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính. 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

a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀
8	17	23	1	12	7	5	1	13	10

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.

1) Tìm x = 5;

2) Tìm x = 6.

Đáp án: Mô phỏng thuật toán tìm kiếm tuần tự

1) Tìm x = 5;

Dãy xuất phát

a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀
8	17	23	1	12	7	5	1	13	10

Tìm x = 5. Các bước thực hiện tìm kiếm như sau:

Bước	Thực hiện
1	So sánh số ở đầu với x: Vì a₁ = 8 ≠ x nên chuyển sang xét số tiếp theo a₂ trong dãy
2	So sánh số đang xét với x: Vì a₂ = 17 ≠ x nên chuyển sang xét số tiếp theo a₃ trong dãy
3	So sánh số đang xét với x: Vì a₃ = 23 ≠ x nên chuyển sang xét số tiếp theo a₄ trong dãy
4	So sánh số đang xét với x: Vì a₄ = 1 ≠ x nên chuyển sang xét số tiếp theo a₅ trong dãy
5	So sánh số đang xét với x: Vì a₅ = 12 ≠ x nên chuyển sang xét số tiếp theo a₆ trong dãy
6	So sánh số đang xét với x: Vì a₆ = 7 ≠ x nên chuyển sang xét số tiếp theo a₇ trong dãy
7	So sánh số đang xét với x: Vì a₇ = 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.

2) Tìm x = 6.

Dãy xuất phát

a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀
8	17	23	1	12	7	5	1	13	10

Tìm x = 5. Các bước thực hiện tìm kiếm như sau:

Bước	Thực hiện
1	So sánh số ở đầu với x: Vì a₁ = 8 ≠ x nên chuyển sang xét số tiếp theo a₂ trong dãy
2	So sánh số đang xét với x: Vì a₂ = 17 ≠ x nên chuyển sang xét số tiếp theo a₃ trong dãy
3	So sánh số đang xét với x: Vì a₃ = 23 ≠ x nên chuyển sang xét số tiếp theo a₄ trong dãy
4	So sánh số đang xét với x: Vì a₄ = 1 ≠ x nên chuyển sang xét số tiếp theo a₅ trong dãy
5	So sánh số đang xét với x: Vì a₅ = 12 ≠ x nên chuyển sang xét số tiếp theo a₆ trong dãy
6	So sánh số đang xét với x: Vì a₆ = 7 ≠ x nên chuyển sang xét số tiếp theo a₇ trong dãy
7	So sánh số đang xét với x: Vì a₇ = 5 ≠ x nên chuyển sang xét số tiếp theo a₈ trong dãy
8	So sánh số đang xét với x: Vì a₈ = 1 ≠ x nên chuyển sang xét số tiếp theo a₉ trong dãy
9	So sánh số đang xét với x: Vì a₉ = 13 ≠ x nên chuyển sang xét số tiếp theo a₁₀ trong dãy
10	So sánh số cuối dãy với x: Vì a₁₀ = 10 ≠ x Kết luận: Không tìm thấy x ở trong dãy; kết thúc thuật toán.

Bài 2

Cho dãy số ban đầu như trong 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 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ách làm trong Bài “Sắp xếp chọn”.

Đáp án:

Dãy (a)	a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀	Giải thích
Ban đầu	8	17	23	1	12	7	5	1	13	10	Tiếp theo: đổi chỗ 23 và a₁.
Sau bước 1	23	17	8	1	12	7	5	1	13	10	Tiếp theo: không đổi chỗ
Sau bước 2	23	17	8	1	12	7	5	1	13	10	Tiếp theo: đổi chỗ 13 và a₃.
Sau bước 3	23	17	13	1	12	7	5	1	8	10	Tiếp theo: đổi chỗ 12 và a₄.
Sau bước 4	23	17	13	12	1	7	5	1	8	10	Tiếp theo: đổi chỗ 10 và a₅.
Sau bước 5	23	17	13	12	10	7	5	1	8	1	Tiếp theo: đổi chỗ 8 và a₆.
Sau bước 6	23	17	13	12	10	8	5	1	7	1	Tiếp theo: đổi chỗ 7 và a₇.
Sau bước 7	23	17	13	12	10	8	7	1	5	1	Tiếp theo: đổi chỗ 5 và a₈.
Sau bước 8	23	17	13	12	10	8	7	5	1	1	Tiếp theo: Không đổi chỗ
Sau bước 9	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ư trong 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 trong Bài “Sắp xếp nổi bọt”.

Đáp án:

Lượt thứ nhất:

a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀	Giải thích
8	17	23	1	12	7	5	1	13	10
8	17	23	1	12	7	5	1	13	10
8	17	23	1	12	7	5	1	13	10	Đổi chỗ
8	17	1	23	12	7	5	1	13	10	Đổi chỗ
8	17	1	12	23	7	5	1	13	10	Đổi chỗ
8	17	1	12	7	23	5	1	13	10	Đổi chỗ
8	17	1	12	7	5	23	1	13	10	Đổi chỗ
8	17	1	12	7	5	1	23	13	10	Đổi chỗ
8	17	1	12	7	5	1	13	23	10	Đổi chỗ
8	17	1	12	7	5	1	13	10	23	Hết lượt 1

Lượt thứ hai:

a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀	Giải thích
8	17	1	12	7	5	1	13	10	23
8	17	1	12	7	5	1	13	10	23	Đổi chỗ
8	1	17	12	7	5	1	13	10	23	Đổi chỗ
8	1	12	17	7	5	1	13	10	23	Đổi chỗ
8	1	12	7	17	5	1	13	10	23	Đổi chỗ
8	1	12	7	5	17	1	13	10	23	Đổi chỗ
8	1	12	7	5	1	17	13	10	23	Đổi chỗ
8	1	12	7	5	1	13	17	10	23	Đổi chỗ
8	1	12	7	5	1	13	10	17	23
8	1	12	7	5	1	13	10	17	23	Hết lượt 2

Lượt thứ ba:

a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀	Giải thích
8	1	12	7	5	1	13	10	17	23	Đổi chỗ
1	8	12	7	5	1	13	10	17	23
1	8	12	7	5	1	13	10	17	23	Đổi chỗ
1	8	7	12	5	1	13	10	17	23	Đổi chỗ
1	8	7	5	12	1	13	10	17	23	Đổi chỗ
1	8	7	5	1	12	13	10	17	23
1	8	7	5	1	12	13	10	17	23	Đổi chỗ
1	8	7	5	1	12	10	13	17	23
1	8	7	5	1	12	10	13	17	23
1	8	7	5	1	12	10	13	17	23	Hết lượt 3

Lượt thứ tư:

a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀	Giải thích
1	8	7	5	1	12	10	13	17	23
1	8	7	5	1	12	10	13	17	23	Đổi chỗ
1	7	8	5	1	12	10	13	17	23	Đổi chỗ
1	7	5	8	1	12	10	13	17	23	Đổi chỗ
1	7	5	1	8	12	10	13	17	23
1	7	5	1	8	12	10	13	17	23	Đổi chỗ
1	7	5	1	8	10	12	13	17	23
1	7	5	1	8	10	12	13	17	23
1	7	5	1	8	10	12	13	17	23
1	7	5	1	8	10	12	13	17	23	Hết lượt 4

Lượt thứ năm:

a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀	Giải thích
1	7	5	1	8	10	12	13	17	23
1	7	5	1	8	10	12	13	17	23	Đổi chỗ
1	5	7	1	8	10	12	13	17	23	Đổi chỗ
1	5	1	7	8	10	12	13	17	23
1	5	1	7	8	10	12	13	17	23
1	5	1	7	8	10	12	13	17	23
1	5	1	7	8	10	12	13	17	23
1	5	1	7	8	10	12	13	17	23
1	5	1	7	8	10	12	13	17	23
1	5	1	7	8	10	12	13	17	23	Hết lượt 5

Lượt thứ sáu:

a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀	Giải thích
1	5	1	7	8	10	12	13	17	23
1	5	1	7	8	10	12	13	17	23	Đổi chỗ
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23	Hết lượt 6

Lượt thứ bảy:

a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀	Giải thích
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23
1	1	5	7	8	10	12	13	17	23	Hết lượt 7

Dãy đã sắp xếp xong; thuật toán kết thúc.

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.

1) Tìm x = 5;

2) Tìm x = 6.

Đáp án:

1) Tìm x = 5;

Dãy (a)	a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀
Ban đầu	1	1	5	7	8	10	12	13	17	23
Bước 1	1	1	5	7
Bước 2			5	7
Bước 3			5

Chia đôi lần 1: số giữa dãy là a₅ = 8.

Vì x = 5 < 8 nên chọn nửa dãy phía trước là 1, 1, 5, 7.

Chia đôi lần 2: số giữa dãy mới là a₂ = 1.

Vì x = 5 > 1 nên chọn nửa dãy phía sau là 5, 7.

Chia đôi lần 3: số giữa dãy mới là a₃ = 5.

Vì x = 5 =5 (a₃). Thuật toán kết thúc với kết quả: Tìm thấy x ở vị trí thứ ba trong dãy.

1) Tìm x = 6;

Dãy (a)	a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	a₁₀
Ban đầu	1	1	5	7	8	10	12	13	17	23
Bước 1	1	1	5	7
Bước 2			5	7
Bước 3			5

Chia đôi lần 1: số giữa dãy là a₅ = 8.

Vì x = 6 < 8 nên chọn nửa dãy phía trước là 1, 1, 5, 7.

Chia đôi lần 2: số giữa dãy mới là a₂ = 1.

Vì x = 6 > 1 nên chọn nửa dãy phía sau là 5, 7.

Chia đôi lần 3: số giữa dãy mới là a₃ = 5.

Vì x = 6 >5 (a₃). Phạm vi tìm kiếm chỉ còn một số.

Thuật toán kết thúc với kết quả: Không tìm thấy x ở vị trí thứ ba trong dãy.

Xem thêm các bài khác tại Giải bài tập sách giáo khoa Tin học lớp 7 – NXB Cánh Diều

Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech

Tuyết Nguyễn

Không bao giờ từ bỏ hy vọng. Cố gắng mỗi ngày.

Post Views: 210