和同学聊天时提到了在新浪面试记中说的那道编程题，这里再描述一遍题目：从1到100中取5个不相同的数，相加小于100，有多少种方法。

给她看了我的方法：

int iprfunc()
{
	int num=0;
	int i,j,k,m,n;
	for(i=1;i<18;i++)
		for(j=2;j<24;j++)
			for(k=3;k<32;k++)
				for(m=4;m<47;m++)
					for(n=5;n<90;n++)
						if((i+j+k+m+n)<100 && (i<j) && (j<k) && (k<m) && (m<n)){
							num++;
						}
	return num;
}

大神问了循环边界的确定方法，然后给出一个改进的版本：

int func2()
{
	int num = 0;
	int i,j,k,m;
	for(i=1;i<18;i++)
		for(j=i+1;j<24;j++) 
			for(k=j+1;k<32;k++)
				for(m=k+1;m<47;m++)
				{
					int sum = i+j+k+m;
					if(sum<95 && m<(99-sum)) {
						num +=99-sum-m;
					}
				}
    return num;

}

既然是递增排列，那么循环初始值就不用像我的方法那样定死了，然后是最去掉一层循环，意思是最 后一个数有多少种情况是可以直接算出来的，99-sum得最后一个数的最大值，然后最后一个数一定是从m+1开始，所以又 num=99-sum-(m+1)+1 = 99-sum-m；

跑一下，确实快了很多，1ms以内解决问题，我之前的是要144ms左右。

然后继续看代码，发现循环边界确定的其实是有问题的，之前只是确定了边界的最大值，然而最大值并不是固定不变的，比如i=1时，j可以取到23，但是i=2时，j只能到22了，也就是说循环边界应该动态确定，修改iprfunc()，如下：

int func3()
{
	int num=0;
	int i,j,k,m,n;
	for(i=1;i<18;i++)
		for(j=i+1;j<((99-i-6)/4+1);j++)
			for(k=j+1;k<((99-i-j-3)/3+1);k++)
				for(m=k+1;m<((99-i-j-k-1)/2+1);m++)
					for(n=m+1;n<(99-i-j-k-m+1);n++)
						if((i+j+k+m+n)<100){
							num++;
						}
	return num;
}

解释一下，i确定之后，最大情况：j+(j+1)+(j+2)+(j+3) = 99-i，所以 j<(99-i-6)/4 + 1，余下的同理。跑一下，2至3毫秒之间。还是比大神的慢一些。

结合大神的思想，去掉一层循环：

int final()
{
	int num=0;
	int i,j,k,m;
	for(i=1;i<18;i++)
		for(j=i+1;j<((99-i-6)/4+1);j++)
			for(k=j+1;k<((99-i-j-3)/3+1);k++)
				for(m=k+1;m<((99-i-j-k-1)/2+1);m++)
				{
					int sum = i+j+k+m;
					num += (99-sum-m);	//直接算出有最后一个可选数的数量  如 1+2+3+4，第5个数只能从5到89，共85种情况
				}
	return num;

}

然后测试一下:

int main(int argc, char* argv[])
{
	clock_t start,finish;
	int total;

	start=clock();
	cout<<func()<<endl;
	finish=clock();
	total=(int)(finish-start);
	cout<<"改进前(执行1次): "<<total<<endl;

	start=clock();
	cout<<iprfunc()<<endl;
	finish=clock();
	total=finish-start;
	cout<<"改进后(执行1次): "<<total<<endl;

	start=clock();
	for(int i=0;i<1000;i++)
		func2();
	cout<<func2()<<endl;
	finish=clock();
	total=finish-start;
	cout<<"改进后2(执行1000次): "<<total<<endl;

	start=clock();
	for(int i=0;i<1000;i++)
		func3();
	cout<<func3()<<endl;
	finish=clock();
	total=finish-start;
	cout<<"改进后3(执行1000次): "<<total<<endl;

	start=clock();
	for(int i=0;i<1000;i++)
		final();
	cout<<final()<<endl;
	finish=clock();
	total=finish-start;
	cout<<"改进后4(执行1000次): "<<total<<endl;
	return 0;
}

终于比大神的快一些了：

$ ./1-100.exe
455175
改进前(执行1次): 16537
455175
改进后(执行1次): 141
455175
改进后2(执行1000次): 477
455175
改进后3(执行1000次): 2259
455175
改进后4(执行1000次): 149

不知道此类问题有没有通用的算法，比如1到n中取m个数。如果路过的大神知道，还望不吝赐教。