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 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告