每人只握手一次的情况下，握手次数

---

假设你参加一个社交聚会。如果你只和每人握一次手，你能计算出你能握多少次手吗？这个问题对你来说可能很有趣。这可以用排列组合的数学方法来解决。然而，数学运算可能很费时。

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

输入输出场景

假设在一个聚会上你有 N 个人。你想计算出每人只握手一次的情况下可能的握手次数。

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

使用握手公式

在 N 个人的聚会中，求握手次数的公式是：

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

N 个人中的每一个人都会与 (N-1) 个人握手（不包括自己），并且两个人之间的握手不会被计算两次。

例如，如果人数是 14，那么握手次数是

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

示例

在下面的例子中，我们使用计算握手次数的公式。在这里，我们简单地使用数学运算符，并将聚会中的人数作为输入。

#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' 并将所有值相加来计算握手次数。

示例

#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

使用递归

我们可以使用递归来计算握手次数。这样做，我们通过一次考虑一个人来将问题分解成更小的问题。

示例

#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 循环来计算握手次数。循环从总人数开始，然后在每次迭代后将计数器减少一个。

示例

#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

使用动态规划

在这里，我们使用了动态规划进行计算。

• 初始化一个 'dp' 向量来存储握手次数。

• 从 1 迭代到 N。在每次迭代中，它将握手次数声明为先前握手次数和当前人数减 1 的总和。

示例

#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' 向量中，你可以随时访问和重用它。这使得算法更高效。同时也减少了整体计算时间。

结论

我们讨论了各种方法，通过这些方法我们可以计算每人只握手一次的握手次数。这些方法包括使用公式的数学运算符、使用 for 循环、递归、while 循环和动态规划。每种方法都有其自身的优势。动态规划是解决问题的一种更系统和组织化的方法。你可以根据具体需求使用任何一种方法。