Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
Để giải bài toán tìm bi giả với n = 9, ta có thể sử dụng trọng lượng của cân để tìm ra bi giả. Ta có thể áp dụng phương pháp chia đôi để tìm ra bi giả trong tối đa lần cân.
Cụ thể, ta sẽ thực hiện như sau:
1. Đặt ba viên bi vào mỗi bên của cân và để lại ba viên bi còn lại bên ngoài.
2. So sánh hai bên của cân:
- Nếu hai bên bằng nhau, thì ba viên bi còn lại sẽ là bi giả.
- Nếu hai bên không bằng nhau, thì bi giả phải nằm ở bên nặng hơn. Vì vậy, ta bỏ ba viên bi ở bên nhẹ đi và chia ba viên còn lại thành hai phần bằng nhau.
3. Đặt hai viên bi lên cân và để lại một viên bi bên ngoài.
4. So sánh hai bên của cân:
- Nếu hai bên bằng nhau, thì viên bi còn lại sẽ là bi giả.
- Nếu hai bên không bằng nhau, thì bi giả phải nằm ở bên nặng hơn. Vì vậy, ta bỏ viên bi ở bên nhẹ đi và chia viên bi còn lại thành hai phần bằng nhau.
5. Đặt một viên bi lên cân và để lại một viên bi bên ngoài.
6. So sánh hai bên của cân:
- Nếu hai bên bằng nhau, thì viên bi còn lại sẽ là bi giả.
- Nếu hai bên không bằng nhau, thì bi giả phải nằm ở bên nặng hơn.
Vì vậy, để tìm ra bi giả với n = 9, ta cần tối đa 3 lần cân.
Quảng cáo
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Để 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ị.
Câu 2:
Mô tả các bước thực hiện thuật toán tìm kiếm nhị phân khi left = right
Câu 3:
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.
Câu 4:
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?
Câu 5:
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.
Câu 6:
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?
về câu hỏi!