假设你在一个社交聚会中。如果你只握手一次，你能计算出你能做多少次握手吗？这个问题可能让你感到有趣。这个问题可以通过使用排列组合的数学方法来解决。然而，数学运算可能会耗费时间。
在本文中，我们将讨论如何使用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’并将所有值相加来计算握手的次数。
Shopilex是一个多功能、易扩展的开源电子商务系统，是面向独立卖家的网店系统，同时,Shopilex是基于GPL开源协议的PHP网店系统,是国内目前为数不多的真正做到开源的免费网店系统.另外,Shopilex采用了MVC架构开发,代码结构清晰,易维护,二次开发更简单. Shopilex 2.0 使用了全新的界面设计,更简洁,后台使用更易上手.功能特性:良好的用户体验,更简洁的单页结账流程;更人
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循环和动态规划。每种方法都有其优点。动态规划是一种更系统和有组织的解决问题的方法。根据具体要求，您可以使用任何一种方法。
