计算使用N个不相交和弦分割圆的方法-yiteyi-C++库

给定一个数字N，找出在一个有2*N个点的圆中绘制N个和弦的方法，这样就没有两个和弦相交。如果有一个和弦以一种方式存在，而不是以另一种方式存在，那么两种方式是不同的。 例如：

null

Input : N = 2Output : 2Explanation: If points are numbered 1 to 4 in clockwise direction, then different ways to draw chords are:{(1-2), (3-4)} and {(1-4), (2-3)}Input : N = 1Output : 1Explanation: Draw a chord between points 1 and 2.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

如果我们在任意两点之间画一条弦，你能观察到当前的一组点被分成两个较小的集合S_1和S_2吗。如果我们从S_1中的一点到S_2中的一点画一个和弦，它肯定会与我们刚才画的和弦相交。所以，我们可以得到一个循环，即Ways（n）=sum[i=0到n-1]{Ways（i）*Ways（n-i-1）}。这里我们迭代i，假设其中一个集合的大小为i，另一个集合的大小自动为（n-i-1），因为我们已经在一个集合中使用了一对点和一对点。

C++

                         // cpp code to count ways                       
                         // to divide circle using                       
                         // N non-intersecting chords.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     chordCnt(                                     int                                     A){                       
           
                                                 // n = no of points required                       
                                                 int                                     n = 2 * A;                       
                                   
                                                 // dp array containing the sum                       
                                                 int                                     dpArray[n + 1]={ 0 };                       
                                                 dpArray[0] = 1;                       
                                                 dpArray[2] = 1;                       
                                                 for                                     (                                     int                                     i=4;i<=n;i+=2){                       
                                                 for                                     (                                     int                                     j=0;j<i-1;j+=2){                       
                                   
                                                 dpArray[i] +=                       
                                                 (dpArray[j]*dpArray[i-2-j]);                       
                                                 }                       
                                                 }                       
           
                                                 // returning the required number                       
                                                 return                                     dpArray[n];                       
                         }                       
                         // Driver function                       
                         int                                     main()                       
                         {                       
           
                                                 int                                     N;                       
                                                 N = 2;                       
                         cout<<chordCnt( N)<<                                     ''                                     ;                       
                                                 N = 1;                       
                         cout<<chordCnt( N)<<                                     ''                                     ;                       
                                                 N = 4;                       
                         cout<<chordCnt( N)<<                                     ''                                     ;                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by Gitanjali.                       

JAVA

                         // Java code to count ways                       
                         // to divide circle using                       
                         // N non-intersecting chords.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                                 static                                     int                                     chordCnt(                                     int                                     A)                       
                                                 {                       
           
                                                 // n = no of points required                       
                                                 int                                     n =                                     2                                     * A;                       
           
                                                 // dp array containing the sum                       
                                                 int                                     [] dpArray =                                     new                                     int                                     [n +                                     1                                     ];                       
                                                 dpArray[                                     0                                     ] =                                     1                                     ;                       
                                                 dpArray[                                     2                                     ] =                                     1                                     ;                       
                                                 for                                     (                                     int                                     i =                                     4                                     ; i <= n; i +=                                     2                                     ) {                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < i -                                     1                                     ; j +=                                     2                                     )                       
                                                 {                       
                                                 dpArray[i] += (dpArray[j] *                       
                                                 dpArray[i -                                     2                                     - j]);                       
                                                 }                       
                                                 }                       
           
                                                 // returning the required number                       
                                                 return                                     dpArray[n];                       
                                                 }                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     N;                       
                                                 N =                                     2                                     ;                       
                                                 System.out.println(chordCnt(N));                       
                                                 N =                                     1                                     ;                       
                                                 System.out.println(chordCnt(N));                       
                                                 N =                                     4                                     ;                       
                                                 System.out.println(chordCnt(N));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Gitanjali.                       

Python 3

                         # python code to count ways to divide                       
                         # circle using N non-intersecting chords.                       
                         def                                     chordCnt( A):                       
           
                                                 # n = no of points required                       
                                                 n                                     =                                     2                                     *                                     A                       
           
                                                 # dp array containing the sum                       
                                                 dpArray                                     =                                     [                                     0                                     ]                                     *                                     (n                                     +                                     1                                     )                       
                                                 dpArray[                                     0                                     ]                                     =                                     1                       
                                                 dpArray[                                     2                                     ]                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (                                     4                                     , n                                     +                                     1                                     ,                                     2                                     ):                       
                                                 for                                     j                                     in                                     range                                     (                                     0                                     , i                                     -                                     1                                     ,                                     2                                     ):                       
                                                 dpArray[i]                                     +                                     =                                     (dpArray[j]                                     *                                     dpArray[i                                     -                                     2                                     -                                     j])                       
           
                                                 # returning the required number                       
                                                 return                                     int                                     (dpArray[n])                       
           
                         # driver code                       
                         N                                     =                                     2                       
                         print                                     (chordCnt( N))                       
                         N                                     =                                     1                       
                         print                                     (chordCnt( N))                       
                         N                                     =                                     4                       
                         print                                     (chordCnt( N))                       

C#

                         // C# code to count ways to divide                       
                         // circle using N non-intersecting chords.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     chordCnt(                                     int                                     A)                       
                                                 {                       
                                                 // n = no of points required                       
                                                 int                                     n = 2 * A;                       
           
                                                 // dp array containing the sum                       
                                                 int                                     [] dpArray =                                     new                                     int                                     [n + 1];                       
                                                 dpArray[0] = 1;                       
                                                 dpArray[2] = 1;                       
                                   
                                                 for                                     (                                     int                                     i = 4; i <= n; i += 2)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 0; j < i - 1; j += 2)                       
                                                 {                       
                                                 dpArray[i] += (dpArray[j] * dpArray[i - 2 - j]);                       
                                                 }                       
                                                 }                       
           
                                                 // returning the required number                       
                                                 return                                     dpArray[n];                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     N;                       
                                                 N = 2;                       
                                                 Console.WriteLine(chordCnt(N));                       
                                                 N = 1;                       
                                                 Console.WriteLine(chordCnt(N));                       
                                                 N = 4;                       
                                                 Console.WriteLine(chordCnt(N));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP code to count ways                       
                         // to divide circle using                       
                         // N non-intersecting chords.                       
                         function                                     chordCnt(                                     $A                                     )                       
                         {                       
           
                                                 // n = no of points required                       
                                                 $n                                     = 2 *                                     $A                                     ;                       
                                   
                                                 // dp array containing the sum                       
                                                 $dpArray                                     =                                     array_fill                                     (0,                                     $n                                     + 1, 0);                       
                                                 $dpArray                                     [0] = 1;                       
                                                 $dpArray                                     [2] = 1;                       
                                                 for                                     (                                     $i                                     = 4;                                     $i                                     <=                                     $n                                     ;                                     $i                                     += 2)                       
                                                 {                       
                                                 for                                     (                                     $j                                     = 0;                                     $j                                     <                                     $i                                     - 1;                                     $j                                     += 2)                       
                                                 {                       
                                   
                                                 $dpArray                                     [                                     $i                                     ] += (                                     $dpArray                                     [                                     $j                                     ] *                       
                                                 $dpArray                                     [                                     $i                                     - 2 -                                     $j                                     ]);                       
                                                 }                       
                                                 }                       
           
                                                 // returning the required number                       
                                                 return                                     $dpArray                                     [                                     $n                                     ];                       
                         }                       
           
                         // Driver Code                       
                         $N                                     = 2;                       
                         echo                                     chordCnt(                                     $N                                     ),                                     ""                                     ;                       
                         $N                                     = 1;                       
                         echo                                     chordCnt(                                     $N                                     ),                                     ""                                     ;                       
                         $N                                     = 4;                       
                         echo                                     chordCnt(                                     $N                                     ),                                     ""                                     ;                       
                                   
                         // This code is contributed by Ryuga                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript code to count ways                       
                         // to divide circle using                       
                         // N non-intersecting chords.                       
           
                         function                                     chordCnt( A){                       
           
                                                 // n = no of points required                       
                                                 var                                     n = 2 * A;                       
                                   
                                                 // dp array containing the sum                       
                                                 var                                     dpArray = Array(n+1).fill(0);                       
                                                 dpArray[0] = 1;                       
                                                 dpArray[2] = 1;                       
                                                 for                                     (                                     var                                     i=4;i<=n;i+=2){                       
                                                 for                                     (                                     var                                     j=0;j<i-1;j+=2){                       
                                   
                                                 dpArray[i] +=                       
                                                 (dpArray[j]*dpArray[i-2-j]);                       
                                                 }                       
                                                 }                       
           
                                                 // returning the required number                       
                                                 return                                     dpArray[n];                       
                         }                       
           
           
                         // Driver function                       
                         var                                     N;                       
                         N = 2;                       
                         document.write( chordCnt( N) +                                     '<br>'                                     );                       
                         N = 1;                       
                         document.write( chordCnt( N) +                                     '<br>'                                     );                       
                         N = 4;                       
                         document.write( chordCnt( N) +                                     '<br>'                                     );                       
           
           
                         </script>                       

输出：

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章