假设你在一个社交聚会中。如果你只握手一次,你能计算出你能做多少次握手吗?这个问题可能让你感到有趣。这个问题可以通过使用排列组合的数学方法来解决。然而,数学运算可能会耗费时间。
在本文中,我们将讨论如何使用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
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
在下面的示例中,我们使用的是计算握手次数的公式。在这里,我们只需使用数学运算符,以聚会上的人数作为输入。
#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
在这里,我们通过从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
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.
#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循环,它具有一个递减的计数器来计算握手的次数。循环从总人数开始,然后在每次迭代后逐个减少计数器。
#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.
#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循环和动态规划。每种方法都有其优点。动态规划是一种更系统和有组织的解决问题的方法。根据具体要求,您可以使用任何一种方法。
以上是握手次数,每个人只握一次手的详细内容。更多信息请关注PHP中文网其他相关文章!