Question

c++编程 从n个数中选出m个数进行组合

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

void f(int *a,int n,int m,vector<int> result);
int main()
{
int num,n,m;
int i;
cin>>num;
while(num--)
{
cin>>n>>m;
int *a=new int[n];
for(i=0;i<n;i++)
a[i]=i+1;
vector<int> result;
f(a,n,m,result);
}
return 0;
}
void f(int *a,int n,int m,vector<int> result)
{
int i,j,temp;
for(i=0;i<n;i++)
{
temp=a[i];
if(a[i]!=0)
{
result.push_back(a[i]);
a[i]=0;
if(m>1)
f(a,n,m-1,result);
else
{
for(j=0;j<result.size();j++)
cout<<result[j];
cout<<endl;
}
result.pop_back();
}
a[i]=temp;
}
}
求大神解释下此代码

Answer 1

　　编程思路：

　　从n个数中选出m个数进行组合（n>m)可以采用递归的方式解决

　　先从n个数中选一个数出来，然后在剩下的n-1个数当中选取m-1个数进行组合

　　对于n-1个数，同样有

　　先从n-1个数中选一个数出来，然后在剩下的n-2个数当中选取m-2个数进行组合

　　...

　　对于n-N个数，同样有

　　先从n-N个数中选一个数出来，然后在剩下的n-N个数当中选取m-N个数进行组合

　　如此递归

　　直到m-N==1为止

　　当m-N为1的时候，自然不用选了

　　每次选取的结果放入一个数组当中，作为参数传递下去

　　当递归到m-N为1的时候，数组和当前选定的值即构成一个有效组合，便可输出

　　这类问题都可以尝试递归的解决思路，将一个复杂的大问题，一级一级转化为较小的，可以解决的问题

　　示例代码如下：

void select(
int* data/*待筛选的数 里面不能有重复的数*/,
int n,
int m,
int list[]/*假设list长度足够，为m,初始list中的元素值为-1*/,
int listlen)
{
    int i,j;
    if(m==1){
        for(i=0;i<n;i++){
            for(j=0;list[j]!=-1;j++)
            {
                printf("%d ",list[j]);
            }
            printf("%d\n",data[i]);//输出一个结果
        }
        return;
    }
    for(int i=0;i<n-m;i++)
    {
       list[listlen-m] = data[i];
       select(data+i+1,n-i,m-1,list,listlen);//递归调用
    } 
}

Answer 2

n = 5
m = 3
a数组 result向量
{1,2,3,4,5} {}
{0,2,3,4,5} {1}
{0,0,3,4,5} {1,2}
{0,0,0,4,5} {1,2,3} //输出，回溯
{0,0,3,0,5} {1,2,4} //输出，回溯
{0,0,3,4,0} {1,2,5} //输出，回溯
{0,2,0,4,5} {1,3}
{0,0,0,4,5} {1,3,2} //输出，回溯
{0,2,0,0,5} {1,3,4} //输出，回溯
。。。。。。 //这是排列，不是组合
自己单步运行调试吧，这样更容易理解

追问

我的编译器有问题 亲 可不可以给我一个呀

追答

我手上只有VS 镜像，这太大了，没法给， 你还是网上搜搜吧。 祝好运

追问

谢谢啦 我也被我的vc干死了