P1028 [NOIP 2001 普及组] 数的计算

题目描述

给出正整数nnn，要求按如下方式构造数列：

1. 只有一个数nnn的数列是一个合法的数列。
2. 在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。

请你求出，一共有多少个合法的数列。两个合法数列a,ba, ba,b不同当且仅当两数列长度不同或存在一个正整数i≤∣a∣i \leq |a|i≤∣a∣，使得ai≠bia_i \neq b_iai​=bi​。

解法，两种（三种）

递归：

intrec(intx){if(s[x])returns[x];//避免重复，剪枝intsum=1;//这里的值设定挺重要的for(inti=1;i<=x/2;i++){s[i]=rec(i);sum+=s[i];}returnsum;}

递归就是将过于复杂的过程打包成块，然后下发处理。如果一个问题可以被拆分成多个高度相似的子问题，就可以考虑递归。

存储数据有利于剪枝，空间换时间。

“递归代码最重要的两个特征：结束条件和自我调用．自我调用是在解决子问题，而结束条件定义了最简子问题的答案．”

提问：不同递归函数中的sum值会不会互相挤占？

递推：

易知当n为奇数时，f[n]=f[n-1]
当n为偶数时，f[n]=f[n-1]+f[n/2]
这里有两种推导方式：
第一是写f[n]的通式作差，
第二种是再次运用递推思想，在n-1的基础上，多出来的是f[n/2]的值

#include"iostream"usingnamespacestd;intf[1010]={0,1};//初始化值，主要是为了f[1]intmain(){intn;cin>>n;for(inti=2;i<=n;i++){if(i%2==1)f[i]=f[i-1];elsef[i]=f[i-1]+f[i/2];}cout<<f[n];return0;}

其实这里还有一种递推，双重循环寻找，和不剪枝的递归差不多

for(inti=2;i<=n;i++){f[i]=1;//这一步初始化很重要for(intj=1;j<=i/2;j++){f[i]+=f[j];}}

大概就是以上，结束啦(=´ω`=)