关于递推算法，解析进击的青蛙，B君的寄望，Fibonacci数列整除问题

数列整除问题"/>

关于递推算法，解析进击的青蛙，B君的寄望，Fibonacci数列整除问题

1.关于递推算法解析：

我们在学习这一类题时，首先要了解到的题是爬楼梯和Fibonacci数列

先讲一下Fibonacci数列，因为我认为这是递推算法的最简单也最明了的题

1.1：斐波那契数列

我们输入一个值，假定为5，那么需要计算的就是f(5),我们从前往后运算

f(3)=f(1)+f(2);

f(4)=f(2)+f(3);

f(5)=f(3)+f(4);

我们可以看到，它的每一次结果都是从上一次的结果进行计算

那么在写代码的时候，关键代码就是：dp[i]=dp[i-1]+dp[i-2];

1.2爬楼梯问题

问题一：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

它的初始位置为0，要跳到第n级台阶，我们可以定义一个数组 dp[n+1],并且dp[0]=1;

那么我们开始从第一级台阶开始算

走到第一台阶的只有一种，走一格

而走到第二阶台阶的可能就有1+1 或者直接走两格

但是，我们可以简单的分析一下，当你走上第n级台阶的时候，你的方法种数有哪些？

那你要考虑：你上一步是走一格还是走两格

走一格的话就是 从第n-1格走上来

走两格就是从第n-2格走上来

那么，dp【n】=dp【n-1】+dp【n-2】；

错误问题：从n-2可以走两次1格啊，为什么直接加的dp【n-2】？

因为当你在走dp【n-1】时，已经是计算了dp【n-2】走到dp【n-1】的方案了

而如果你从dp【n-2】走两次1，那会先走到dp【n-1】，再走到dp【n】，会导致重复计算

问题二：一只青蛙一次可以跳上1级台阶，也可以跳上2级，3级.......n级，求该青蛙跳上一个n级的台阶总共有多少种跳法。

这题的思路和上面的其实一样，但是有一点，就是这一级台阶他是可以一次到的

那么dp【n】=dp【0】+dp【1】+dp【2】+.......+dp【n-1】

但是如果值太大，就太方便计算，因为每一次都要从0加到n-1，在蓝桥杯中如果值大了，会超时

那我们可以看一下，dp【1】=dp【0】，dp【2】=dp【1】+dp【0】=2dp【0】；

dp【3】=dp【2】+dp【1】+dp【0】=2dp【2】；

dp【n】=dp【n-1】+...+dp【0】=2dp【n-1】；

所以，这是一个等比函数，直接得结果，2^(n-1);

2.题目讲解1.进击的青蛙

题目其实和爬楼梯是一样的，不过这个算爬楼梯的升级版

注意点1.要是遇到连续的三个石头，那就不需要再进行额外的运算，因为结果必定无法走通

注意点2.如果它在终点设置一个1，那么最终的结果将为0

注意点3（实测）：定义数组会导致内存超限（可能是小怂比较菜鸡，没用到正确的定义数组方法吧）

开始解析：每一次可以+1，+2，+3，那么就需要计算每一个格子的前三项

分情况：当前格子为0还是1，如果为0，则当前格子为前三项相加求和，如果为1，则当前格子为0

分情况：如果当前为1，并且连续的1已经存在2个，则说明有3个1连续，结果固定为0，不然，连续格子为1加1，如果为0，则连续中断，重归于0

import java.util.Scanner;
public class 进击的青蛙 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();//有n个数据int t=0;int k=0;long a=1,b=0,c=0,d=1;brr[0]=1;for (int i=1;i<=n;i++){t=sc.nextInt();//输入每一个数值if (k<3) {//用于计算当前连续的石头个数是否进行运算if (t == 1) {//当前位置为石头 则k+1；不然说明连续石头结束，k为0；k++;d=0;//走到当前位置的方法为0，因为不能走石头上if (i>=3) {//只有当个数大于等于三时，才会需要前面的数值更改//以下更改为每个数更改为后一个数 比如 a=1；b=2；c=3；d=0； 更改为 a=2，b=3，c=0；//因为如果下一个数要计算的话 是跳1 2 3 ，则为当前的a b c或者说是更改前的b c da = b % 1000000007;b = c % 1000000007;c = d % 1000000007;}} else {// 当前值为0  说明可以跳到k=0;//清空连续石头个数if (i>=3){//如果 是大于等于三的位置，则为当前位置前三个的方法种数和d=(c+b+a)%1000000007;//求完和后 需要更改位置值，以便下一个值的计算a=b%1000000007;b=c%1000000007;c=d%1000000007;}else if (i==2){//如果是2，则为初始位置和1号位置的种数和c=(a+b)%1000000007;}else{//如果是1，则为初始位置的种数b=(a)%1000000007;}}}}if (k>=3||t==1){//说明有连续3个石头，或者最后一个位置是石头，不能跳，输出No Way！System.out.println("No Way!");return;}//输出最后的种数System.out.println(d);}
}

2.题目讲解2.B君的寄望

 这题其实还是从爬楼梯上变更来的，可以看成每次+1或者+2，然后每一次过后都往上进1，但是这样子，你在运算时，写法会比较累，下面讲解此题方法：

每一次+1，+2，但是他们的空格都是+1，那么，可以看成每一次都是+2，+3

但是，你+2，+3是算上空格，那么你最后一个位置应该也要算上时间

所以可以把这题看成：每次往上跳两格或者三个，跳到n+1时的可能性，剩下的就是和上面的一样

import java.math.BigInteger;
import java.util.Scanner;public class B君的寄望 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt() + 1;if (n==2||n==3||n==4){System.out.println(1);return;}BigInteger ai=new BigInteger(String.valueOf(1));BigInteger bi=new BigInteger(String.valueOf(1));BigInteger ci=new BigInteger(String.valueOf(1));BigInteger di=new BigInteger(String.valueOf(1));for (int i = 5; i <= n + 1; i++) {ci=di;di=ai.add(bi);ai=bi;bi=ci;}System.out.println(bi);}
}

我用的是BigInteger，因为无论 是long 或者double 结果都会出错，它的n<1000,当测试为1000时

 2.题目讲解3.Fibonacci数列整除问题

 这题其实不难，用每一个斐波那契数去除a,b,c,d 如果都不为0，就输出i

但是，当s，t为10000的时候，它计算的值会是下面这样：

 所以，此题依旧是运用BigInteger

import java.math.BigInteger;
import java.util.Scanner;public class Fibonacci数列整除问题 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int s=sc.nextInt();//输入sint t=sc.nextInt();//输入tBigInteger a=new BigInteger(String.valueOf(sc.nextInt()));//输入4个需要除的数BigInteger b=new BigInteger(String.valueOf(sc.nextInt()));BigInteger c=new BigInteger(String.valueOf(sc.nextInt()));BigInteger d=new BigInteger(String.valueOf(sc.nextInt()));BigInteger ai=new BigInteger(String.valueOf(1));//初始值为1BigInteger bi=new BigInteger(String.valueOf(1));BigInteger ci=new BigInteger(String.valueOf(1));;BigInteger []arr=new BigInteger[4];int []brr=new int[4];//用于比较结果为0/1/-1for (int i=1;i<=t;i++) {if (i >= 3) {ci = ai.add(bi);ai = bi;bi = ci;} else if (i == 1) {ai = BigInteger.valueOf(1);} else if (i == 2) {bi = BigInteger.valueOf(1);}if (i >= s) {arr[0] = ci.remainder(a);//求余arr[1] = ci.remainder(b);arr[2] = ci.remainder(c);arr[3] = ci.remainder(d);brr[0] = arr[0]pareTo(BigInteger.valueOf(0));//比较求余后的值和0的大小brr[1] = arr[1]pareTo(BigInteger.valueOf(0));brr[2] = arr[2]pareTo(BigInteger.valueOf(0));brr[3] = arr[3]pareTo(BigInteger.valueOf(0));if (brr[0] != 0 && brr[1] != 0 && brr[2] != 0 && brr[3] != 0) {//判断余数对比后是否为0System.out.print(i + " ");}}}}
}

因本人比较菜，有更好的方法可以评论，当然，有哪个地方不理解的也可以评论询问