小韦老师@NOIP普及组-2001-数的计算.pdfVIP

⼩韦⽼师@NOIP普及组-2001-数的计算 ⼩韦⽼师@NOIP普及组-2001-数的计算 题⽬： 描述 我们要求找出具有下列性质数的个数(包含输⼊的⾃然数 n): 先输⼊⼀个⾃然数 n ( n=1000),然后对此⾃然数按照如下⽅法进⾏处理: 1. 不作任何处理; 2. 在它的左边加上⼀个⾃然数，但该⾃然数不能超过原数的⼀半; 3. 加上数后，继续按此规则进⾏处理，直到不能再加⾃然数为⽌。 输⼊ 输⼊⼀个⾃然数。 输出 输出满⾜条件的数的个数。 输⼊样例1 6 输出样例1 6 提⽰ 输⼊样例1 的 6 个数分别是： 6 16 26 126 36 136 来源 NOIP 普及组 2001年 第⼀题 题解： 破题 对于⾃然数 n，按照以下的⽅法进⾏出处理： 1.不作任何处理; 2.在它的左边加上⼀个⾃然数，但该⾃然数不能超过原数的⼀半; 3.加上数后，继续按此规则进⾏处理，直到不能再加⾃然数为⽌。 这⾥的此规则是指，这个新的数要将刚刚得到的数作为处理的对象再进⾏处理， 例如 n = 6： 1.先得到的数是 6 2.枚举 1~3(6 的⼀半，即为 3) 1. 枚举 1，可以放在 6 的左边变成 16，1 已经不能再枚举⼩于 1 的⼀半的数 2. 枚举 2，可以放在 6 的左边变成 26；2 还可以枚举 1，所以放在 26 的前⾯变成 126，现在 1 已经不可以再枚举 3. 枚举 3，可以放在 6 的左边变成 36；3 还可以枚举 1，所以放在 26 的前⾯变成 136，现在 1 已经不可以再枚举 所以，得到了 6 个数分别是：6，16，26，126，36，136 ⽅法⼀：递归 思路： 整体思路： 对于⼀个⾃然数 n ⽽⾔，得到它⾃⼰这 1 个数后，然后枚举 1~n/2 得到 n/2 个数，然后再对枚举 1~n/2 的每个数进⾏同样规则的枚 举，所以原问题被分解成结构与原问题⼀致，但是规模变⼩的⼦问题，因此可以⽤递归。 具体步骤： 1.定义 n，并输⼊ n。 2.定义⼀个 cnt，作为计数器，⽤于记录结果。 3.调⽤⾃定义函数完成计算过程： // 函数功能：完成计算过程 // 参数：n // 返回值：⽆ f(n); 4.输出结果 f(n)。 5…实现递归函数 f(n)： void f(int n) { cnt++; // 进来就加 1 ( 第⼀次进来的时候是加 n ⾃⼰) for (int i = 1; i = n/2; i++) { // 枚举 1~n/2 f(i); // 调⽤递归函数 } } 完整代码： #include bits/stdc++.h using namespace std; int cnt = 0; // 计数器，⽤于记录结果 void f(int n) { cnt++; // 进来就加 1 ( 第⼀次进来的时候是加 n ⾃⼰) for (int i = 1; i = n/2; i++) { // 枚举 1~n/2 f(i); // 调⽤递归函数 } } int main() { // 定义 n ，并输⼊ n int n; cin n; // 函数功能：完成计算过程 // 参数：n // 返回值：⽆ f(n); // 调⽤⾃定义函数完成计算过程 // 输出结果 cout cnt; return 0; } ⽅法⼆：递推 思路： 整体思路： 从 n = 6 的例⼦中，我们可以发现，如果⽤ f[n] 表⽰⾃然数为 n 时，按照以上规则可以得到的数的数量(也即题⽬所求)，则递推式为： f[n] = 1 + f[1] + f[2] + f[3] +……+f[n/2]( 加 1 是加上⾃⼰) 边界条件为: f[1] = 1 f[1]~f[n/2] 为 1~n/2 在 n 的左边时能得到的数的数量。 例如：n = 6 时， f[2] = f[1] + 1 = 2 f[3] = f[1] + 1 = 2 f[4] = f[1] + f[2] + 1 = 4 f[5] = f[1] + f[2] + 1 = 4 f[6] = f[1] + f[2] + f[3] + 1 = 1 + 2 + 2 + 1 = 6 具体步骤： 1.定义数组 f，⽤来存储对应的⾃然数能得到的数的数量 const int N = 1e3 +