Đếm số cách chia đường tròn bằng N dây cung không cắt nhau trong C++

Cho một số nguyên N làm đầu vào cho số dây cung trong một đường tròn với 2*N điểm cuối. Mục tiêu là đếm số cách chia đường tròn đó bằng các dây cung sao cho không có dây cung nào cắt nhau.

Với N=3, số điểm sẽ là 6, 1 cách để có 3 dây cung là giữa 1-2, 3-4, 5-6.

Các cách khác:

1-6, 2-5, 3-4
1-2, 3-6, 4-5
1-4, 2-3, 5-6
1-6, 2-3, 4-5

Tổng 5 cách.

Ví dụ

Đầu vào

N=4

Đầu ra

Số cách chia đường tròn bằng N dây cung không cắt nhau là: 14

Giải thích

Sẽ có tổng 8 điểm giữa các dây cung có thể vẽ. Sau khi vẽ dây cung đầu tiên, các điểm còn lại sẽ bị chia thành hai tập hợp. Không dây cung nào có thể vẽ giữa các điểm từ tập 1 và tập 2 vì chúng sẽ cắt dây cung đầu tiên.

Đầu vào

N=6

Đầu ra

Số cách chia đường tròn bằng N dây cung không cắt nhau là: 132

Giải thích

Sẽ có tổng 12 điểm giữa các dây cung có thể vẽ. Sau khi vẽ dây cung đầu tiên, các điểm còn lại sẽ bị chia thành hai tập hợp. Không dây cung nào có thể vẽ giữa các điểm từ tập 1 và tập 2 vì chúng sẽ cắt dây cung đầu tiên.

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ đếm số cách dùng các số cách trước đó. Nếu chúng ta vẽ bất kỳ dây cung nào giữa 2 điểm, các điểm còn lại sẽ bị chia thành hai tập hợp set1 và set2, nếu chúng ta vẽ bất kỳ dây cung nào giữa các điểm trong hai tập hợp này thì chúng sẽ cắt dây cung đầu tiên.

Nhận số nguyên N làm đầu vào.
Hàm divide_circle(int N) nhận số và trả về số cách chia đường tròn dùng N dây cung không cắt nhau.
Tổng số điểm sẽ là 2*N như total_points.
Tạo mảng total_cuts[] lưu số cách.
Đối với 0 hoặc 2 điểm sẽ chỉ có 1 cách, khởi tạo total_cuts[0], total_cuts[2] bằng 1.
Đối với tất cả các điểm khác bắt đầu từ points=4, tổng số cách sẽ là số cách với i điểm và phần còn lại n-i-1 điểm.
Vì vậy lấy total_cuts[i] += (total_cuts[j] * total_cuts[i-2-j]).
Cuối cùng, chúng ta có total_cuts[total_points] là tổng số cách.
Trả về total_cuts[total_points] làm kết quả ở cuối vòng lặp.

Ví dụ mã

#include <bits/stdc++.h> 
using namespace std; 

int divide_circle(int N) {
    int total_points = 2 * N;
    int total_cuts[total_points + 1] = { 0 };
    total_cuts[0] = 1;
    total_cuts[2] = 1;
    
    for (int i = 4; i <= total_points; i += 2) {
        for (int j = 0; j < i-1; j += 2) {
            total_cuts[i] += (total_cuts[j] * total_cuts[i-2-j]);
        }
    }
    
    return total_cuts[total_points];
}

int main() {
    int N = 3;
    cout << "Số cách chia đường tròn bằng N dây cung không cắt nhau là: " << divide_circle(N);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số cách chia đường tròn bằng N dây cung không cắt nhau là: 5