Bài tập  /  Bài đang cần trả lời

Nêu ý tưởng thuật toán tìm kiếm tuần tự

Cứu e 
----- Nội dung dịch tự động từ ảnh -----
Câu 2: Thuật toán tìm kiếm tuần tự
a. Nêu ý tưởng thuật toán tìm kiếm tuần tự
b. Có những khả năng nào xảy ra khi thuật toán tìm kiếm tuần tự được kết thúc?
c. Hãy trình bày diễn biến từng bước của thuật toán tìm kiếm tuần tự áp dụng cho dãy số
{11, 70, 18, 39, 63, 52, 41, 5} để tìm:
1) x = 39.
2) x = 60.
Câu 3. Thuật toán tìm kiếm nhị phân
a. Nêu ý tưởng thuật toán tìm kiếm nhị phân
b. Theo em, có phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm
nhị phân không? Giải thích tại sao.
c. Cho dãy số {5, 23,25,46,57,58,69,78,95}. Hãy mô tả diễn biến từng bước tìm kiếm nhị
phân để tìm kiếm x=57 trong dãy trên
1 trả lời
Hỏi chi tiết
855
0
0
HoàngMinh
26/04/2023 22:00:40
+5đ tặng
Câu 2:
a. Ý tưởng thuật toán tìm kiếm tuần tự là duyệt từng phần tử của dãy để tìm phần tử cần tìm. Bắt đầu từ phần tử đầu tiên, so sánh với phần tử cần tìm. Nếu bằng thì trả về vị trí của phần tử đó, nếu khác thì tiếp tục so sánh với các phần tử tiếp theo cho đến khi tìm thấy hoặc duyệt hết dãy.
b. Khi thuật toán kết thúc, có thể xảy ra hai trường hợp: tìm thấy phần tử cần tìm hoặc không tìm thấy.
c. 
1) Để tìm x = 39: 

Bước 1: So sánh 11 với 39. Không bằng, tiếp tục. 

Bước 2: So sánh 70 với 39. Không bằng, tiếp tục. 

Bước 3: So sánh 18 với 39. Không bằng, tiếp tục. 

Bước 4: So sánh 39 với 39. Bằng, trả về vị trí của phần tử là 4. 

2) Để tìm x = 60: 

Bước 1: So sánh 11 với 60. Không bằng, tiếp tục. 

Bước 2: So sánh 70 với 60. Không bằng, tiếp tục. 

Bước 3: So sánh 18 với 60. Không bằng, tiếp tục. 

Bước 4: So sánh 39 với 60. Không bằng, tiếp tục. 

Bước 5: So sánh 63 với 60. Không bằng, tiếp tục. 

Bước 6: So sánh 52 với 60. Không bằng, tiếp tục. 

Bước 7: So sánh 41 với 60. Không bằng, tiếp tục. 

Bước 8: So sánh 5 với 60. Không bằng, kết thúc thuật toán và trả về không tìm thấy. 

Câu 3:
a. Ý tưởng của thuật toán tìm kiếm nhị phân là tìm kiếm trong một dãy đã được sắp xếp. So sánh phần tử ở giữa của dãy với phần tử cần tìm. Nếu bằng thì kết thúc thuật toán, nếu lớn hơn thì tiếp tục tìm kiếm ở nửa đầu của dãy, nếu nhỏ hơn thì tìm kiếm ở nửa sau của dãy. Tiến hành lặp lại quá trình này cho đến khi tìm thấy hoặc không tìm thấy phần tử cần tìm.
b. Không phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân. Thuật toán chỉ hoạt động với các dãy đã được sắp xếp.
c. Để tìm kiếm x = 57:

Bước 1: So sánh phần tử giữa của dãy (46) với 57. Nhỏ hơn, tiếp tục. 

Bước 2: So sánh phần tử giữa của nửa sau của dãy (69) với 57. Lớn hơn, tiếp tục. 

Bước 3: So sánh phần tử giữa của nửa trước của nửa sau dãy (58) với 57. Nhỏ hơn, tiếp tục. 

Bước 4: So sánh phần tử giữa của nửa sau của nửa sau dãy (69) với 57. Lớn hơn, tiếp tục. 

Bước 5: So sánh phần tử giữa của nửa trước của nửa sau của nửa sau dãy (58) với 57. Nhỏ hơn, tiếp tục. 

Bước 6: So sánh phần tử giữa của nửa sau của nửa sau của nửa sau dãy (69) với 57. Lớn hơn, tiếp tục. 

Bước 7: So sánh phần tử giữa của nửa trước của nửa sau của nửa sau dãy (58) với 57. Nhỏ hơn, tiếp tục. 

Bước 8: So sánh phần tử giữa của nửa sau của nửa sau của nửa sau dãy (69) với 57. Lớn hơn, tiếp tục. 

Bước 9: So sánh phần tử giữa của nửa trước của nửa sau của nửa sau dãy (58) với 57. Nhỏ hơn, không còn nửa trước để tìm kiếm, kết thúc thuật toán và trả về không tìm thấy.
 

Mở khóa để xem toàn bộ nội dung trả lời

(?)
Bạn đã đạt đến giới hạn của mình. Bằng cách Đăng ký tài khoản, bạn có thể xem toàn bộ nội dung trả lời
Cải thiện điểm số của bạn bằng cách đăng ký tài khoản Lazi.
Xem toàn bộ các câu trả lời, chat trực tiếp 1:1 với đội ngũ Gia sư Lazi bằng cách Đăng nhập tài khoản ngay bây giờ
Tôi đã có tài khoản? Đăng nhập

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui Buồn Bình thường

Học ngoại ngữ với Flashcard

×
Trợ lý ảo Trợ lý ảo
×
Đấu trường tri thức | Lazi Quiz Challenge +500k