資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中計算配對數，一個人最多與另一個人配對
假設在一個程式設計競賽中有 N 個參與者。目標是找到當一個人最多隻能與另一個人配對時可能的配對數。因此，一個配對最多包含 2 個參與者。參與者也可以單獨參加。
我們可以使用遞迴來解決這個問題，其中配對數為：
當 n=0 或 1 時，計數=1（只剩下一個人）
如果一個人保持單身，n 減少到 n-1
現在對於剩下的配對，剩下的人數 = n-2
計數=makePairs(p-1) + (p-1)*makePairs(p-2);
讓我們用例子來理解。
輸入 - 人數=3
輸出 - 配對方式的計數 - 4
解釋 -
If three persons are a,b,c then ways of pairing could be: (a,b), (c) → c remained single (a,c), (b) → b remained single (b,c), (a) → a remained single (a),(b),(c) → all remained single Total ways = 4
輸入 - 人數=2
輸出 - 配對方式的計數 - 2
解釋 -
I persons are a,b then ways of pairing could be − (a,b) → both paired (a),(b) → both remained single Total ways = 2
下面程式中使用的方案如下
我們使用一個整數 person 來儲存參與者的數量。
函式 makePairs(int p) 以人數作為輸入，並返回他們可以配對的方式的數量。
將初始計數設為 0。
如果 p=0 或 1，則唯一的方式是 1 保持單身。
否則，一個人可以選擇保持單身，然後剩下的 (p-1) 將使用 (p1)*makePairs(p-2) 找到配對。
最後返回計數的值作為最終配對方式的數量。
示例
#include<iostream>
using namespace std;
int makePairs(int p){
int count=0;
// Base condition
if (p==0 || p==1)
{ count=1; }
else
{ count=makePairs(p-1) + (p-1)*makePairs(p-2); }
return count;
}
int main(){
int persons = 5;
cout <<"Number of ways to make pair ( or remain single ):"<<makePairs(persons);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Number of ways to make pair ( or remain single ): 26
更新於: 2020-08-29
201 次瀏覽
廣告