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

题目描述给出正整数nnn要求按如下方式构造数列只有一个数nnn的数列是一个合法的数列。在一个合法的数列的末尾加入一个正整数但是这个正整数不能超过该数列最后一项的一半可以得到一个新的合法数列。请你求出一共有多少个合法的数列。两个合法数列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];//避免重复剪枝intsum1;//这里的值设定挺重要的for(inti1;ix/2;i){s[i]rec(i);sums[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]的值#includeiostreamusingnamespacestd;intf[1010]{0,1};//初始化值主要是为了f[1]intmain(){intn;cinn;for(inti2;in;i){if(i%21)f[i]f[i-1];elsef[i]f[i-1]f[i/2];}coutf[n];return0;}其实这里还有一种递推双重循环寻找和不剪枝的递归差不多for(inti2;in;i){f[i]1;//这一步初始化很重要for(intj1;ji/2;j){f[i]f[j];}}大概就是以上结束啦(´ω)