C/C++语言100题练习计划 86——数的计算（递推实现）

名人说：故立志者，为学之心也；为学者，立志之事也。—— 王阳明
进度：C/C++语言100题练习计划专栏，目前86/100

🥇C/C++语言100题练习专栏计划：目的：巩固练习C/C++语言，增强上机、动手实践能力，交流学习！

一、问题呈现

1.问题描述

Problem Description
我们要求找出具有下列性质数的个数（包含输入的正整数 $n$）。

先输入一个正整数 $n$（$n\le 1000$），然后对此正整数按照如下方法进行处理：

1. 不作任何处理；

2. 在它的左边拼接一个正整数，但该正整数不能超过原数，或者是上一个被拼接的数的一半；

3. 加上数后，继续按此规则进行处理，直到不能再加正整数为止。

2.输入输出

Input

一行，一个正整数 $n$（$n\le 1000$）。

Output

一个整数，表示具有该性质数的个数。

3.测试样例

Sample Input

6

Sample Output
6

★提示：

【样例解释】

满足条件的数为：$6$，$16$，$26$，$126$，$36$，$136$。

【题目来源】

NOIP 2001 普及组第一题

二、源码实现

#include 
const int maxn=1e3+5;
using namespace std;
int f[maxn];

int main()
{
    int n;
    //输入正整数n
    cin>>n;
    //初始化f[1]为1
    f[1]=1;
    //递推实现
    for(int i=2;i<=n;i++)
    {
        f[i]=f[i-1];
        if(i%2==0)
        {
		  f[i]+=f[i/2];	
		}
    }
    //输出具有该性质数的个数
    cout<<f[n]<<endl;
    return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

★关于本题思路及递推：

1、本题思路简述

首先以4为例：
4后面可以与1,2组成14,24
14后面就没了,24可以与1组成124
再加上4本身就可以得到4的种类了
即：14,24,124,4
而我们只要算出1,2的种类就可以加起来得到4的种类
以此类推：
f[1]=1
f[2]=2=f[1]+1
f[3]=2=f[1]+1
f[4]=4=f[1]+f[2]+1
f[5]=4=f[1]+f[2]+1
通过多例的观察，可以推断出当i为奇数时f[i]=f[i-1]，当i为偶数时f[i]=f[i-1]+f[i/2];

2、递推

1️⃣递推相关概念
递推是经常被使用的一种简单的算法。递推是一种用若干步可重复的简单运算来描述复杂问题的方法。

2️⃣递归的特点
递推的特点在于，每一项都和他前面的若干项由一定的关联，这种关联一般可以通过递推关系式来表示，可以通过其前面若干项得出某项的数据。

3️⃣递归求解
对于递推问题的求解一般从初始的一个或若干个数据项出发，通过递推关系式逐步推进，从而得出想要的结果，这种求解问题的方法叫递推法。其中，初始的若干数据项称为边界。

4️⃣递推举例
经典的斐波那契数列问题，用 f (i)表示第 i 项的值，则 f (1) =0，f(2) =1，在 n>2 时，存在递推关系式：f (n) = f(n-1) + f(n-2)。

★注意，递推算法相对来说适合有明显公式规律的场合。

三、测试结果

6
6

--------------------------------
Process exited after 3.292 seconds with return value 0
请按任意键继续. . .
1
2
3
4
5
6

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
如果对大家有帮助的话，希望大家能多多点赞+关注！这样我动力会更足哦！ ღ( ´･ᴗ･` )比心