Bài toán 12 viên bi (Đề thi Tin học trẻ)

Bài toán (Dành cho học sinh THCS)

Có 12 hòn bi giống hệt nhau về kích thước, hình dáng và khối lượng. Tuy nhiên trong chúng lại có đúng một hòn bi kém chất lượng: hoặc nhẹ hơn hoặc nặng hơn bình thường. Dùng một cân bàn hai bên, bạn hãy dùng 3 lần cân để tìm ra được viên bi đó. Cần chỉ rõ rằng viên bi đó là nặng hơn hay nhẹ hơn.

Viết chương trình mô phỏng việc tổ chức cân các hòn bi trên. Dữ liệu về hòn bi kém chất lượng do người sử dụng chương trình nắm giữ. Yêu cầu trình bày chương trình đẹp và mỹ thuật.

Đây là bài toán cân đồng quê (12 bi) – tìm bi nặng/nhẹ trong 3 lần cân. Bài toán cân đồng quê (12 bi) là một bài toán tìm kiếm mà trong đó bạn có một tập hợp 12 đồng xu giống hệt nhau về kích thước và hình dáng, nhưng có đúng một đồng xu kém chất lượng, có thể nhẹ hơn hoặc nặng hơn so với các đồng xu khác. Bạn có một cân bàn hai đĩa và chỉ được sử dụng tối đa ba lần cân để tìm ra đồng xu kém chất lượng và xác định xem nó nặng hơn hay nhẹ hơn so với các đồng xu còn lại. Bài toán này đòi hỏi sự phán đoán và khéo léo trong việc chọn các đồng xu để cân và dựa trên kết quả của các lần cân để tìm ra đồng xu kém chất lượng.

Cách giải bài toán

Bài toán cân đồng quê có thể được giải bằng phương pháp chia để trị, trong đó chúng ta chia tất cả các viên bi thành các nhóm bằng nhau (ví dụ: ba nhóm với bốn viên bi trong mỗi nhóm). Tiếp theo, chúng ta cân một số nhóm để loại trừ các nhóm cân bằng. Sau đó, chúng ta chia các viên bi còn lại thành các nhóm mới và tiếp tục quá trình loại trừ các nhóm cân bằng. Quá trình này tiếp tục cho đến khi chỉ còn lại một viên bi, hoặc chúng ta đã tìm được viên bi kém chất lượng.

Cụ thể, để giải bài toán cân đồng quê, chúng ta có thể thực hiện các bước sau đây:

1. Chia tất cả các viên bi thành ba nhóm bằng nhau, với mỗi nhóm chứa bốn viên bi.

2. Cân hai trong ba nhóm để tìm ra nhóm có viên bi kém chất lượng. Nếu cân bằng, viên bi kém chất lượng nằm trong nhóm còn lại.

3. Chia nhóm chứa viên bi kém chất lượng thành hai nhóm, mỗi nhóm chứa hai viên bi.

4. Cân hai viên bi trong một trong hai nhóm để xác định viên bi kém chất lượng có trọng lượng nhẹ hơn hay nặng hơn so với các viên bi khác.

5. Chia nhóm chứa viên bi kém chất lượng thành hai nhóm, mỗi nhóm chứa một viên bi.

6. Cân hai viên bi này để xác định viên bi kém chất lượng có trọng lượng nhẹ hơn hay nặng hơn so với các viên bi khác.

Sau các bước trên, chúng ta sẽ xác định được viên bi kém chất lượng và cũng biết được nó nặng hơn hay nhẹ hơn so với các viên bi khác.

Cài đặt bài toán với Python

# Tạo danh sách chứa các hòn bi
balls = list(range(1, 13))

# Tạo danh sách các trường hợp cân
cases = [(0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11),
         (0, 1, 4, 5), (2, 3, 6, 7), (1, 2, 5, 6),
         (0, 4, 8, 11), (3, 5, 8, 10)]

# Bắt đầu quá trình tìm kiếm bi nặng hoặc nhẹ
for case in cases:
    left = sum([balls[i] for i in case[:2]])
    right = sum([balls[i] for i in case[2:]])
    
    if left == right:
        # Cả hai bên cân bằng nhau - bi nặng/nhẹ không nằm trong danh sách này
        balls = [balls[i] for i in set(range(12)) - set(case)]
    elif left < right:
        # Bên phải nặng hơn
        balls = [balls[i] for i in case[2:]]
    else:
        # Bên trái nặng hơn
        balls = [balls[i] for i in case[:2]]

# Kiểm tra bi nặng/nhẹ
if len(balls) == 1:
    print(f"Bi {balls[0]} là bi kém chất lượng và nặng hơn.")
else:
    print(f"Bi {balls[0]} là bi kém chất lượng và nhẹ hơn.")

Cài đặt bài toán với C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    // Tạo danh sách chứa các hòn bi
    vector<int> balls(12);
    for (int i = 0; i < 12; i++) {
        balls[i] = i + 1;
    }

    // Tạo danh sách các trường hợp cân
    vector<vector<int>> cases = {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11},
                                 {0, 1, 4, 5}, {2, 3, 6, 7}, {1, 2, 5, 6},
                                 {0, 4, 8, 11}, {3, 5, 8, 10}};

    // Bắt đầu quá trình tìm kiếm bi nặng hoặc nhẹ
    for (vector<int> case_: cases) {
        int left = balls[case_[0]] + balls[case_[1]];
        int right = balls[case_[2]] + balls[case_[3]];

        if (left == right) {
            // Cả hai bên cân bằng nhau - bi nặng/nhẹ không nằm trong danh sách này
            vector<int> new_balls;
            set_difference(balls.begin(), balls.end(), case_.begin(), case_.end(), back_inserter(new_balls));
            balls = new_balls;
        }
        else if (left < right) {
            // Bên phải nặng hơn
            balls = {balls[case_[2]], balls[case_[3]]};
        }
        else {
            // Bên trái nặng hơn
            balls = {balls[case_[0]], balls[case_[1]]};
        }
    }

    // Kiểm tra bi nặng/nhẹ
    if (balls.size() == 1) {
        cout << "Bi " << balls[0] << " là bi kém chất lượng và nặng hơn." << endl;
    }
    else {
        cout << "Bi " << balls[0] << " là bi kém chất lượng và nhẹ hơn." << endl;
    }

    return 0;
}