数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究好友结对问题
在一个组中，有 n 个朋友。每个人可以选择保持单身或与其他朋友配对。求解朋友保持单身或配对的所有方法数。
如果一对朋友是 p 和 q，则 (p，q) 或 (q，p) 相同。
对于一个 n 人组，设 f(n) 为他们可以配对或保持单身的方案数。那么，第 n 个人要么保持单身，要么配对。如果第 n 个人单身，那么我们对 (n - 1) 个朋友进行递归。如果第 n 个人与剩下的 (n-1) 个朋友中任意一个人配对，那么我们进行递归 (n-1) *f(n-2)。
输入和输出
Input: The number of friends. Say 5. Output: The possible way to pair them. Here the answer is 26.
算法
countPairs(n)
输入：朋友人数。
输出：配对 n 个朋友的方法数。
Begin define pair array of size n + 1 pair[0] := 0, pair[1] := 1 and pair[2] := 2 for i in range 3 to n, do pair[i] := pair[i-1] + (i+1)*pairs[i-2] done pair[n] End
示例
#include <iostream>
using namespace std;
int countPairs(int n) {
int pairs[n + 1]; //number of pairs for ith number
//for number 0 to 2, there are 0 to 2 possible combination
pairs[0] = 0;
pairs[1] = 1;
pairs[2] = 2;
for (int i = 3; i <= n; i++) //fill array for 3 to n numbers
pairs[i] = pairs[i-1] + (i-1) * pairs[i-2];
return pairs[n];
}
int main() {
int n;
cout << "Enter numbers: "; cin >> n;
cout << "Number of ways to pair "<<n<<" friends: " << countPairs(n);
}输出
Enter numbers: 5 Number of ways to pair 5 friends: 26
更新于： 17-06-2020
587 次浏览
广告