握手次数，使一个人只握手一次-yiteyi-C++库

聚会上有N个人。找出握手的总次数，这样一个人只能握手一次。

null

例如：

Input : 5Output : 10Input : 9Output : 36

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

我们可以在这个问题中看到递归的本质。

// n-th person has (n-1) choices and after// n-th person chooses a person, problem// recurs for n-1.handshake(n) = (n-1) + handshake(n-1)// Base casehandshake(0) = 0

图片[1]-握手次数，使一个人只握手一次-yiteyi-C++库

下面是上述递归公式的实现。

C++

                         // Recursive C++ program to count total                       
                         // number of handshakes when a person                       
                         // can shake hand with only one.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find all possible handshakes                       
                         int                                     handshake(                                     int                                     n)                       
                         {                       
                                   
                                                 // When n becomes 0 that means all the                       
                                                 // persons have done handshake with other                       
                                                 if                                     (n == 0)                       
                                                 return                                     0;                       
                                                 else                       
                                                 return                                     (n - 1) + handshake(n - 1);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 9;                       
                                                 cout <<                                     " "                                     << handshake(n);                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by shivanisinghss2110                       

C

                         // Recursive C program to count total                       
                         // number of  handshakes when a person                       
                         // can shake hand with only one.                       
                         #include <stdio.h>                       
           
                         // function to find all possible handshakes                       
                         int                                     handshake(                                     int                                     n)                       
                         {                       
                                                 // when n becomes 0 that means all the                       
                                                 // persons have done handshake with other                       
                                                 if                                     (n == 0)                       
                                                 return                                     0;                       
                                                 else                       
                                                 return                                     (n - 1) + handshake(n - 1);                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     n = 9;                       
                                                 printf                                     (                                     "%d"                                     , handshake(n));                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Recursive Java program to                       
                         // count total number of                       
                         // handshakes when a person                       
                         // can shake hand with only one.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         // function to find all                       
                         // possible handshakes                       
                         static                                     int                                     handshake(                                     int                                     n)                       
                         {                       
                                                 // when n becomes 0 that                       
                                                 // means all the persons                       
                                                 // have done handshake                       
                                                 // with other                       
                                                 if                                     (n ==                                     0                                     )                       
                                                 return                                     0                                     ;                       
                                                 else                       
                                                 return                                     (n -                                     1                                     ) + handshake(n -                                     1                                     );                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     n =                                     9                                     ;                       
                                                 System.out.print(handshake(n));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by chandan_jnu                       

Python3

                         # Recursive Python program                       
                         # to count total number of                       
                         # handshakes when a person                       
                         # can shake hand with only one.                       
           
                         # function to find all                       
                         # possible handshakes                       
                         def                                     handshake(n):                       
           
                                                 # when n becomes 0 that means                       
                                                 # all the persons have done                       
                                                 # handshake with other                       
                                                 if                                     (n                                     =                                     =                                     0                                     ):                       
                                                 return                                     0                       
                                                 else                                     :                       
                                                 return                                     (n                                     -                                     1                                     )                                     +                                     handshake(n                                     -                                     1                                     )                       
           
                         # Driver Code                       
                         n                                     =                                     9                       
                         print                                     (handshake(n))                       
           
                         # This code is contributed                       
                         # by Shivi_Aggarwal                       

C#

                         // Recursive C# program to                       
                         // count total number of                       
                         // handshakes when a person                       
                         // can shake hand with only one.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                         // function to find all                       
                         // possible handshakes                       
                         static                                     int                                     handshake(                                     int                                     n)                       
                         {                       
                                                 // when n becomes 0 that                       
                                                 // means all the persons                       
                                                 // have done handshake                       
                                                 // with other                       
                                                 if                                     (n == 0)                       
                                                 return                                     0;                       
                                                 else                       
                                                 return                                     (n - 1) + handshake(n - 1);                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main (String []args)                       
                         {                       
                                                 int                                     n = 9;                       
                                                 Console.WriteLine(handshake(n));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by Arnab Kundu                       

PHP

                         <?php                       
                         // Recursive PHP program to                       
                         // count total number of                       
                         // handshakes when a person                       
                         // can shake hand with only one.                       
           
                         // function to find all                       
                         // possible handshakes                       
                         function                                     handshake(                                     $n                                     )                       
                         {                       
                                                 // when n becomes 0 that means                       
                                                 // all the persons have done                       
                                                 // handshake with other                       
                                                 if                                     (                                     $n                                     == 0)                       
                                                 return                                     0;                       
                                                 else                       
                                                 return                                     (                                     $n                                     - 1) + handshake(                                     $n                                     - 1);                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 9;                       
                         echo                                     (handshake(                                     $n                                     ));                       
           
                         // This code is contributed                       
                         // by Shivi_Aggarwal                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Recursive JavaScript program to                       
                                                 // count total number of                       
                                                 // handshakes when a person                       
                                                 // can shake hand with only one.                       
                                                 // function to find all                       
                                                 // possible handshakes                       
                                                 function                                     handshake(n) {                       
                                                 // when n becomes 0 that                       
                                                 // means all the persons                       
                                                 // have done handshake                       
                                                 // with other                       
                                                 if                                     (n === 0)                       
                                                 return                                     0;                       
                                                 else                       
                                                 return                                     n - 1 + handshake(n - 1);                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 var                                     n = 9;                       
                                                 document.write(handshake(n));                       
                         </script>                       

输出：

我们可以想出一个解决办法 直接公式 通过扩展递归。

handshake(n) = (n-1) + handshake(n-1)             = (n-1) + (n-2) + handshake(n-2)             = (n-1) + (n-2) + .... 1 + 0             = n * (n - 1)/2

C++

                         // Recursive CPP program to count total                       
                         // number of  handshakes when a person                       
                         // can shake hand with only one.                       
                         #include <stdio.h>                       
           
                         // function to find all possible handshakes                       
                         int                                     handshake(                                     int                                     n)                       
                         {                       
                                                 return                                     n * (n - 1)/2;                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     n = 9;                       
                                                 printf                                     (                                     "%d"                                     , handshake(n));                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Recursive Java program to                       
                         // count total number of                       
                         // handshakes when a person                       
                         // can shake hand with only one.                       
                         class                                     GFG                       
                         {                       
           
                         // function to find all                       
                         // possible handshakes                       
                         static                                     int                                     handshake(                                     int                                     n)                       
                         {                       
                                                 return                                     n * (n -                                     1                                     ) /                                     2                                     ;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String args[])                       
                         {                       
                                                 int                                     n =                                     9                                     ;                       
                                                 System.out.println(handshake(n));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by Arnab Kundu                       

Python3

                         # Recursive Python program                       
                         # to count total number of                       
                         # handshakes when a person                       
                         # can shake hand with only one.                       
           
                         # function to find all                       
                         # possible handshakes                       
                         def                                     handshake(n):                       
                                   
                                                 return                                     int                                     (n                                     *                                     (n                                     -                                     1                                     )                                     /                                     2                                     )                       
           
                         # Driver Code                       
                         n                                     =                                     9                       
                         print                                     (handshake(n))                       
                                   
                         # This code is contributed                       
                         # by Shivi_Aggarwal                       

C#

                         // Recursive C# program to                       
                         // count total number of                       
                         // handshakes when a person                       
                         // can shake hand with only one.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // function to find all                       
                         // possible handshakes                       
                         static                                     int                                     handshake(                                     int                                     n)                       
                         {                       
                                                 return                                     n * (n - 1) / 2;                       
                         }                       
           
                         // Driver code                       
                         static                                     public                                     void                                     Main ()                       
                         {                       
                                                 int                                     n = 9;                       
                                                 Console.WriteLine(handshake(n));                       
                         }                       
                         }                       
           
                         // This code is contributed by Sachin                       

PHP

                         <?php                       
                         // Recursive PHP program to                       
                         // count total number of                       
                         // handshakes when a person                       
                         // can shake hand with only one.                       
           
                         // function to find all                       
                         // possible handshakes                       
                         function                                     handshake(                                     $n                                     )                       
                         {                       
                                                 return                                     $n                                     * (                                     $n                                     - 1) / 2;                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 9;                       
                         echo                                     (handshake(                                     $n                                     ));                       
           
                         // This code is contributed                       
                         // by Shivi_Aggarwal                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Recursive Javascript program to                       
                         // count total number of                       
                         // handshakes when a person                       
                         // can shake hand with only one.                       
           
                         // Function to find all                       
                         // possible handshakes                       
                         function                                     handshake(n)                       
                         {                       
                                                 return                                     n * parseInt((n - 1) / 2, 10);                       
                         }                       
           
                         // Driver code                       
                         let n = 9;                       
           
                         document.write(handshake(n));                       
           
                         // This code is contributed by rameshtravel07                       
           
                         </script>                       

输出：

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

THE END

技术文章