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

2.9 K

Lời giải bài tập Tin học lớp 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 sách Cánh diều hay, ngắn gọn sẽ giúp học sinh dễ dàng trả lời câu hỏi Tin học 7 Bài 5 từ đó học tốt môn Tin 7.

Giải bài tập Tin học lớp 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

Luyện tập 1 trang 90 Tin học lớp 7: Cho dãy số ban đầu

Cho dãy số ban đầu

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.

Trả lời:

1) Đối với bài này ta sẽ sử dụng thuật toán tìm kiếm tuần tự để trình bày.

Bước 1. So sánh số ở đầu dãy với x. Vì a1 = 8 khác x nên chuyển sang xét số tiếp theo a2 trong dãy.

Bước 2. So sánh số ở đầu dãy với x. Vì a2 = 17 khác x nên chuyển sang xét số tiếp theo a3 trong dãy.

Bước 3. So sánh số ở đầu dãy với x. Vì a3 = 23 khác x nên chuyển sang xét số tiếp theo a4 trong dãy.

Bước 4. So sánh số ở đầu dãy với x. Vì a4 = 1 khác x nên chuyển sang xét số tiếp theo a5 trong dãy.

Bước 5. So sánh số ở đầu dãy với x. Vì a5 = 12 khác x nên chuyển sang xét số tiếp theo a6 trong dãy.

Bước 6. So sánh số ở đầu dãy với x. Vì a6 = 7 khác x nên chuyển sang xét số tiếp theo a7 trong dãy.

Bước 7. So sánh số ở đầu dãy với x. Vì a7 = 5 bằng 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.

2) Đối với bài này ta sẽ sử dụng thuật toán tìm kiếm tuần tự để trình bày.

Bước 1. So sánh số ở đầu dãy với x. Vì a1 = 8 khác x nên chuyển sang xét số tiếp theo a2 trong dãy.

Bước 2. So sánh số ở đầu dãy với x. Vì a2 = 17 khác x nên chuyển sang xét số tiếp theo a3 trong dãy.

Bước 3. So sánh số ở đầu dãy với x. Vì a3 = 23 khác x nên chuyển sang xét số tiếp theo a4 trong dãy.

Bước 4. So sánh số ở đầu dãy với x. Vì a4 = 1 khác x nên chuyển sang xét số tiếp theo a5 trong dãy.

Bước 5. So sánh số ở đầu dãy với x. Vì a5 = 12 khác x nên chuyển sang xét số tiếp theo a6 trong dãy.

Bước 6. So sánh số ở đầu dãy với x. Vì a6 = 7 khác x nên chuyển sang xét số tiếp theo a7 trong dãy.

Bước 7. So sánh số ở đầu dãy với x. Vì a7 = 5 khác x nên chuyển sang xét số tiếp theo a8 trong dãy.

Bước 8. So sánh số ở đầu dãy với x. Vì a8 = 1 khác x nên chuyển sang xét số tiếp theo a9 trong dãy.

Bước 9. So sánh số ở đầu dãy với x. Vì a9 = 13 khác x nên chuyển sang xét số tiếp theo a10 trong dãy.

Bước 10. So sánh số ở đầu dãy với x. Vì a10 = 10 khác x, ta đã duyệt đến cuối dãy những không tìm thấy x = 6.

Kết luận: Không tìm thấy phần tử x = 6.

Luyện tập 2 trang 90 Tin học lớp 7: 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

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

Trả lời:

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

Tiếp theo đổi chỗ 23 và a1

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

Sau bước 3

23

17

13

1

12

7

5

1

8

10

Tiếp theo đổi chỗ 12 và a4

Sau bước 4

23

17

13

12

1

7

5

1

8

10

Tiếp theo đổi chỗ 10 và a5

Sau bước 5

23

17

13

12

10

7

5

1

8

1

Tiếp theo đổi chỗ 8 và a6

Sau bước 6

23

17

13

12

10

8

5

1

7

1

Tiếp theo đổi chỗ 7 và a7

Sau bước 7

23

17

13

12

10

8

7

1

5

1

Tiếp theo đổi chỗ 5 và a8

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

 

Luyện tập 3 trang 90 Tin học lớp 7: 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

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

Trả lời:

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

Tiếp theo so sánh a1 và a2, a> ađổi chổ a1 và a2

Sau bước 1

17

8

23

1

12

7

5

1

13

10

Tiếp theo so sánh a2 và a3, a> ađổi chổ a2 và a3

Sau bước 2

17

23

8

1

12

7

5

1

13

10

Tiếp theo so sánh a3 và a4, a> agiữ nguyên vị trí

Sau bước 3

17

23

8

1

12

7

5

1

13

10

Tiếp theo so sánh a4 và a5, a> ađổi chổ a4 và a5

Sau bước 4

17

23

8

12

1

7

5

1

13

10

Tiếp theo so sánh a5 và a6, a> ađổi chổ a5 và a6

Sau bước 5

17

23

8

12

7

1

5

1

13

10

Tiếp theo so sánh a6 và a7, a> ađổi chổ a6 và a7

Sau bước 6

17

23

8

12

7

5

1

1

13

10

Tiếp theo so sánh a7 và a8, a= agiữ nguyên vị trí

Sau bước 7

17

23

8

12

7

5

1

1

13

10

Tiếp theo so sánh a8 và a9, a> ađổi chổ a8 và a9

Sau bước 8

17

23

8

12

7

5

1

13

1

10

Tiếp theo so sánh a9 và a10, a10 > ađổi chổ a9 và a10

Sau bước 9

17

23

8

12

7

5

1

13

10

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ả

23

17

13

12

10

8

7

5

1

1

 

Luyện tập 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:

 

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

Dãy kết quả

23

17

13

12

10

8

7

5

1

1

1) x = 5

Bước 1. Chia đôi phạm vi tìm kiếm từ đầu dãy a1 đến a10.

Bước 2. Lấy a5 là vị trí cần chia đôi. Vì a5 > x. Ta sẽ thu hẹp được phạm vi tìm kiếm. Từ a1 đến a5 chắc chắn sẽ không chứa x cần tìm. Kết quả: Tìm thấy số x tại vị trí a8.

Bước 3. Lấy a8 là vị trí cần chia đôi. Khi ta chia đôi ở ata thấy vị trí số x.

2) x = 6

Bước 1. Chia đôi phạm vi tìm kiếm từ đầu dãy a1 đến a10.

Bước 2. Lấy a5 là vị trí cần chia đôi. Vì a5 > x. Ta sẽ thu hẹp được phạm vi tìm kiếm. Từ a1 đến a5 chắc chắn sẽ không chứa x cần tìm.

Bước 3. Lấy a8 là vị trí cần chia đôi. Ta sẽ thu hẹp được phạm vi tìm kiếm. Từ a8 đến a10 chắc chắn sẽ không chứa x cần tìm. Khi đó chỉ còn vị trí avà a7, thì ta kiểm tra không có số x cần tìm. Kết quả: Không tìm thấy số x.

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:

Em sẽ lựa chọn thuật toán sắp xếp nổi bọt vì sắp xếp chọn hay nổi bọt đều như nhau, đều dùng phép so sánh để đưa ra kết quả lớn nhất và đổi chỗ vị trí với nhau. Nhưng khi dùng sắp xếp nổi bọt thì em thấy bước cuối cùng sẽ duyệt mảng lần nữa sẽ chắc chắn là mảng đó đã được sắp xếp theo thứ tự tăng hoặc giảm.

Xem thêm các bài giải SGK Tin học lớp 7 Cánh diều hay, chi tiết khác:

Bài 1: Tìm kiếm tuần tự

Bài 2: Tìm kiếm nhị phân

Bài 3: Sắp xếp chọn

Bài 4: Sắp xếp nổi bọ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

Đánh giá

0

0 đánh giá