简单的整数划分问题(递归)

描述
将正整数n 表示成一系列正整数之和,n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ,k>=1 。
正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。

输入
标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。
输出
对于每组测试数据,输出N的划分数。
样例输入
5
样例输出
7
提示
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

可能是因为本人比较笨的原因吧,这道题提交了九遍才对。
简单的整数划分问题(递归)
一开始觉得像斐波那契的变式,但后来才发现不行,才老老实实写递归,这个问题我们需要把我们递归的数记录下来,因为题目说了(n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1)
所以我们用a数组来记录,每次判断这个数行不行时,就与前面的数进行判断,比大小,本人给这个递归函数取了一个没有技术含量的名字叫solve(int n),我们用循环从1到n(两端取到,不必从0~n,因为0可以一直递归下去,而且判断n时,就相当于在判断0)。
OK,那么我们这个边界值就是n==0,就cnt++;
最后输出。
提醒一下,数据最大为50,会超时,所以我们保险起见,先把40~50的结果打出来,直接复制给a,然后输出。
我是把1~40的先算出来,40-50的直接复制。然后再输入n,直接输出。
好了,看代码。

#include<bits/stdc++.h>
using namespace std;
long long int n,a[1000],cnt,b[70];
void solve(int m,int death)
{
	bool flag=1;
	if(m==0)
	{
		cnt++;
	}
	else
	{
		for(int i=1;i<=m;i++)
		{
			flag=1;
			++death; 
			for(int j=1;j<death;j++)
			if(a[j]>i)
			{
				flag=0;
				break;
			}
			if(flag)
			{
				a[death]=i;
				solve(m-i,death);
			}
			--death;
		}
	}
}
int main()
{
	for(int i=1;i<=39;i++)
	{
		solve(i,0);
		memset(a,0,sizeof(a));
		b[i]=cnt;
		cnt=0;
	}
	b[40]=37338;
	b[41]=44583;
	b[42]=53174;
	b[43]=63261;
	b[44]=75175;
	b[45]=89134;
	b[46]=105558;
	b[47]=124754;
	b[48]=147273;
	b[49]=173525;
	b[50]=204226;
	while(cin>>n)
	{
		cout<<b[n]<<endl;
	}
}
上一篇:PG守护进程(Postmaster)——InitPostmasterDeathWatchHandle


下一篇:python yield 和 yield from用法总结