当一个人最多只能和一个人结对时，计算结对数-yiteyi-C++库

考虑编码竞赛 Geeksforgek的实践 .现在他们的 N 参加比赛的不同参与者。一名参与者最多可与另一名参与者配对。我们需要数一数 N 参与编码竞赛的参与者。 例如：

null

Input : n = 2Output : 22 shows that either both participant can pair themselves in one way or both of them can remain single.Input : n = 3 Output : 4One way : Three participants remain singleThree More Ways : [(1, 2)(3)], [(1), (2,3)]and [(1,3)(2)]

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

1）每个参与者可以与另一个参与者配对，也可以保持单身。 2）让我们考虑 第X位 参与者，他可以保持单身，也可以他可以和来自美国的人结对 [1，x-1] .

C++

                         // Number of ways in which participant can take part.                       
                         #include<iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     numberOfWays(                                     int                                     x)                       
                         {                       
                                                 // Base condition                       
                                                 if                                     (x==0 || x==1)                       
                                                 return                                     1;                       
           
                                                 // A participant can choose to consider                       
                                                 // (1) Remains single. Number of people                       
                                                 //     reduce to (x-1)                       
                                                 // (2) Pairs with one of the (x-1) others.                       
                                                 //     For every pairing, number of people                       
                                                 //     reduce to (x-2).                       
                                                 else                       
                                                 return                                     numberOfWays(x-1) +                       
                                                 (x-1)*numberOfWays(x-2);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     x = 3;                       
                                                 cout << numberOfWays(x) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Number of ways in which                       
                         // participant can take part.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
           
                         static                                     int                                     numberOfWays(                                     int                                     x)                       
                         {                       
                                                 // Base condition                       
                                                 if                                     (x==                                     0                                     || x==                                     1                                     )                       
                                                 return                                     1                                     ;                       
           
                                                 // A participant can choose to consider                       
                                                 // (1) Remains single. Number of people                       
                                                 //     reduce to (x-1)                       
                                                 // (2) Pairs with one of the (x-1) others.                       
                                                 //     For every pairing, number of people                       
                                                 //     reduce to (x-2).                       
                                                 else                       
                                                 return                                     numberOfWays(x-                                     1                                     ) +                       
                                                 (x-                                     1                                     )*numberOfWays(x-                                     2                                     );                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main (String[] args) {                       
                         int                                     x =                                     3                                     ;                       
                         System.out.println( numberOfWays(x));                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

Python3

                         # Python program to find Number of ways                       
                         # in which participant can take part.                       
           
                         # Function to calculate number of ways.                       
                         def                                     numberOfWays (x):                       
           
                                                 # Base condition                       
                                                 if                                     x                                     =                                     =                                     0                                     or                                     x                                     =                                     =                                     1                                     :                       
                                                 return                                     1                       
                                   
                                                 # A participant can choose to consider                       
                                                 # (1) Remains single. Number of people                       
                                                 # reduce to (x-1)                       
                                                 # (2) Pairs with one of the (x-1) others.                       
                                                 # For every pairing, number of people                       
                                                 # reduce to (x-2).                       
                                                 else                                     :                       
                                                 return                                     (numberOfWays(x                                     -                                     1                                     )                                     +                       
                                                 (x                                     -                                     1                                     )                                     *                                     numberOfWays(x                                     -                                     2                                     ))                       
           
                         # Driver code                       
                         x                                     =                                     3                       
                         print                                     (numberOfWays(x))                       
           
                         # This code is contributed by "Sharad_Bhardwaj"                       

C#

                         // Number of ways in which                       
                         // participant can take part.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     numberOfWays(                                     int                                     x)                       
                                                 {                       
                                   
                                                 // Base condition                       
                                                 if                                     (x == 0 || x == 1)                       
                                                 return                                     1;                       
                                   
                                                 // A participant can choose to                       
                                                 // consider (1) Remains single.                       
                                                 // Number of people reduce to                       
                                                 // (x-1) (2) Pairs with one of                       
                                                 // the (x-1) others. For every                       
                                                 // pairing, number of people                       
                                                 // reduce to (x-2).                       
                                                 else                       
                                                 return                                     numberOfWays(x - 1) +                       
                                                 (x - 1) * numberOfWays(x - 2);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     x = 3;                       
                                   
                                                 Console.WriteLine(numberOfWays(x));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // Number of ways in which                       
                         // participant can take part.                       
           
                         function                                     numberOfWays(                                     $x                                     )                       
                         {                       
                                                 // Base condition                       
                                                 if                                     (                                     $x                                     == 0 ||                                     $x                                     == 1)                       
                                                 return                                     1;                       
           
                                                 // A participant can choose                       
                                                 // to consider (1) Remains single.                       
                                                 // Number of people reduce to (x-1)                       
                                                 // (2) Pairs with one of the (x-1)                       
                                                 // others. For every pairing, number                       
                                                 // of peopl reduce to (x-2).                       
                                                 else                       
                                                 return                                     numberOfWays(                                     $x                                     - 1) +                       
                                                 (                                     $x                                     - 1) * numberOfWays(                                     $x                                     - 2);                       
                         }                       
           
                         // Driver code                       
                         $x                                     = 3;                       
                         echo                                     numberOfWays(                                     $x                                     );                       
           
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
                         // Number of ways in which                       
                         // participant can take part.                       
           
                                                 function                                     numberOfWays(x)                       
                                                 {                       
                                   
                                                 // Base condition                       
                                                 if                                     (x == 0 || x == 1)                       
                                                 return                                     1;                       
           
                                                 // A participant can choose to consider                       
                                                 // (1) Remains single. Number of people                       
                                                 // reduce to (x-1)                       
                                                 // (2) Pairs with one of the (x-1) others.                       
                                                 // For every pairing, number of people                       
                                                 // reduce to (x-2).                       
                                                 else                       
                                                 return                                     numberOfWays(x - 1) + (x - 1) * numberOfWays(x - 2);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 var                                     x = 3;                       
                                                 document.write(numberOfWays(x));                       
           
                         // This code is contributed by gauravrajput1                       
                         </script>                       

输出：

由于存在重叠的子问题，我们可以使用动态规划 .

C++

                         // Number of ways in which participant can take part.                       
                         #include<iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     numberOfWays(                                     int                                     x)                       
                         {                       
                                                 int                                     dp[x+1];                       
                                                 dp[0] = dp[1] = 1;                       
           
                                                 for                                     (                                     int                                     i=2; i<=x; i++)                       
                                                 dp[i] = dp[i-1] + (i-1)*dp[i-2];                       
           
                                                 return                                     dp[x];                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     x = 3;                       
                                                 cout << numberOfWays(x) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Number of ways in which                       
                         // participant can take part.                       
                         import                                     java.io.*;                       
                         class                                     GFG {                       
           
                         static                                     int                                     numberOfWays(                                     int                                     x)                       
                         {                       
                                                 int                                     dp[] =                                     new                                     int                                     [x+                                     1                                     ];                       
                                                 dp[                                     0                                     ] = dp[                                     1                                     ] =                                     1                                     ;                       
           
                                                 for                                     (                                     int                                     i=                                     2                                     ; i<=x; i++)                       
                                                 dp[i] = dp[i-                                     1                                     ] + (i-                                     1                                     )*dp[i-                                     2                                     ];                       
           
                                                 return                                     dp[x];                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main (String[] args) {                       
                         int                                     x =                                     3                                     ;                       
                         System.out.println(numberOfWays(x));                       
                                   
                                                 }                       
                         }                       
                         // This code is contributed by vipinyadav15799                       

Python3

                         # Python program to find Number of ways                       
                         # in which participant can take part.                       
           
                         # Function to calculate number of ways.                       
                         def                                     numberOfWays (x):                       
           
                                                 dp                                     =                                     []                       
                                                 dp.append(                                     1                                     )                       
                                                 dp.append(                                     1                                     )                       
                                                 for                                     i                                     in                                     range                                     (                                     2                                     ,x                                     +                                     1                                     ):                       
                                                 dp.append(dp[i                                     -                                     1                                     ]                                     +                                     (i                                     -                                     1                                     )                                     *                                     dp[i                                     -                                     2                                     ])                       
                                                 return                                     (dp[x])                       
                                   
           
                         # Driver code                       
                         x                                     =                                     3                       
                         print                                     (numberOfWays(x))                       
           
                         # This code is contributed by "Sharad_Bhardwaj"                       

C#

                         // Number of ways in which                       
                         // participant can take part.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     numberOfWays(                                     int                                     x)                       
                                                 {                       
                                                 int                                     []dp =                                     new                                     int                                     [x+1];                       
                                                 dp[0] = dp[1] = 1;                       
                                   
                                                 for                                     (                                     int                                     i = 2; i <= x; i++)                       
                                                 dp[i] = dp[i - 1] +                       
                                                 (i - 1) * dp[i - 2];                       
                                   
                                                 return                                     dp[x];                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     x = 3;                       
                                   
                                                 Console.WriteLine(numberOfWays(x));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program for Number of ways                       
                         // in which participant can take part.                       
           
                         function                                     numberOfWays(                                     $x                                     )                       
                         {                       
                                   
                                                 $dp                                     [0] = 1;                       
                                                 $dp                                     [1] = 1;                       
                                                 for                                     (                                     $i                                     = 2;                                     $i                                     <=                                     $x                                     ;                                     $i                                     ++)                       
                                                 $dp                                     [                                     $i                                     ] =                                     $dp                                     [                                     $i                                     - 1] + (                                     $i                                     - 1) *                       
                                                 $dp                                     [                                     $i                                     - 2];                       
           
                                                 return                                     $dp                                     [                                     $x                                     ];                       
                         }                       
           
                                                 // Driver code                       
                                                 $x                                     = 3;                       
                                                 echo                                     numberOfWays(                                     $x                                     ) ;                       
                                   
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
                         // Number of ways in which                       
                         // participant can take part.                       
           
                                                 function                                     numberOfWays( x)                       
                                                 {                       
                                                 let dp = Array(x + 1).fill(0);                       
                                                 dp[0] = dp[1] = 1;                       
           
                                                 for                                     ( i = 2; i <= x; i++)                       
                                                 dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];                       
           
                                                 return                                     dp[x];                       
                                                 }                       
           
                                                 // Driver code                       
                                                 let x = 3;                       
                                                 document.write(numberOfWays(x));                       
           
                         // This code is contributed by gauravrajput1                       
                         </script>                       

输出：

本文由 尼金古·阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章