Cho một số nguyên N làm đầu vào cho một số hợp âm trong một vòng tròn có 2 * N điểm cuối. Mục đích là để đếm các cách mà chúng ta có thể chia vòng tròn đó bằng cách sử dụng các hợp âm như vậy để không có hợp âm nào giao nhau.
Với N =3, điểm sẽ là 6, 1 cách nhận được 3 hợp âm nằm trong khoảng 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 số 5 cách.
Ví dụ
Đầu vào
N=4
Đầu ra
Count of ways to divide circle using N non-intersecting chords are: 14
Giải thích
There will be a total 8 points between which we can draw chords. After drawing the first chord, the rest of the points will be divided into two sets. No chord can be drawn between points from set 1 and set 2 as they will intersect with the first chord.
Đầu vào
N=6
Đầu ra
Count of ways to divide circle using N non−intersecting chords are: 132
Giải thích
There will be a total 12 points between which we can draw chords. After drawing the first chord, the rest of the points will be divided into two sets. No chord can be drawn between points from set 1 and set 2 as they will intersect with the first chord.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Trong cách tiếp cận này, chúng tôi sẽ đếm các cách sử dụng các số đếm trước đó. Nếu chúng ta vẽ bất kỳ hợp âm nào giữa 2 điểm, các điểm còn lại sẽ được chia thành hai bộ set1 và set2, nếu chúng ta vẽ bất kỳ hợp âm nào giữa các điểm trong hai bộ này thì chúng sẽ giao nhau với hợp âm đầu tiên.
-
Lấy một số nguyên N làm đầu vào.
-
Hàm split_circle (int N) nhận số và trả về số cách chia vòng tròn bằng cách sử dụng N hợp âm không giao nhau
-
Tổng số điểm sẽ là 2 * N dưới dạng tổng_điểm.
-
Lấy một mảng total_cuts [] lưu trữ số lượng các 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] với 1.
-
Đối với tất cả các điểm khác bắt đầu từ điểm =4, tổng số cách sẽ là các cách có điểm i và còn lại n − i − 1 điểm.
-
Vì vậy, hãy lấy total_cuts [i] + =(total_cuts [j] * total_cuts [i − 2 − j])
-
Cuối cùng, chúng ta có tổng số lần cắt [total_points] là tổng số cách.
-
Kết quả là trả về total_cuts [total_points] ở cuối vòng lặp.
Ví dụ
#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<<"Count of ways to divide circle using N non−intersecting chords are:"<<divide_circle(N);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of ways to divide circle using N non-intersecting chords are: 5