Tin học 7 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

* Yêu cầu: 

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 thực hiện:

a. x = 5

- Bước 1: 

So sánh số ở đầu dãy với x

Vì a₁ = 8 ≠ x nên chuyển sang xét số tiếp theo a₂ trong dãy

- Bước 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 a₃ trong dãy

- Bước 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 a₄ trong dãy

- Bước 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

- Bước 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

- Bước 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 a₇ trong dãy

- Bước 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ứ 7 trong dãy; kết thúc thuật toán

b. x = 6

Tương tự cách thực hiện câu a ta có:

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. Hết dãy đã xét Kết luận: Không Tìm thấy x trong dãy; kết thúc thuật toán

* Yêu cầu: 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 giải:

* Yêu cầu: 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 thực hiệ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:

- Lượt thứ hai:

- Lượt thứ ba: 

→ Tiếp tục quá trình cho đến khi thu được dãy giảm dần

* Yêu cầu: 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.

a. Tìm x = 5.

b. Tìm x = 6.

* Hướng dẫn thực hiện:

a. Tìm x = 5

- Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a₁ đến a₁₀. Lấy a₅ là số có vị trí giữa dãy; Vì x < a₅ 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ừ a₆ đến a₁₀.

- Chia đôi lần 2: Phạm vi tìm kiếm là dãy từ a₆ đến a₁₀. Lấy a₈ là số có vị trí giữa dãy. Vì x = a₈ 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ừ a₁ đến a₁₀. Lấy a₅ là số có vị trí giữa dãy; Vì x < a₅ 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ừ a₆ đến a₁₀. Lấy a₈ là số có vị trí giữa dãy. Vì x > a₈ 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ừ a₅ đến a₇.

- Chia đôi lần 3: Phạm vi tìm kiếm là dãy từ a₅ đến a₇. Lấy a₆ là số có vị trí giữa dãy. Vì  x < a₆ 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à a₇.

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.

Qua bài học các em có thể:

Mô phỏng được hoạt động của một số thuật toán tìm kiếm, sắp xếp bằng các bước thủ công (không cần dùng máy tính) trên một bộ dữ liệu có kích thước nhỏ.

Các em có thể hệ thống lại nội dung kiến thức đã học được thông qua bài kiểm tra Trắc nghiệm Tin học 7 Cánh diều Chủ đề F Bài 5 cực hay có đáp án và lời giải chi tiết. 

• Câu 1:

  Trong thuật toán tìm kiếm tuần tự có bao nhiêu khả năng xảy ra khi kết thúc tìm kiếm tuần tự?

  • A. 1
  • B. 2
  • C. 3
  • D. 4

• Câu 2:

  Với dãy số: 12, 13, 32, 45, 33. Số lần so sánh trong bài toán “Tìm xem số 13 có trong dãy này không” là bao nhiêu?

  • A. 1
  • B. 2
  • C. 3
  • D. 4

• Câu 3:

  Kết quả của bài toán “Tìm xem số 13 có trong dãy này không” với dãy số: 12, 14, 32, 45, 3 là gì?

  • A. Không tìm thấy
  • B. Tìm thấy
  • C. Tìm thấy ở đầu dãy
  • D. Tìm thấy ở cuối dãy

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 7 Cánh diều Chủ đề F Bài 5 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Vận dụng trang 90 SGK Tin học 7 Cánh diều - CD

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!