握手次数，每个人只握一次手

假设你在一个社交聚会中。如果你只握手一次，你能计算出你能做多少次握手吗？这个问题可能让你感到有趣。这个问题可以通过使用排列组合的数学方法来解决。然而，数学运算可能会耗费时间。

在本文中，我们将讨论如何使用C++解决这个问题。我们将探讨不同的方法，包括数学公式、递归和其他组合技术。

输入输出场景

Suppose you have N number of people in a gathering. You want to calculate the number of handshakes possible such that a person shakes hands only once.

Input: N = 16
Output: 120
Input: N = 11
Output: 55

Using the Formula for Handshakes

The formula for finding the number of handshakes in a gathering of N people is −

No. of handshakes = N *(N-1) /2

Each of the N people will shake the hands with (N-1) individuals (excluding the person itself) and the handshakes between two individuals is not counted twice.

For Example, if the number of individuals is 14. Then, number of handshakes are

Handshakes = 14 * (14 - 1)/ 2
           = 14 * 13 / 2
           = 182/2
           = 91

Example

在下面的示例中，我们使用的是计算握手次数的公式。在这里，我们只需使用数学运算符，以聚会上的人数作为输入。

#include <iostream>
using namespace std;

int count(int N) {
   // Formula: N * (N-1) / 2
   return (N * (N - 1)) / 2;
}

int main() {
   int totalIndividuals= 10;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

输出

Number of handshakes: 45

使用for循环

在这里，我们通过从1迭代到‘N-1’并将所有值相加来计算握手的次数。

Example

#include <iostream>
using namespace std;

int count(int N) {
   int numHandshakes = 0;

   for (int x = 1; x < N; x++) {
      numHandshakes += x;
   }

   return numHandshakes;
}

int main() {
   int totalIndividuals = 10;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

输出

Number of handshakes: 45

使用递归

We can use recursion for calculating the number of handshakes. By doing so, we divide the problem into smaller problems by considering one person at a time.

Example

#include <iostream>
using namespace std;

int count(int N) {
   if (N <= 1)
      return 0;
   return (N - 1) + count(N - 1);
}

int main() {
   int totalIndividuals = 20;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

输出

Number of handshakes: 190

使用While循环

在这里，我们使用了一个while循环，它具有一个递减的计数器来计算握手的次数。循环从总人数开始，然后在每次迭代后逐个减少计数器。

Example

#include <iostream>
using namespace std;

int count(int N) {
   int numHandshakes = 0;

   while (N > 1) {
      numHandshakes += N - 1;
      N--;
   }

   return numHandshakes;
}

int main() {
   int totalIndividuals = 16;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

输出

Number of handshakes: 120

使用动态规划

Here, we have used dynamic programming for the calculation.

• Initialize a ‘dp’ vector to store the number of handshakes.

• Iterate from 1 to N. In each iteration, it declares the number of handshakes as the sum of previous handshakes and the present number of individual minus 1.

Example

#include <iostream>
#include <vector>
using namespace std;

int count(int N) {
   std::vector<int> dp(N + 1);
   dp[0] = 0;

   for (int x = 1; x <= N; x++) {
      dp[x] = dp[x - 1] + (x - 1);
   }

   return dp[N];
}

int main() {
   int totalIndividuals = 21;
   int numHandshakes = count(totalIndividuals);
   std::cout << "Number of handshakes: " << numHandshakes << std::endl;
   return 0;
}

输出

Number of handshakes: 210

注意 − 这种方法有助于避免冗余计算。在这里，我们将先前计算的值存储在“dp”向量中，您可以随时访问并重复使用它。这使得算法高效，并且减少了总体计算时间。

Conclusion

我们已经讨论了各种方法，可以计算出一个人只握手一次的握手次数。这些方法包括使用数学运算符进行公式计算，使用for循环，递归，while循环和动态规划。每种方法都有其优点。动态规划是一种更系统和有组织的解决问题的方法。根据具体要求，您可以使用任何一种方法。

以上是握手次数，每个人只握一次手的详细内容。更多信息请关注PHP中文网其他相关文章！