连接圆中点的非交叉线-yiteyi-C++库

考虑一个圆 N 它周长上的点在哪里 n是偶数 .计算连接这些点的方法，这样就不会有两条连接线相互交叉，而且每个点都正好与另一个点连接。任何点都可以与任何其他点连接。

null

Consider a circle with 4 points.    12        3    4In above diagram, there are two non-crossing ways to connect{{1, 2}, {3, 4}} and {{1, 3}, {2, 4}}.Note that {{2, 3}, {1, 4}} is invalidas it would cause a cross

例如：

Input : n = 2Output : 1Input : n = 4Output : 2Input : n = 6Output : 5Input : n = 3Output : Invalidn must be even.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们需要画n/2条线来连接n个点。当我们画一条线时，我们将点分成两组需要连接的点。每套设备都需要在自身内部连接。下面是同样的循环关系。

Let m = n/2// For each line we draw, we divide points// into two sets such that one set is going// to be connected with i lines and other// with m-i-1 lines.Count(m) = ∑ Count(i) * Count(m-i-1)            where 0 <= i < mCount(0) = 1Total number of ways with n points                = Count(m) = Count(n/2)

如果我们仔细观察上面的复发，它实际上是复发加泰罗尼亚数字因此，任务简化为寻找加泰罗尼亚的n/2个数。下面是基于上述思想的实现。

C++

                         // C++ program to count number of ways to connect n (where n                       
                         // is even) points on a circle such that no two connecting                       
                         // lines cross each other and every point is connected with                       
                         // one other point.                       
                         #include<iostream>                       
                         using                                     namespace                                     std;                       
           
                         // A dynamic programming based function to find nth                       
                         // Catalan number                       
                         unsigned                                     long                                     int                                     catalanDP(unsigned                                     int                                     n)                       
                         {                       
                                                 // Table to store results of subproblems                       
                                                 unsigned                                     long                                     int                                     catalan[n+1];                       
           
                                                 // Initialize first two values in table                       
                                                 catalan[0] = catalan[1] = 1;                       
           
                                                 // Fill entries in catalan[] using recursive formula                       
                                                 for                                     (                                     int                                     i=2; i<=n; i++)                       
                                                 {                       
                                                 catalan[i] = 0;                       
                                                 for                                     (                                     int                                     j=0; j<i; j++)                       
                                                 catalan[i] += catalan[j] * catalan[i-j-1];                       
                                                 }                       
           
                                                 // Return last entry                       
                                                 return                                     catalan[n];                       
                         }                       
           
                         // Returns count of ways to connect n points on a circle                       
                         // such that no two connecting lines cross each other and                       
                         // every point is connected with one other point.                       
                         unsigned                                     long                                     int                                     countWays(unsigned                                     long                                     int                                     n)                       
                         {                       
                                                 // Throw error if n is odd                       
                                                 if                                     (n & 1)                       
                                                 {                       
                                                 cout <<                                     "Invalid"                                     ;                       
                                                 return                                     0;                       
                                                 }                       
           
                                                 // Else return n/2'th Catalan number                       
                                                 return                                     catalanDP(n/2);                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 cout << countWays(6) <<                                     " "                                     ;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count number                       
                         // of ways to connect n (where                       
                         // n is even) points on a circle                       
                         // such that no two connecting                       
                         // lines cross each other and                       
                         // every point is connected with                       
                         // one other point.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         // A dynamic programming                       
                         // based function to find                       
                         // nth Catalan number                       
                         static                                     int                                     catalanDP(                                     int                                     n)                       
                         {                       
                                                 // Table to store                       
                                                 // results of subproblems                       
                                                 int                                     []catalan =                                     new                                     int                                     [n +                                     1                                     ];                       
           
                                                 // Initialize first                       
                                                 // two values in table                       
                                                 catalan[                                     0                                     ] = catalan[                                     1                                     ] =                                     1                                     ;                       
           
                                                 // Fill entries in catalan[]                       
                                                 // using recursive formula                       
                                                 for                                     (                                     int                                     i =                                     2                                     ; i <= n; i++)                       
                                                 {                       
                                                 catalan[i] =                                     0                                     ;                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < i; j++)                       
                                                 catalan[i] += catalan[j] *                       
                                                 catalan[i - j -                                     1                                     ];                       
                                                 }                       
           
                                                 // Return last entry                       
                                                 return                                     catalan[n];                       
                         }                       
           
                         // Returns count of ways to                       
                         // connect n points on a circle                       
                         // such that no two connecting                       
                         // lines cross each other and                       
                         // every point is connected                       
                         // with one other point.                       
                         static                                     int                                     countWays(                                     int                                     n)                       
                         {                       
                                                 // Throw error if n is odd                       
                                                 if                                     (n <                                     1                                     )                       
                                                 {                       
                                                 System.out.println(                                     "Invalid"                                     );                       
                                                 return                                     0                                     ;                       
                                                 }                       
           
                                                 // Else return n/2'th                       
                                                 // Catalan number                       
                                                 return                                     catalanDP(n /                                     2                                     );                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 System.out.println(countWays(                                     6                                     ) +                                     " "                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by akt_mit                       

Python3

                         # Python3 program to count number                       
                         # of ways to connect n (where n                       
                         # is even) points on a circle such                       
                         # that no two connecting lines                       
                         # cross each other and every point                       
                         # is connected with one other point.                       
           
                         # A dynamic programming based                       
                         # function to find nth Catalan number                       
                         def                                     catalanDP(n):                       
                                   
                                                 # Table to store results                       
                                                 # of subproblems                       
                                                 catalan                                     =                                     [                                     1                                     for                                     i                                     in                                     range                                     (n                                     +                                     1                                     )]                       
                                   
                                                 # Fill entries in catalan[]                       
                                                 # using recursive formula                       
                                                 for                                     i                                     in                                     range                                     (                                     2                                     , n                                     +                                     1                                     ):                       
                                                 catalan[i]                                     =                                     0                       
                                                 for                                     j                                     in                                     range                                     (i):                       
                                                 catalan[i]                                     +                                     =                                     (catalan[j]                                     *                       
                                                 catalan[i                                     -                                     j                                     -                                     1                                     ])                       
                                                 # Return last entry                       
                                                 return                                     catalan[n]                       
           
                         # Returns count of ways to connect                       
                         # n points on a circle such that                       
                         # no two connecting lines cross                       
                         # each other and every point is                       
                         # connected with one other point.                       
                         def                                     countWays(n):                       
                                   
                                                 # Throw error if n is odd                       
                                                 if                                     (n &                                     1                                     ):                       
                                                 print                                     (                                     "Invalid"                                     )                       
                                                 return                                     0                       
                                   
                                                 # Else return n/2'th Catalan number                       
                                                 return                                     catalanDP(n                                     /                                     /                                     2                                     )                       
           
                         # Driver Code                       
                         print                                     (countWays(                                     6                                     ))                       
           
                         # This code is contributed                       
                         # by sahilshelangia                       

C#

                         // C# program to count number                       
                         // of ways to connect n (where                       
                         // n is even) points on a circle                       
                         // such that no two connecting                       
                         // lines cross each other and                       
                         // every point is connected with                       
                         // one other point.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // A dynamic programming                       
                         // based function to find                       
                         // nth Catalan number                       
                         static                                     int                                     catalanDP(                                     int                                     n)                       
                         {                       
                                                 // Table to store                       
                                                 // results of subproblems                       
                                                 int                                     []catalan =                                     new                                     int                                     [n + 1];                       
           
                                                 // Initialize first                       
                                                 // two values in table                       
                                                 catalan[0] = catalan[1] = 1;                       
           
                                                 // Fill entries in catalan[]                       
                                                 // using recursive formula                       
                                                 for                                     (                                     int                                     i = 2; i <= n; i++)                       
                                                 {                       
                                                 catalan[i] = 0;                       
                                                 for                                     (                                     int                                     j = 0; j < i; j++)                       
                                                 catalan[i] += catalan[j] *                       
                                                 catalan[i - j - 1];                       
                                                 }                       
           
                                                 // Return last entry                       
                                                 return                                     catalan[n];                       
                         }                       
           
                         // Returns count of ways to                       
                         // connect n points on a circle                       
                         // such that no two connecting                       
                         // lines cross each other and                       
                         // every point is connected                       
                         // with one other point.                       
                         static                                     int                                     countWays(                                     int                                     n)                       
                         {                       
                                                 // Throw error if n is odd                       
                                                 if                                     (n < 1)                       
                                                 {                       
                                                 Console.WriteLine(                                     "Invalid"                                     );                       
                                                 return                                     0;                       
                                                 }                       
           
                                                 // Else return n/2'th                       
                                                 // Catalan number                       
                                                 return                                     catalanDP(n / 2);                       
                         }                       
           
                         // Driver Code                       
                         static                                     public                                     void                                     Main ()                       
                         {                       
                                                 Console.WriteLine(countWays(6) +                                     " "                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by M_kit                       

PHP

                         <?php                       
                         // PHP program to count number of                       
                         // ways to connect n (where n is                       
                         // even) points on a circle such                       
                         // that no two connecting lines                       
                         // cross each other and every                       
                         // point is connected with one                       
                         // other point.                       
           
                         // A dynamic programming based                       
                         // function to find nth Catalan number                       
                         function                                     catalanDP(                                     $n                                     )                       
                         {                       
                                                 // Table to store results                       
                                                 // of subproblems Initialize                       
                                                 // first two values in table                       
                                                 $catalan                                     [0] =                                     $catalan                                     [1] = 1;                       
           
                                                 // Fill entries in catalan[]                       
                                                 // using recursive formula                       
                                                 for                                     (                                     $i                                     = 2;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 $catalan                                     [                                     $i                                     ] = 0;                       
                                                 for                                     (                                     $j                                     = 0;                                     $j                                     <                                     $i                                     ;                                     $j                                     ++)                       
                                                 $catalan                                     [                                     $i                                     ] +=                                     $catalan                                     [                                     $j                                     ] *                       
                                                 $catalan                                     [                                     $i                                     -                                     $j                                     - 1];                       
                                                 }                       
           
                                                 // Return last entry                       
                                                 return                                     $catalan                                     [                                     $n                                     ];                       
                         }                       
           
                         // Returns count of ways to connect                       
                         // n points on a circle such that                       
                         // no two connecting lines cross                       
                         // each other and every point is                       
                         // connected with one other point.                       
                         function                                     countWays(                                     $n                                     )                       
                         {                       
                         // Throw error if n is odd                       
                         if                                     (                                     $n                                     & 1)                       
                         {                       
                                                 echo                                     "Invalid"                                     ;                       
                                                 return                                     0;                       
                         }                       
           
                         // Else return n/2'th                       
                         // Catalan number                       
                         return                                     catalanDP(                                     $n                                     / 2);                       
                         }                       
           
                         // Driver Code                       
                         echo                                     countWays(6) ,                                     " "                                     ;                       
           
                         // This code is contributed by aj_36                       
                         ?>                       

Javascript

                         <script>                       
                         // javascript program to count number of                       
                         // ways to connect n (where n is                       
                         // even) points on a circle such                       
                         // that no two connecting lines                       
                         // cross each other and every                       
                         // point is connected with one                       
                         // other point.                       
           
                         // A dynamic programming based                       
                         // function to find nth Catalan number                       
                         function                                     catalanDP(n)                       
                         {                       
                                                 // Table to store results                       
                                                 // of subproblems Initialize                       
                                                 // first two values in table                       
                                                 let catalan = []                       
                                                 catalan[0] = catalan[1] = 1;                       
           
                                                 // Fill entries in catalan[]                       
                                                 // using recursive formula                       
                                                 for                                     (let i = 2; i <= n; i++)                       
                                                 {                       
                                                 catalan[i] = 0;                       
                                                 for                                     (let j = 0; j < i; j++)                       
                                                 catalan[i] += catalan[j] *                       
                                                 catalan[i - j - 1];                       
                                                 }                       
           
                                                 // Return last entry                       
                                                 return                                     catalan[n];                       
                         }                       
           
                         // Returns count of ways to connect                       
                         // n points on a circle such that                       
                         // no two connecting lines cross                       
                         // each other and every point is                       
                         // connected with one other point.                       
                         function                                     countWays(n)                       
                         {                       
                         // Throw error if n is odd                       
                         if                                     (n & 1)                       
                         {                       
                                                 document.write(                                     "Invalid"                                     );                       
                                                 return                                     0;                       
                         }                       
           
                         // Else return n/2'th                       
                         // Catalan number                       
                         return                                     catalanDP(n / 2);                       
                         }                       
           
                         // Driver Code                       
                         document.write(countWays(6) +                                     " "                                     );                       
           
                         // This code is contributed by _saurabh_jaiswal                       
                         </script>                       

输出：

时间复杂性： O（n） ^2. ) 辅助空间： O（n）本文由 希瓦姆·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

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

THE END

技术文章