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

Giải 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 tin học 7 cánh diều. Phần đáp án chuẩn, hướng dẫn giải chi tiết cho từng bài tập có trong chương trình học của sách giáo khoa. Hi vọng, các em học sinh hiểu và nắm vững kiến thức bài học.

Bài 1. Cho dãy số ban đầu

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

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.

Câu trả lời:

1. Tìm x = 5;

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

Gọi số phải tìm là x (x=5). Các bước thực hiện là:

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.

2. Tìm x = 6

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

Gọi số phải tìm là x (x=6). Các bước thực hiện là:

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 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 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ách làm trong bài "Sắp xếp chọn"

Giải 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âu trả lời:

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

Giải 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 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"

Giải 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âu trả lời:

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

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

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

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

Giải 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 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.

Giải 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âu trả lời:

1. Tìm x = 5.

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

  • 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<a4 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.

2. Tìm x = 6

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

  • 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<a4 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à dãy từ a6 đến 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.

 

VẬN DỤNG

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.

Câu 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 vì thuật toán sắp xếp chọn sẽ chọn phần tử lớn nhất trong dãy để xếp vào đầu dãy đó. Việc chọn này sẽ tiết kiệm thời gian hơn, nhanh chóng và dễ hiểu hơn so với thuật toán nổi bọt chỉ so sánh và đổi chỗ hai phần tử liền kề. 

Xem thêm các bài Giải tin học 7 cánh diều, hay khác:

Xem thêm các bài Giải tin học 7 cánh diều được biên soạn cho Học kì 1 & Học kì 2 theo mẫu chuẩn của Bộ Giáo dục theo sát chương trình Lớp 7 giúp bạn học tốt hơn.

Lớp 7 | Để học tốt Lớp 7 | Giải bài tập Lớp 7

Giải bài tập SGK, SBT, VBT và Trắc nghiệm các môn học Lớp 7, dưới đây là mục lục các bài giải bài tập sách giáo khoa và Đề thi chi tiết với câu hỏi bài tập, đề kiểm tra 15 phút, 45 phút (1 tiết), đề thi học kì 1 và 2 (đề kiểm tra học kì 1 và 2) các môn trong chương trình Lớp 7 giúp bạn học tốt hơn.