F12.Em đã viết thuật toán giải bài toán cho ba đồng xu trong đó có một đồng xu giả nhẹ hơn,...
Câu hỏi:
F12. Em đã viết thuật toán giải bài toán cho ba đồng xu trong đó có một đồng xu giả nhẹ hơn, dùng cân thăng bằng để tìm ra đồng xu giả.
1) Hãy bổ sung chỉnh sửa thuật toán nếu chỉ biết đồng xu giả có trọng lượng khác với đồng xu thật.
2) Hãy bổ sung chỉnh sửa thành thuật toán giải bài toán cho bốn đồng xu trong đó có một đồng xu giả.
Câu trả lời:
Người trả lời: GV. Đỗ Hồng Ánh
Phương pháp giải:1) Bước 1: Lấy hai đồng xu bất kì và đặt lên cân thăng bằng.2) Bước 2: Nếu cân thăng bằng, kết luận đồng xu còn lại là đồng xu giả.3) Bước 3: Nếu cân lệch nghiêng, tráo đổi đồng xu còn lại với một trong hai đồng xu trên cân.4) Bước 4: Nếu cân thăng bằng, đồng xu vừa lấy ra là đồng xu giả.5) Bước 5: Nếu cân lệch nghiêng, đồng xu còn để nguyên trên cân là đồng xu giả.2) Bước 1: Lấy hai đồng xu bất kì và đặt lên cân thăng bằng.2) Bước 2: Nếu cân thăng bằng, xếp hai đồng xu đã cân vào bên T.3) Bước 3: Nếu cân lệch nghiêng, xếp hai đồng xu chưa cân vào bên T.4) Bước 4: Cân so sánh một đồng xu bên T với một đồng xu chưa xếp.5) Bước 5: Nếu cân thăng bằng, đồng xu chưa cân là đồng xu giả.6) Bước 6: Nếu cân lệch nghiêng, đồng xu vừa cân so sánh là đồng xu giả.Câu trả lời:1) Đồng xu giả có trọng lượng khác với đồng xu thật.2) Đồng xu giả có trọng lượng khác với đồng xu thật.Mỗi bước chi tiết trong thuật toán đã được mô tả, giúp phát hiện đồng xu giả trong số các đồng xu bằng cách sử dụng cân thăng bằng.
Câu hỏi liên quan:
5) Để tối ưu thuật toán, ta có thể sử dụng phương pháp chia đôi liên tục. Chia dãy đồng xu thành các phần bằng nhau, thực hiện cân so sánh trọng lượng của các phần. Tiếp tục chia đôi phần có đồng xu giả đến khi chỉ còn lại một đồng xu, đó chính là đồng xu giả.
4) Một phương pháp khác, ta có thể sử dụng phép cân đơn giản bằng cách cân từng cặp đồng xu, nếu có đồng xu giả, nó sẽ làm cho cân bất kỳ cặp nào trở nên không cân bằng. Sử dụng số lần cân ít nhất để xác định đồng xu giả.
3) Để tổng quát hơn, ta có thể áp dụng giải thuật chia để trị trong trường hợp này. Chia dãy đồng xu thành hai phần bằng nhau, thực hiện cân so sánh trọng lượng của hai phần. Nếu hai phần không cân bằng, ta tiếp tục tìm trong phần nặng hơn, nếu hai phần cân bằng, ta tìm trong phần thứ ba.
2) Bổ sung chỉnh sửa thành thuật toán giải bài toán cho bốn đồng xu trong đó có một đồng xu giả, ta có thể thực hiện bước kiểm tra bằng cách chia bốn đồng xu thành hai nhóm, mỗi nhóm chứa hai đồng xu. Thực hiện cân so sánh hai nhóm, nếu cân không cân bằng thì ta đã tìm ra đồng xu giả, nếu cân bằng thì đồng xu giả nằm trong nhóm chưa cân mà nặng hơn nhóm cân.
1) Để bổ sung chỉnh sửa thuật toán nếu chỉ biết đồng xu giả có trọng lượng khác với đồng xu thật, ta có thể thực hiện bước kiểm tra bằng cách chia ba đồng xu thành hai nhóm bằng nhau, mỗi nhóm chứa 1 đồng xu. Thực hiện cân so sánh hai nhóm, nếu cân không cân bằng thì ta đã tìm ra đồng xu giả, nếu cân bằng thì đồng xu giả nằm trong nhóm chưa cân mà nặng hơn nhóm cân.