資料結構
網路
關係資料庫管理系統
作業系統
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
更新時間： 2020-06-17
587 次瀏覽
廣告