斐波那契數列自第三個數開始,每個數均為之前兩個數的和。
至少有兩種方法來實現它。
最常見的利用叠代的方法,其核心思路是
fib(n) =?fib(n-1) +?fib(n-2)
而在n<2時直接,沒有n-2,因此直接返回1:
def fib(num): return 1 if n<2 else fib(num-1) + fib(num-2)
這是壹種很簡單的實現。在階梯數不大時,它很好用。當階梯數很大時,因為二次手叠代,會比較慢。因此,可以在計算中保存中間值(1至n-1的階梯數)來減少計算量:
這種方式在計算階梯數10000時就可以保持不錯的性能。如果需要多次計算該數列,則可以利用對象來保持這個中間值列表,下列代碼中,Fibonaci實例只計算未曾計算的階梯數,在重復調用時它更具優勢:
class Fibonaci(object):
....history=[1, 1]
....def cacl(self, num):
........while len(self.history) <= num:
............self.history.append(self.history[-1] + self.history[-2])
........return?self.history[num]
if __name__ == '__main__':
....fib =?Fibonaci()
....print(fib.calc(100))
....print(fib.calc(32))
....print(fib.calc(10000))