递归法求组合数C(m,n)

假设这样一个数组：

1　　2　　3　　4　　5

n=5

若 m=3 也就是要求C(3,5)

首先先选第一个数 1

那么剩下的工作就是在2-5之间选择2个数

如果我们没有选择第一个数选第二个数2

那么剩下的工作就是在3-5之间选择2个数

这样就很好递归了只需要记录下当前已经选了几个数当前选的最后一个数是什么递归即可

#include<bits/stdc++.h>

using namespace std;

int sum=0; //记录总数

void digui(int *a,int *b,int t,int now,int n,int m)
{
    int i;
    if(t==m)   //t记录已经选择了几个数 若=m，输出结果
    {
        for(i=0;i<m;i++)
        cout<<b[i]<<" ";
        cout<<endl;
        sum++;
        return;
    }
    else
    {
        for(i=now;i<=n-(m-t);i++)  //now代表现在可以从哪个数选起
        {
            b[t]=a[i];
            digui(a,b,t+1,i+1,n,m);
        }
    }
}


int main()
{
    int a[10],b[10],i,n,m;   //a为原数组 b存储结果 
    cin>>n>>m;
    for(i=0;i<n;i++)
    cin>>a[i];
    digui(a,b,0,0,n,m);
    cout<<sum<<endl;
}

原文链接: https://www.cnblogs.com/dyhaohaoxuexi/p/10915619.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/295541

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

递归法求组合数C(m,n)

相关推荐