概述
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 d
a = 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();//输入s
int t=sc.nextInt();//输入t
BigInteger 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));//初始值为1
BigInteger 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/-1
for (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].compareTo(BigInteger.valueOf(0));//比较求余后的值和0的大小
brr[1] = arr[1].compareTo(BigInteger.valueOf(0));
brr[2] = arr[2].compareTo(BigInteger.valueOf(0));
brr[3] = arr[3].compareTo(BigInteger.valueOf(0));
if (brr[0] != 0 && brr[1] != 0 && brr[2] != 0 && brr[3] != 0) {
//判断余数对比后是否为0
System.out.print(i + " ");
}
}
}
}
}
因本人比较菜，有更好的方法可以评论，当然，有哪个地方不理解的也可以评论询问
最后
以上就是开放小鸭子为你收集整理的关于递推算法，解析进击的青蛙，B君的寄望，Fibonacci数列整除问题的全部内容，希望文章能够帮你解决关于递推算法，解析进击的青蛙，B君的寄望，Fibonacci数列整除问题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复