每周一课：L13 Fibonacci numbers(13.1)
13.png
P13.1 FibFrog
Count the minimum number of jumps required for a frog to get to the other side of a river.
-
P13.1 斐波那契青蛙跳
计算青蛙跳到河对岸的最小的跳跃次数
斐波那契序列定义如下：
F(0) = 0
F(1) = 1
F(M) = F(M - 1) + F(M - 2)，当M >= 2时
一只小青蛙想到河对岸。它开始位于河的一个岸边（位置-1），想要到达对面的河岸（位置N）。青蛙可以跳过任意距离F(K)， 其中F(K)是第K个斐波那契数。并且河面上有许多树叶，青蛙可以在树叶之间跳跃，但只能朝河岸N的方向跳。
数组A表示河的位置0到位置N−1的每个位置的叶子有无情况，它由N个整数组成，整数为0或1：
- 0表示此位置没有树叶；
- 1表示此位置有树叶；
计算青蛙能够到达河的对岸（从位置−1到位置N）的最小跳跃次数。青蛙从位置-1开始跳跃，只可以在有树叶的位置上才能进行下一次起跳，最后到达位置N结束跳跃。
例如，考虑数组A：
A[0] = 0，A[1] = 0，A[2] = 0，A[3] = 1，A[4] = 1，A[5] = 0，A[6] = 1，A[7] = 0，A[8] = 0，A[9] = 0，A[10] = 0
青蛙可以跳三次，长度F(5)=5, F(3)=2 and F(5)=5。
编写函数：
def solution(A)
给定一个由N个整数组成的数组A，则返回青蛙能跳到河的另一边的最小跳跃次数。如果青蛙不能到达河流的另一侧，函数应返回−1。
例如，针对给出的例子，函数应该返回3。
假定：
- N是区间[0，100000]中的整数；
- 数组A的每个元素都是一个整数，其值为0或者1；
- 解题思路
典型的BFS搜索问题。对于河面上有树叶的位置index，则就要遍历比index不大的所有斐波那契数f，只要index-f这个位置可以达到，那么index这个位置就可以经过一次跳跃长度为f达到。因为是遍历，所以就决定了最后得到的是最小次数。
- Python3代码
# -*- coding：utf-8 -*-
# &Author AnFany
# Lesson 13：Fibonacci numbers
# P 13.1 FibFrog
def fib(n):
"""
构造不大于n的斐波那契数的列表
:param n: 最大值
:return: 斐波那契数列[1， 1， 2， 3， 5， 8 ……]
"""
fib_list = [1]
a = fib_list[0]
b = 1
while b <= n:
fib_list.append(b)
a, b = b, a+b
return fib_list
def solution(A):
"""
判断能否按照斐波那契步数过河。 时间复杂度O(N * log(N))
:param A: 表示河面上树叶情况的数组
:return: 能，返回最少次数。不能，返回-1
"""
A = [1] + A + [1] # 添加开始的位置-1，以及结束的位置N
length = len(A)
fib_list = fib(length)
if length - 1 == fib_list[-1]: # 一次就可从位置-1跳到位置N
return 1
else:
sign_list = [length] * length # 参照序列
sign_list[0] = 0
for i in range(1, length):
if A[i] == 1: # 此处有树叶
# 遍历斐波那契数列, 寻找最少的跳跃次数
for j in fib_list:
dis = i - j # dis不得小于0，
if dis >= 0:
if sign_list[dis] + 1 < sign_list[i]: # 说明dis位置可以斐波那契到达的，
sign_list[i] = sign_list[dis] + 1 # 达到位置dis的次数再加上走长度为斐波那契数j的一次
print(sign_list)
else:
break # 后面的斐波那契数更大
if sign_list[-1] < length:
return sign_list[-1]
else:
return -1
-
结果
image
点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。
image
image
