【递推算法】

1. 雌雄各一的一对新兔子放入养猪场，每只雌兔在出生两个月后，每月产雌雄兔子各一只，试问第N个月后，养殖场中有多少对兔子。
   1. Fibonacci数列
   2. 方法1：找规律
   3. 方法2：直接推导：f(n)=f(n-1)+f(n-2), f(n-1)是上一个月及以前的老兔子（定义f(n)表示第n个月养殖场中有的所有兔子对，所以f(n-1)就是上个月的所有的兔子对），f(n-2)是这个月新生的兔子！！（这个月新生的兔子就是n-2个月的时候那f(n-2)所有的雌兔子生的，所以是n-2）
   4. f(1)=1,第一个月只有一对兔子，f(2)=1，已经长大了具备生育能力但是还没有繁殖新的兔子
2. 昆虫繁殖

   1. 科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0≤X≤20,1≤Y≤20,X≤Z≤50。

      【输入】

      x,y,z的数值。

      【输出】

      过Z个月以后，共有成虫对数。

   2. 注意这题求的是成虫数，而且是z后那个月的，将a[i]视为存放第i个月的成虫数，最后要求的是a[z+1]
   3. 有两种分类方法：
   4. 成虫=有繁殖能力的成虫+没有繁殖能力的成虫
   5. 成虫=上个月所有的老的成虫+这个月新加入的年轻成虫
   6. 第一种分类方法不适合用于求a[z+1]，因为没有繁殖能力的成虫很难求
   7. 一般会选择用第二种分类法，上个月的老成虫就是a[i-1]，设第i个月新出生的卵为b[i]，则这个月新加入的成虫为b[i-2]，就是两个月前的卵。
   8. 而第i个月新生的卵就是那时的所有有繁殖能力的成虫（a[i-x]）所生的，所以b[i]=y*a[i-x])

   9. #include<iostream>
      #include<string.h> 
      using namespace std;
      int x,y,z;
      int main()
      {
          cin>>x>>y>>z;
          long long a[100],b[100];
          memset(a,0,sizeof(a));
          memset(b,0,sizeof(b));
          for(int i=1;i<=x;i++)    
          {
              b[i]=0;
              a[i]=1;
              #ifdef debug 
              cout<<a[i]<<endl;
              #endif 
          }
          for(int i=x+1;i<=z+1;i++)    //因为是z后的那个月的成虫，所以是循环到z+1 
          {
              b[i]=y*a[i-x];    //新的虫子，最年轻的那些能繁殖的虫子生的 
              a[i]=a[i-1]+b[i-2];    //a[i-1]所有老的成虫
              //b[i-2]是两个月前的卵，也就是这个月的最年轻的成虫 
              #ifdef debug
              cout<<"second: "; 
              cout<<a[i]<<endl;
              #endif 
          }
          cout<<a[z+1]<<endl;
          return 0;
      }

       

【递推算法】

原文：https://www.cnblogs.com/xuwanwei/p/10896762.html