洛谷 P1028 数的计算

绝地灬酷狼 2022-01-11 07:15 434阅读 0赞

## **嗯...**  ##

# #

## **首先这道题想到的就是递推....** ##

# #

## **但是递推失败 （不知道自己是怎么想的 然后又想打一个暴力，但是数的最高位太难存储了，所以又放弃了（并且好像这个暴力大约500就会炸...** ##

# #

## **然后看了题解，才发现是这样的简单....** ##

# #

# **先看一下题：** #

# #

## **题目描述** ##

**我们要求找出具有下列性质数的个数(包含输入的自然数n):**

**先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:**

1.  **不作任何处理;**
2.  **在它的左边加上一个自然数,但该自然数不能超过原数的一半;**
3.  **加上数后,继续按此规则进行处理,直到不能再加自然数为止.**

## **输入输出格式** ##

**输入格式：**

**1个自然数n(n≤1000n)**

**输出格式：**

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

## **输入输出样例** ##

**输入样例\#1：**

**输出样例\#1：**

## **说明** ##

**满足条件的数为**

**6，16，26，126，36，136**

# **思路：** #

## **其实这道题的思路很简单（在你知道它是一道递推题之后...** ##

### **假设 n == 4， 那么它前面的一个数可能是2或1， 而这时我们通过递推已经求出2 或 1 中有这种性质的数的个数，只需要加起来存到4中即可...** ###

## **你用手模一下，便可以发现，好像有点类似于斐波那契数列....但又不完全是，所以手模后可以发现：** ##

## **n == 1  ------->   ans == 1** ##

## **n == 2  ------->   ans == 2** ##

## **n == 3  ------->   ans == 2** ##

## **n == 4  ------->   ans == 4** ##

## **所以又一次验证了上面的结论的正确性，ans\[4\] = ans\[2\] + ans\[1\] + 1 ...** ##

## **所以便有了递推式：** ##

1 for(int i = 1; i <= n; i++){
         //递推 
    2         for(int j = 1; j <= i / 2; j++){
    3             f[i] += f[j];
    4         }
    5         f[i]++;
    6     }

# **下面是AC代码：** #

1 #include<cstdio>
     2 #include<iostream>
     3 
     4 using namespace std;
     5 
     6 int f[1005];
     7 
     8 int main(){
     9     int n;
    10     scanf("%d", &n);
    11     for(int i = 1; i <= n; i++){
         //递推 
    12         for(int j = 1; j <= i / 2; j++){
    13             f[i] += f[j];
    14         }
    15         f[i]++;
    16     }
    17     printf("%d", f[n]);
    18     return 0;
    19 }

转载于:https://www.cnblogs.com/New-ljx/p/10587593.html