Câu hỏi:
12/07/2024 713
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.
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.
Quảng cáo
Trả lời:
Giải bởi Vietjack
|
|
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 ở a8 ta 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í a6 và 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.
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
Sách thầy cô Vietjack biên soạn:
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giả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.
Lời giả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, a2 > a2 đổ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, a3 > a2 đổ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, a3 > a4 giữ 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, a5 > a4 đổ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, a6 > a5 đổ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, a7 > a6 đổ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, a7 = a8 giữ 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, a9 > a8 đổ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 > a9 đổ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 |
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 10 có đáp án
-
Đề kiểm tra học kì 2 Tin học 7 Kết nối tri thức có đáp án - Đề 1
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 14 có đáp án
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 9 có đáp án
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 15 có đáp án
-
Đề kiểm tra học kì 2 Tin học 7 Cánh diều có đáp án - Đề 1
-
Đề kiểm tra giữa học kì 2 Tin học 7 Chân trời sáng tạo có đáp án - Đề 2
-
Đề kiểm tra giữa học kì 2 Tin học 7 Kết nối tri thức có đáp án - Đề 1
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận