Bài toán đổi màu bi

Học sinh học lập trình

Bài toán đổi màu bi

Trên bàn có N1 hòn bi xanh, N2 hòn bi đỏ và N3 hòn bi vàng. Luật chơi như sau:

Nếu 2 hòn bi khác màu nhau chạm nhau thì chúng sẽ cùng biến thành màu thứ 3 (ví dụ: xanh, vàng --> đỏ, đỏ).

Tìm thuật toán và lập chương trình cho biết rằng có thể biến tất cả các hòn bi đó thành một màu đỏ có được không?

Thuật toán

Để biến tất cả các hòn bi thành màu đỏ, ta cần có ít nhất một hòn bi đỏ để có thể kết hợp với các hòn bi còn lại. Nếu không có hòn bi đỏ nào ban đầu, thì không thể biến tất cả các hòn bi thành màu đỏ.

Nếu có ít nhất một hòn bi đỏ, ta có thể thực hiện thuật toán sau: Chọn một hòn bi đỏ bất kỳ, sau đó lần lượt kết hợp với các hòn bi khác để biến chúng thành hòn bi đỏ. Ví dụ, nếu có một hòn bi đỏ và một hòn bi xanh, ta có thể kết hợp chúng để biến thành hòn bi vàng. Sau đó, ta lại tiếp tục kết hợp hòn bi vàng với các hòn bi khác cho đến khi tất cả các hòn bi đều trở thành màu đỏ.

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

def mix_balls(n1, n2, n3):
    # Kiểm tra xem có ít nhất một hòn bi đỏ không
    if n2 == 0:
        return False

    # Tiến hành biến tất cả các hòn bi thành màu đỏ
    while n1 + n2 + n3 > 1:
        # Nếu còn ít nhất một hòn bi xanh và một hòn bi đỏ, kết hợp chúng để biến thành hòn bi vàng
        if n1 > 0 and n2 > 0:
            n1 -= 1
            n2 -= 1
            n3 += 1
        # Nếu còn ít nhất một hòn bi vàng và một hòn bi đỏ, kết hợp chúng để biến thành hòn bi xanh
        elif n2 > 0 and n3 > 0:
            n2 -= 1
            n3 -= 1
            n1 += 1
        # Nếu chỉ còn một loại bi, ta đã biến được tất cả các hòn bi thành màu đỏ
        else:
            return True

    return True

# Sử dụng chương trình để kiểm tra xem có thể biến tất cả các hòn bi thành màu đỏ hay không
n1 = 5  # số hòn bi xanh
n2 = 3  # số hòn bi đỏ
n3 = 2  # số hòn bi vàng
if mix_balls(n1, n2, n3):
    print("Có thể biến tất cả các hòn bi thành màu đỏ")
else:
    print("Không thể biến tất cả các hòn bi thành màu đỏ")

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

#include <iostream>

using namespace std;

bool mixBalls(int n1, int n2, int n3) {
    // Kiểm tra xem có ít nhất một hòn bi đỏ không
    if (n2 == 0) {
        return false;
    }

    // Tiến hành biến tất cả các hòn bi thành màu đỏ
    while (n1 + n2 + n3 > 1) {
        // Nếu còn ít nhất một hòn bi xanh và một hòn bi đỏ, kết hợp chúng để biến thành hòn bi vàng
        if (n1 > 0 && n2 > 0) {
            n1--;
            n2--;
            n3++;
        }
        // Nếu còn ít nhất một hòn bi vàng và một hòn bi đỏ, kết hợp chúng để biến thành hòn bi xanh
        else if (n2 > 0 && n3 > 0) {
            n2--;
            n3--;
            n1++;
        }
        // Nếu chỉ còn một loại bi, ta đã biến được tất cả các hòn bi thành màu đỏ
        else {
            return true;
        }
    }

    return true;
}

int main() {
    int n1 = 5;  // số hòn bi xanh
    int n2 = 3;  // số hòn bi đỏ
    int n3 = 2;  // số hòn bi vàng
    if (mixBalls(n1, n2, n3)) {
        cout << "Có thể biến tất cả các hòn bi thành màu đỏ" << endl;
    }
    else {
        cout << "Không thể biến tất cả các hòn bi thành màu đỏ" << endl;
    }

    return 0;
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *