Câu hỏi:
12/07/2024 666
Theo em, với dãy đã sắp thứ tự và cho một số x cụ thể
a) Trường hợp nào tìm kiếm tuần tự nhanh hơn tìm kiếm nhị phân?
b) Về trung bình thuật toán tìm kiếm tuần tự hay thuật toán tìm kiếm nhị phân tốt hơn?
Theo em, với dãy đã sắp thứ tự và cho một số x cụ thể
a) Trường hợp nào tìm kiếm tuần tự nhanh hơn tìm kiếm nhị phân?
b) Về trung bình thuật toán tìm kiếm tuần tự hay thuật toán tìm kiếm nhị phân tốt hơn?
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
a. Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:
Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:
- Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5
- Vì sau bước 2 đã tìm thấy tên học sinh nên thuật toán kết thúc.
b) Thuật toán tìm kiếm nhị phân
- Thuật toán tìm kiếm nhị phân thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp. Thuật toán chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.
Thuật toán tuần tự
- Mô tả thuật toán phải cụ thể, rõ ràng, đầy đủ, đầu vào là gì, đầu ra là gì và chỉ rõ sự kết thúc thuật toán.
- Cần mô tả thuật toán cho tốt thì người máy hay máy tính mới hiểu đúng và thực hiện được.
- Nếu không, kết quả thực hiện thuật toán có thể không như mong đợi.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
a. Viết chương trình phython thực hiện tìm kiếm tuần tự
b. Viết phiên bản tìm kiếm tuần tự thứ hai, dùng vòng lặp for thay cho vòng lặp while (hoặc ngược lại).
c. Viết phiên bản tìm kiếm tuần tự có thêm hai tham số đầu vào lo và hi tương tự như của hàm index. So sánh kết quả với phương thức index của phython.
a. Viết chương trình phython thực hiện tìm kiếm tuần tự
b. Viết phiên bản tìm kiếm tuần tự thứ hai, dùng vòng lặp for thay cho vòng lặp while (hoặc ngược lại).
c. Viết phiên bản tìm kiếm tuần tự có thêm hai tham số đầu vào lo và hi tương tự như của hàm index. So sánh kết quả với phương thức index của phython.
Xem đáp án »
13/07/2024
1,819
Câu 2:
Em hãy nêu ra một vài ví dụ về bài toàn tìm kiếm trong thực tế.
Em hãy nêu ra một vài ví dụ về bài toàn tìm kiếm trong thực tế.
Xem đáp án »
13/07/2024
1,391
Câu 3:
Em hãy tính số phép toán sơ cấp, điền vào cột bên phải của bảng ở Hình 2 ước lượng độ phức tạp thời gian của thuật toán tìm kiếm tuần tự.
Em hãy tính số phép toán sơ cấp, điền vào cột bên phải của bảng ở Hình 2 ước lượng độ phức tạp thời gian của thuật toán tìm kiếm tuần tự.
Xem đáp án »
12/07/2024
581
Câu 4:
Em hãy thực hiện các yêu cầu sau:
1. Viết mã giả cho thuật toán tìm kiếm nhị phân.
2. Ước lượng số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân.
3. Ước lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân.
Em hãy thực hiện các yêu cầu sau:
1. Viết mã giả cho thuật toán tìm kiếm nhị phân.
2. Ước lượng số lần thực hiện vòng lặp trong thuật toán tìm kiếm nhị phân.
3. Ước lượng độ phức tạp thời gian của thuật toán tìm kiếm nhị phân.
Xem đáp án »
13/07/2024
501
Câu 5:
Viết chương trình tìm kiếm vị trí tên của một người trong mỗi danh sách sau đây:
a. Danh sách học sinh của lớp em.
b. Danh sách tên của các chủ tài khoản ngân hàng (kí tự không dấu) và đã sắp thứ tự theo bảng chữ cái.
Viết chương trình tìm kiếm vị trí tên của một người trong mỗi danh sách sau đây:
a. Danh sách học sinh của lớp em.
b. Danh sách tên của các chủ tài khoản ngân hàng (kí tự không dấu) và đã sắp thứ tự theo bảng chữ cái.
Xem đáp án »
11/06/2023
445
Câu 6:
Khi tạo mới một tài khoản người dùng, em được yêu cầu nhập tên người dùng “user name”. Có trường hợp em phải nhập lại tên khác vì tên vừa nhập đã có người sử dụng rồi. Theo em, máy tính làm gì ngay sau khi nhận được yêu cầu tạo mới một tài khoản? Hãy phát biểu thành một bài toán.
Khi tạo mới một tài khoản người dùng, em được yêu cầu nhập tên người dùng “user name”. Có trường hợp em phải nhập lại tên khác vì tên vừa nhập đã có người sử dụng rồi. Theo em, máy tính làm gì ngay sau khi nhận được yêu cầu tạo mới một tài khoản? Hãy phát biểu thành một bài toán.
Xem đáp án »
12/07/2024
432
về câu hỏi!