邹城信奥赛C++编程基础算法之递推和递归案例:数的计算

【题目描述】

请找出具有下列性质的数的个数(包含输人的正整数n)。

先输入一个正整数n(n≤1000)，然后对此正整数按照如下方法进行处理。

(1)不做任何处理。

(2)在它的左边拼接一个正整数，但该正整数不能超过原数，也不能超过上一个被拼接的数的一半。

(3)加上一个数后，继续按此规则进行处理，直到不能再加正整数为止。

【输入描述】

输人占一行，为一个正整数n(n≤1000)。

【输出描述】

输出一个整数，表示具有该性质的数的个数。

【样例输入】

6

【样例输出】

6

【样例输入/输出说明】

满足条件的数为:6,16,26,126,36,136。

【分析】

首先要理解本题拼接数的过程。以样例数据为例，给定的正整数n为6，在它的左边可以拼接1、2或3，如果拼接3，就得到36，36是符合要求的一个数。如果要继续在左边拼接数字，就只能拼接1了，得到136，这也是符合要求的一个数。但不能再拼下去了。

进一步分析，从6出发可以拼出6个数，这6个数的组成有什么规律呢?除了6本身外，其他5个数，分别是1能拼接出的1个数+2能拼接出的2个数+3能拼接出的2个数

令f[n]表示从正整数n出发，能够拼成的数的个数，则有f[n]=1+f[1]+f[2]+...+f[n/2]，其中1表示n本身。对n=6，就有f[6]=1+f[1]+f[2]+f[3]。

方法1:递推求解。本题可以直接根据递推公式计算。注意，因为是从1]开始递推到八n的，所以在求几司时，所有小于i的那些数，]的值都已经被计算出来了。代码如下。

#include<bits/stdc++.h> using namespace std;const int maxn = 1010;int n,f[maxn];intmain(){	cin >> n;	for(int i=1;i<=n;i++){		f[i] = 1;//i本身就是符合要求的一个数		for(int j=1; j<=i/2;j++){			f[i] += f[j];		} 	}	cout << f[n] << endl;	return 0;}

方法2：递归求解。本题目也可以使用递归函数来实现，但是当n值比较大的时候，会有大量的重复计算。所以，要用数组把已经求得得f[n]值存起来。具体实现方法是:在递归函数fun(int n1)中，首先判断f[n1]是否有值，如果有值，直接返回f[n1];否则通过递归调用fun(1),fun(2),...fun(n1/2)，求出ans =1+fun(1)+fun(2)+...+fun(n/2)，在返回ans之前先把ans存人f[n1]，这一点很重要。试想f数组最开始是没有值的，如果求出ans后不存人f数组，那fun函数里的i语句能起到作用吗?代码如下。

#include<bits/stdc++.h> using namespace std;const int maxn = 1010;int n,f[maxn];int fun(int n1){	if(f[n1])return f[n1];	int ans = 1;	for(int i=1;i<=n1/2;i++){		ans += fun(i);	}	f[n1] = ans;	return f[n1];}int main(){	int n;cin >> n;	cout << fun(n) << endl;	return 0;}