用递归法求数的计算

题目描述

我们需要计算满足以下条件的数的个数（包含输入的自然数 $n$）：

1. 输入：一个自然数 $n$（$n\le 1000$）。
2. 处理规则：
   • 规则1：直接保留原数 $n$。
   • 规则2：在 $n$ 的左边添加一个自然数 $k$（$1\le k\le \lfloor n/2\rfloor$），形成新数 k⋅10len(n)+n（其中 $\text{len}(n)$ 为 $n$ 的位数）。
   • 规则3：对新增的数 k⋅10len(n)+n，重复应用规则1和规则2，直到无法继续添加自然数为止。

示例：

• 输入 $n=6$，满足条件的数为：6、16、26、126、36、136，共 6 个。
• 输出：6

提示：必须运用递归方法完成

• 递归思想：将问题分解为子问题（如对 $\lfloor n/2\rfloor$ 递归求解）。
• 终止条件：当 $n=1$ 时，直接返回1（仅自身满足条件）。

输入

• 一行，一个自然数 $n$（$1\le n\le 1000$）。

输出

• 一行，一个整数，表示满足条件的数的个数。

样例

提交人

来源/分类