C++でN個の交差しないコードを使用して円を分割する方法を数えます

2*Nの終点を持つ円内のいくつかの弦の入力として整数Nを指定します。目標は、そのようなコードを使用してその円を分割し、コードが互いに交差しないようにする方法を数えることです。

N =3の場合、ポイントは6になります。3つのコードを取得する1つの方法は、1〜2、3〜4、5〜6の間です

その他の方法-

1−6, 2−5, 3−4
1−2, 3−6, 4−5
1−4, 2−3, 5−6
1−6, 2−3, 4−5

合計5つの方法。

例

入力

N=4

出力

Count of ways to divide circle using N non-intersecting chords are: 14

説明

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.

入力

N=6

出力

Count of ways to divide circle using N non−intersecting chords are: 132

説明

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.

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、以前のカウントを使用してウェイをカウントします。 2つのポイントの間にコードを描くと、残りのポイントはset1とset2の2つのセットに分割され、これら2つのセットのポイントの間にコードを描くと、最初のコードと交差します。

• 入力として整数Nを取ります。

• 関数divide_circle（int N）は数値を受け取り、N個の交差しないコードを使用して円を分割する方法の数を返します

• ポイントの総数は、total_pointsとして2*Nになります。

• ウェイの数を格納する配列total_cuts[]を取ります。

• 0または2ポイントの場合、total_cuts [0]、total_cuts[2]を1で初期化する方法は1つだけです。

• points =4から始まる他のすべてのポイントの場合、合計ウェイはポイントiと残りのn-i-1ポイントを持つウェイになります。

• したがって、total_cuts [i] + =（total_cuts [j] * total_cuts [i−2−j]）

• 最後に、ウェイの総数としてtotal_cuts[total_points]があります。

• ループの最後に結果としてtotal_cuts[total_points]を返します。

例

#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;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of ways to divide circle using N non-intersecting chords are: 5