网站开发框架拓扑,导航类网站源码,环保公司网站建设内容,网站紧急维护题目
给出正整数n#xff0c;要求按如下方式构造数列#xff1a;
只有一个数字n的数列是一个合法的数列。在一个合法的数列的末尾加入一个正整数#xff0c;但是这个正整数不能超过该数列最后一项的一半#xff0c;可以得到一个新的合法数列。
请你求出#xff0c;一共…题目
给出正整数n要求按如下方式构造数列
只有一个数字n的数列是一个合法的数列。在一个合法的数列的末尾加入一个正整数但是这个正整数不能超过该数列最后一项的一半可以得到一个新的合法数列。
请你求出一共有多少个合法的数列。两个合法数列a,b不同当且仅当两数列长度不同或存在一个正整数i≤∣a∣使得。
输入输出格式
输入格式
输入只有一行一个整数表示n。
输出格式
输出一行一个整数表示合法的数列个数。
输入输出样例
输入样例
6
输出样例
6
解析
对于一个整数n如果只考虑变换一次那么问题就很简单了答案就是n/21但是还需要对变换后的继续变换。比如说数列中最开始只有一个元素8在末尾加入一个新元素列表就可以变成[8 4]、[8 3]、[8 2]、[8 1]算上[8]一共有五种情况之后的变换只需要按照上面的这种方法分别是计算[4]、[3]、[2]、[1]按照这样的操作能有几种情况然后累加统计即可。
原来是要解决n8的问题现在分解成了4个规模更小但本质上同样的子问题如果要解决n4的问题基于同样的思想还可以分解成两个规模更小的单质相同的子问题当需要解决n2的问题时可以分解成n1的问题只有n1的情况了直到n1时没法继续分解根据题目说的“不作任何处理就直接统计为一种合法的数列”可以直接返回只有唯一一种数列即[1]。然后返回上一层接受到所有小规模问题的答案合并统计处理获得这个规模下的答案再继续返回上一层……直到求得问题的解。
像这样构造函数这个函数在运行过程中调用自己从而解决问题的思路就称为递归思想。
#includeiostream
#includecstring
using namespace std;
int n,count,f[1010];
int sol(int x){int count1;if(f[x]!-1){return f[x];}for(int i1;ix/2;i){countsol(i);}return f[x]count;
}
int main(){cinn;memset(f,-1,sizeof(f));f[1]1;coutsol(n)endl;return 0;
}
直接使用递归运行效率很低为了防止做很多无用功可以定义一个数组f其每一项f[i]就是当问题规模为i的时候的答案首先将数组初始化为-1说明f[i]还没有被计算过。依然使用同样的方法去求解只是如果发现已经计算过就直接返回f[i]而不必进行接下来的计算了否则还是按照刚才递归的方式计算然后将结果存入数组中以便之后再次调用。
这样每个数字最多只计算一次因为一旦计算完成就会被存下来便于日后使用这样的思想称为“记忆化搜索”。
