中信建设有限责任公司内部网站,网站建设 检查 通报,重庆腊肠制作,南宁百姓网时刻记住一句话#xff1a;写递归#xff0c;1画图#xff0c;2大脑放空#xff01;#xff01;#xff01;
意思是#xff0c;自己写递归题目#xff0c;先用样例给的数据画图#xff0c;然后想一个超级简单的思路#xff0c;直接套上去就可以了。 上题干#xff…时刻记住一句话写递归1画图2大脑放空
意思是自己写递归题目先用样例给的数据画图然后想一个超级简单的思路直接套上去就可以了。 上题干 题目描述 给出正整数 n要求按如下方式构造数列 只有一个数字 n 的数列是一个合法的数列。在一个合法的数列的末尾加入一个正整数但是这个正整数不能超过该数列最后一项的一半可以得到一个新的合法数列。 请你求出一共有多少个合法的数列。 输入格式 输入只有一行一个整数表示 n。 输出格式 输出一行一个整数表示合法的数列个数。 输入输出样例 输入 #1复制 6输出 #1复制 6说明/提示 样例 1 解释 满足条件的数列为 66,16,26,36,2,16,3,1 数据规模与约定 对于全部的测试点保证 1≤n≤10^3。 说明 本题数据来源是 NOIP 2001 普及组第一题但是原题的题面描述和数据不符故对题面进行了修改使之符合数据。原题面如下谨供参考 我们要求找出具有下列性质数的个数包含输入的正整数 n。 先输入一个正整数 nn≤1000然后对此正整数按照如下方法进行处理 不作任何处理在它的左边拼接一个正整数但该正整数不能超过原数或者是上一个被拼接的数的一半加上数后继续按此规则进行处理直到不能再加正整数为止。 这道题不要想那么复杂。
题目给的数字是6并且帮我们分析了答案如何来的
66,16,26,36,2,16,3,1
第一步画图
我们可以画出一个简易的树状图 第二步大脑放空想一个最简单的思路
从i0开始枚举一直枚举到 6/2
用 f【i】表示6后面直接跟的数字是 i 的种数。如果i0就代表没有跟任何数字
所以答案就是 f【0】 f【1】 f【2】f【3】
结束
写出代码 const int N 1e3 7;
int lxnb(int x) {int ans 0;if (x 1 or x 0)return 1;for (int i 0; i x / 2; i) {ans lxnb(i);}return ans;
}int main() {int n;cin n;cout lxnb(n);
} 然后这样的普通递归无法完成本题。
所以我们可以用到记忆化的方法用一个数组记录f【i】的值如果f【i】已经被记录了 那么我们就直接返回它的值。
无脑塞进去就行了哪里需要管这么多。。。。
#define _CRT_SECURE_NO_WARNINGS
#includeiostream
#includecstdio
#includecmath
#includestring
#includecstring
#includestring
#includealgorithm
#includevector
#includecctype
#includemap
#includeset
#includequeue
#includenumeric
using namespace std;
const int N 1e3 7;
int flag[N];
int lxnb(int x) {int ans 0;if (flag[x])return flag[x];if (x 1 or x 0)return 1;for (int i 0; i x / 2; i) {ans lxnb(i);}return flag[x]ans;
}int main() {int n;cin n;cout lxnb(n);
}
