2*N 끝점이 있는 원의 여러 코드에 대한 입력으로 정수 N이 주어집니다. 목표는 코드가 서로 교차하지 않도록 이러한 코드를 사용하여 원을 나눌 수 있는 방법을 계산하는 것입니다.
N=3의 경우 포인트는 6이고 3개의 코드를 얻는 방법은 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 두 세트로 나뉘며, 이 두 세트의 포인트 사이에 코드를 그리면 첫 번째 코드와 교차합니다.
-
정수 N을 입력으로 받습니다.
-
함수 Divide_circle(int N)은 숫자를 받아서 N개의 교차하지 않는 코드를 사용하여 원을 나누는 방법의 개수를 반환합니다.
-
총 포인트 수는 total_points로 2*N입니다.
-
방법의 개수를 저장하는 배열 total_cuts[]를 가져옵니다.
-
0 또는 2 포인트의 경우 total_cuts[0], total_cuts[2]를 1로 초기화하는 방법은 단 한 가지뿐입니다.
-
포인트=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