python实现Fibonacci和二分法

时间：2010-11-24 来源：于江朋

def Fibonacci(n):
    if n <= 1:
         return 1
    else:
         return Fibonacci(n-1) + Fibonacci(n-2)

我们可以用一个数组存储，牺牲空间换取时间，避免多次无效求值

代码代码
list = [1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

def Fibonacci(n):
    if list[n] != 0:
        return list[n]
    else:
        list[n] = Fibonacci(n-1) + Fibonacci(n-2)
        return list[n]

二分法

代码 def BinarySearch(numbers,x,n):
    left = 0;right = n - 1
    while(left <= right):
        middle = (left + right)/2
        if numbers[middle] == x:
            return middle + 1
        elif numbers[middle] > x:
            right = middle-1
        else:
            left = middle + 1
    else:
        return -1

相关阅读更多 +