python一只青蛙一次可以_27、青蛙跳台阶/爬楼梯汇总-斐波那契数列及各种变形...

- 日理万妓 2023-01-02 10:26 141阅读 0赞

## **基础问题-洛谷p1255** ##

![ef970a97b743e064c3d60426e2dfeb9e.png][]

分析思路：

假设有i层台阶，res\[i\]表示跳到i层台阶的方法数，最后一步有两种选择：走一步或走两步。

res\[i\] = (res\[i-2\] and 走两步) + (res\[i-1\] and 走一步)

因此，该问题本质是斐波那契数列。

**注意一：直接递归写，肯定会由于大量的重复子问题计算导致超时。**

考虑到要计算fib(N)，要先计算fib(N-1)和fib(N-2)；

fib(N-1) fib(N-2) fib(N-3)

fib(N-2) fib(N-3) fib(N-4)

fib(N-3) fib(N-4) fib(N-5)

fib(N-4) fib(N-5) fib(N-6)

存在着大量的重复计算的子问题。

解决办法：采用备忘录保存计算好的子问题，需要的时候查备忘录即可。

**注意二：整型长整型数据溢出问题**

考虑到N<=5000，最后结果肯定会溢出。

采用C++肯定要用高精才行，long long类型存储不下。

解决办法，采用python来写，不存在整数溢出问题。

s = input()
    n = int(s)
    def fun(n):
        res = [0]*5005 #list初始化为5005个0
        if n<=0: #处理0
            return 0
        else:
            res[1] = 1
            res[2] = 2
            for i in range(3, n+1): #注意闭区间[3, n]
                res[i] = res[i-1] + res[i-2]
            return res[n]
    print(fun(n))

**总结：**

**三个步骤：**

1.  **看出来问题的本质是斐波那契数列；**
2.  **考虑到递归中子问题重复计算导致的超时，采用备忘录的策略解决；**
3.  **考虑到题目里的数据范围和C/C++中整型数据溢出问题。**

## **------下面是各种变形--------** ##

## **青蛙跳台阶-变态版** ##

一只青蛙一次可以跳1级台阶，也可以一次跳2级台阶，...，也可以一次跳n级台阶。求这只青蛙跳上一个n级台阶总共有多少办法？

思路：

f\[n\]为这只青蛙跳上n级台阶的方法数目：

**f\[n\] = f\[n-1\] + f\[n-2\] + ... + f\[1\] + f\[0\]**

解释一下：

这只青蛙可以先跳上1级，余下n-1级；

这只青蛙可以先跳上2级，余下n-2级；

...

这只青蛙可以先跳上n-1级，余下1级；

这只青蛙可以先跳上n级，余下0级；

因此，不难写出：

**f\[n-1\] = f\[n-2\] + ... + f\[1\] + f\[0\]**

则有以下等式

**f\[n\] - f\[n-1\] = f\[n-1\]**

**f\[n\] = 2\*f\[n-1\]**

可以推出最终结果：

f\[1\] = 1;

f\[n\] = 2^(n-1).

## 变形2 ##

一只青蛙一次可以跳1级台阶，也可以一次跳2级台阶，...，也可以一次跳m级台阶。求这只青蛙跳上一个n级台阶总共有多少办法？

思路：

如果n<=m，则同上，直接返回2^(n-1)。

如果n>m，则有：

f\[n\] = f\[n-1\] + f\[n-2\] + f\[n-3\] + ... + f\[n-m\]

f\[n-1\] = f\[n-2\] + f\[n-3\] + ... + f\[n-1-m\]

f\[n\] = 2\*f\[n-1\] - f\[n-1-m\]

## 变形3-带限制跳台阶 ##

一只青蛙一次可以跳1级台阶，也可以一次跳2级台阶，但是出于体力因素不允许连着两次跳2级台阶。求这只青蛙跳上一个n级台阶总共有多少办法？

思路：

f\[n\]仍然是跳n级台阶的方法数，我们用g\[n\]表示最后一步不是跳2级的走法数目，h\[n\]表示最后一步跳2级的走法数目。显然的有：

f\[n\] = g\[n\]+h\[n\]

h\[n\] = g\[n-2\]，这是因为在不能连着两次跳2级的情况下，必定成立的等式，倒数第二步不是跳2级，最后一步跳2级。

g\[n\] = g\[n-1\] + h\[n-1\] 倒数第二步的走法+最后1级台阶的走法 - 先g\[n-1\]再1级+先h\[n-1\]再1级。

f\[n\] = g\[n\] + h\[n\] = g\[n-1\] + g\[n-3\] + g\[n-2\]

f\[n-1\] = g\[n-1\] + h\[n-1\] = g\[n-1\] + g\[n-3\]

**f\[n\] = f\[n-1\] + g\[n-2\]**

**g\[n-2\] = g\[n-3\]+h\[n-3\] = f\[n-3\]**

因此，有f\[n\] = f\[n-1\] + f\[n-3\]

f\[0\]=1

f\[1\]=1

f\[2\]=2

f\[3\]=3

...

**fib数列题目**

有一个分数序列 2/1,3/2,5/3,8/5,13/8,21/13,.... 求这个分数序列的前n项之和。

每组测试数据单独输出有一行：分数序列的和（精确到小数点后4位）。

fib=[0]*91
    k=input()
    k=(int)(k)
    for c in range(k):
        n=input()
        n=(int)(n)
        fib[0]=1
        fib[1]=2
        for i in range(2,n+1):
            fib[i]=fib[i-1]+fib[i-2]
        ans=0.0
        for i in range(n):
            ans = ans + (fib[i+1]/fib[i])
        print('%.4f' % ans)

[ef970a97b743e064c3d60426e2dfeb9e.png]: /images/20221119/e3f1ebdc81954f5fb64f32ff01d06efd.png