斐波那契数列以及变形

系统管理员 2024-04-17 06:03 78阅读 0赞

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。  
n<=39

public class Solution {
        public int RectCover(int target) {
             if(target < 1){
                return 0;
            }
            else if(target == 1 || target ==2){
                return target;
            }
            else {
                return RectCover(target-1)+ RectCover(target-2);
            }
        }
    }

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）

链接：https://www.nowcoder.com/questionTerminal/8c82a5b80378478f9484d87d1c5f12a4?f=discussion
    来源：牛客网
    
    对于本题,前提只有 一次 1阶或者2阶的跳法。
    
    a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);
    
    b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
    
    c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) 
    
    d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
    
    e.可以发现最终得出的是一个斐波那契数列：
    
            
    
                  | 1, (n=1)
    
    f(n) =     | 2, (n=2)
    
                  | f(n-1)+f(n-2) ,(n>2,n为整数)
    
    
    public class Solution {
        public int JumpFloor(int target) {
            if(target < 1){
                return 0;
            }
            if(target == 1){
                return 1;
            }
            if(target == 2){
                return 2;
            }
            
                return JumpFloor(target-1)+JumpFloor(target-2);
            
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，78人围观）

还没有评论，来说两句吧...

相关阅读

相关斐波那契数列以及变形

家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39 public class Solution...

系统管理员/ 2024年04月17日 06:03/ 0 赞/ 79 阅读

相关斐波那契数列

斐波那契数，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，

Love The Way You Lie/ 2022年11月19日 04:15/ 0 赞/ 273 阅读

相关斐波那契数列

\\题目描述大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39 思路 1. 递归（函数栈调用消耗

ゝ一纸荒年。/ 2022年10月29日 06:26/ 0 赞/ 74 阅读

相关斐波那契数列

// 斐波那契数列.cpp : 定义控制台应用程序的入口点。 // \include "stdafx.h" \include<iostream> usin

谁践踏了优雅/ 2022年08月23日 14:45/ 0 赞/ 107 阅读

相关斐波那契数列

关于斐波那契数列的解法，本人找到了一种比较简单的方法，结果是正确的，不知道各位有没有另外更好的解法，一起探讨探讨。 import java.util.; pu

╰+攻爆jí腚メ/ 2022年08月01日 12:15/ 0 赞/ 418 阅读

相关斐波那契数列

定义：斐波那契数列指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 这个数列从第三项开始，每一项都等于前两项之和。

矫情吗；*/ 2022年07月13日 04:49/ 0 赞/ 341 阅读

相关斐波那契数列

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，

冷不防/ 2022年07月13日 03:19/ 0 赞/ 366 阅读

相关斐波那契数列

class FibIter(object): def __init__(self, lenth): self.lent

一时失言乱红尘/ 2022年05月27日 13:51/ 0 赞/ 367 阅读

相关斐波那契数列

include<iostream> using namespace std; int fibonacci1(int t) { if(t

古城微笑少年丶/ 2022年05月09日 08:58/ 0 赞/ 338 阅读

相关斐波那契数列

![1234096-20171112230708606-1911525192.png][] 转载于:https://www.cnblogs.com/ostrich-sugar

た入场券/ 2022年01月06日 23:41/ 0 赞/ 401 阅读