每人只握手一次的情況下，握手次數

---

假設你參加一個社交聚會。如果你只和每人握一次手，你能計算出你能握多少次手嗎？這個問題對你來說可能很有趣。這可以用排列組合的數學方法來解決。然而，數學運算可能很費時。

在這篇文章中，我們將討論如何使用 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 迴圈和動態規劃。每種方法都有其自身的優勢。動態規劃是解決問題的一種更系統和組織化的方法。你可以根據具體需求使用任何一種方法。