递归组合算法

递归组合算法
算法思想：对于一个长度为M的序列，要求N个数的组合。
1.从索引最小的元素遍历到第N-M个元素，将遍历到的元素定为组合中的第一个元素
2.判断组合中N个元素是否已满，如果满了，打印该组合，如果不满重，则截取1中选择的元素之后的序列，复步骤一。

#include<stdio.h>
#include<iostream>
using namespace std;
void getCombine(int* a,int* b,int m,int n,int index)
{
	for(int i=0;i<=m-n;i++)
	{
		b[index]=a[i];
		//cout<<index;
		if(n>1)
		getCombine(a+i+1,b,m-i-1,n-1,index+1);
		else
		{
			for(int j=0;j<=index;j++)
			{
				cout<<b[j];
			}
			cout<<endl;
		}				
	}		
}

int main()
{
	int max;
	cin>>max;
	int m,n;
	int* a=new int(max);
	int* b=new int(max);
	cin>>n;
	for(int i=1;i<=max;i++)
	{
		a[i-1]=i;
		b[i-1]=0;
	}
	getCombine(a,b,max,n,0);
	delete a;
	delete b;
	return 0;

}

评论

1 楼 lanjf635241 2010-10-27