Câu hỏi:
11/05/2023 368
1. Hãy trình bày cách giải bài toán tìm bi giả với 5 viên bi.
2. Trường hợp tổng quát có n viên bi cách làm như thế nào?
3. Ý tưởng chia để trị để giải bài toán tìm bi giả được thể hiện như thế nào?
1. Hãy trình bày cách giải bài toán tìm bi giả với 5 viên bi.
2. Trường hợp tổng quát có n viên bi cách làm như thế nào?
3. Ý tưởng chia để trị để giải bài toán tìm bi giả được thể hiện như thế nào?
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
1. Cách giải bài toán tìm bi giả với 5 viên bi.
Với 5 viên bi, lần cân đầu tiên chúng ta lấy 4 viên bi, đặt 2 viên bi ở hai bên cân.
Trường họp 1. Nếu cân thăng bằng thì xác định được viên bi còn lại chưa cân là bi giả.
Như vậy, sau lần cần thứ nhất ta tìm được bi giả.
Trường hợp 2. Nếu cân bị lệch, ta sẽ xác định bên nặng hơn chứa bi giả. Lấy hai viên bi ở bên nặng hơn và cân mỗi bên một viên, ta sẽ xác định được viên bi giả. Như vậy, sau lần cân thứ hai ta tìm được bi giả.
2. Trường hợp tổng quát có n viên bi cách làm như sau:
- Nếu n lẻ, n = 2k + 1, sau lần cân thứ nhất với mỗi bên k viên, hoặc tìm thấy ngay viên bi giả, hoặc biết bên nào có chứa bi giả và tiếp tục cân với k viên bi đó.
- Nếu n chẵn, n = 2k, sau lần cân thứ nhất, ta tìm được k viên bi chữa viên bi giả. Tổng quát, sau một lần cân, từ bài toán với n viên bi sẽ dẫn đến bài toán với [n/21 viên bi ([x] là phần nguyên của x). Khi bài toán dẫn đến còn hai hoặc ba viên bi thì chỉ cần một lần cân nữa sẽ tìm được viên bi giả.
3. Ý tưởng chia để trị để giải bài toán tìm bi giả được thể hiện như thế nào?
Ý tưởng chia để trị để giải bài toán tìm bi giả: Từ bài toán gốc luôn chia thành các bài toán có kích thước nhỏ hơn, ở đây là [n/2]. Khi số bi còn lại là 2 thì bài toán rất đơn giản có thể giải quyết ngay, đó là trị. Sau khi trị xong, kết hợp lại cả quá trình để tổng hợp kết quả chung sẽ giải quyết được bài toán gốc.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Mô tả các bước thực hiện thuật toán tìm kiếm nhị phân khi left = right
Mô tả các bước thực hiện thuật toán tìm kiếm nhị phân khi left = right
Xem đáp án »
12/07/2024
530
Câu 2:
Để tính giá trị (số nguyên) gần đúng căn bậc hai của số tự nhiên n cho trước, người ta đã thiết lập hàm sau với ý tưởng gần tương tự thuật toán tìm kiếm tuần tự như sau
Hãy thiết kế lại thuật toán tìm số nguyên lớn nhất không vượt quá căn bậc hai của n bằng kĩ thuật chia để trị.
Để tính giá trị (số nguyên) gần đúng căn bậc hai của số tự nhiên n cho trước, người ta đã thiết lập hàm sau với ý tưởng gần tương tự thuật toán tìm kiếm tuần tự như sau
Hãy thiết kế lại thuật toán tìm số nguyên lớn nhất không vượt quá căn bậc hai của n bằng kĩ thuật chia để trị.
Xem đáp án »
12/07/2024
517
Câu 3:
Viết chương trình hoàn chỉnh nhập một dãy số đơn điệu tăng từ bàn phím, các số cách nhau bởi dấu cách. Sau đó, nhập số K bất kì từ bàn phím và thực hiện việc tìm kiếm số K trong dãy trên. Nếu tìm thấy thì trả lại chỉ số của phần tử có giá trị K, ngược lại trả về – 1.
Viết chương trình hoàn chỉnh nhập một dãy số đơn điệu tăng từ bàn phím, các số cách nhau bởi dấu cách. Sau đó, nhập số K bất kì từ bàn phím và thực hiện việc tìm kiếm số K trong dãy trên. Nếu tìm thấy thì trả lại chỉ số của phần tử có giá trị K, ngược lại trả về – 1.
Xem đáp án »
11/05/2023
354
Câu 4:
Em hãy viết chương trình cài đặt các thuật toán tìm kiếm tuần tự và nhị phân rồi tiến hành đo thời gian thực trên máy tính với hai thuật toán này. Thực hiện kiểm thử với các bộ dữ liệu n = 10, 20, 50, 100 và ghi vào bảng để so sánh thời gian chạy giữa hai thuật toán tìm kiếm này.
Em hãy viết chương trình cài đặt các thuật toán tìm kiếm tuần tự và nhị phân rồi tiến hành đo thời gian thực trên máy tính với hai thuật toán này. Thực hiện kiểm thử với các bộ dữ liệu n = 10, 20, 50, 100 và ghi vào bảng để so sánh thời gian chạy giữa hai thuật toán tìm kiếm này.
Xem đáp án »
11/05/2023
298
Câu 5:
Phương án không đệ quy của thuật toán tìm kiếm nhị phân có phải là chia để trị không?
Phương án không đệ quy của thuật toán tìm kiếm nhị phân có phải là chia để trị không?
Xem đáp án »
12/07/2024
280
về câu hỏi!