数的计算

流浪的陈尖刀 · 2019-07-14 20:19:08 · 个人记录

这道题要找规律：（注：自然数即正整数：“1,2,3,4,5……”）

1. 当n==1时：有：“1”；共一个。
2. 当n==2时：有：“2,21”；共两个。
3. 当n==3时：有：“3,31”；共两个。
4. 当n==4时：有：“4,41,42,421”；共四个。
5. 当n==5时：有：“5,51,52,521”；共四个。

……

由此可发现：（f（x）为输入x的输出。）

1. 当n为奇数时，f（n）==f（n-1）
2. 当n为偶数时，f（n）==f（n-1）+f（n/2）

   #include<bits/stdc++.h>
   using namespace std;
   int main(){
   int n,f[1002];
   cin>>n;
   f[1]=1;
   f[2]=2;
   f[3]=2;
   for(int i=4;i<=n;i++)
   {
       if(i%2==0)
       {
           f[i]=f[i-1]+f[i/2];
       }
       else
       {
           f[i]=f[i-1];
       }
   }
   cout<<f[n];
   return 0;
   }