如何写的斐波那契数列的?
https://stackoverflow.com/questions/494594
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我原本编码的程序错误。而不是返回斐波那契数字之间的一个范围(即。startNumber1,endNumber20=只有那些数字之间的1&20)，我已经写程序，以显示所有斐波那契数字之间的一个范围(即。startNumber1,endNumber20显示=第20斐波那契数字)。我认为我有一个肯定火码。我也不明白为什么会发生这种情况。
startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))
def fib(n):
if n < 2:
return n
return fib(n-2) + fib(n-1)
print map(fib, range(startNumber, endNumber))
有人指出，在我的第二部分(这是封闭的，正在一个重复 https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii)，我需要通过startNumber和endNumber通过的发电机使用，同时循环。有人可以请我指的方向对如何做到这一点？任何帮助是受欢迎的。
我有学习程序员和我遇到一个有点混乱。我要求编写一个程序，将会计算并显示斐波那契的顺序由一个用户输入的起始号码和结束号码(ie。startNumber=20endNumber=100，它只会显示的数字之间的范围)。窍门是要用它包含(我不知道如何去做，在蟒蛇?-我假设这意味着使用一种包容性的范围？).
什么我有这么远远没有实际编码而是:
- 写时序列公式无限
- 显示startNumber到endNumber仅从Fib的顺序。
我没有想法从哪里开始，我要求的想法或者深入了解如何编写这一点。我也曾试图写时序列买来送人也是很不错的但我失去了这一点为好。
解决方案
有很多的信息有关的斐波那契数列在 维基百科 和上 wolfram.很多比你可能需要。无论如何这是一个良好的事情，以了解如何使用这些资源(如果可能的话)你需要什么。
写时序列公式无限
在数学，这是鉴于在递归的形式：
在编程， 无限 并不存在。你可以使用递归形式翻译的数学形式直接在你的语言，例如在蟒蛇就变为：
def F(n):
if n == 0: return 0
elif n == 1: return 1
else: return F(n-1)+F(n-2)
试试吧你最喜欢的语言和看到，这种形式要求 很多 时间为正变得更大。事实上，这是O(2n)在时间。
去网站上我与你会看到这一点(上 wolfram):
这个人是很容易实现的，非常，非常快速的计算，在蟒蛇：
from math import sqrt
def F(n):
return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))
其他的方式来做到这一点是以下定义(从 维基百科):
第一号的顺序为0， 第二个数字是1时，和每 随后的数总和等于 以前的两个号码的 序本身，产生的顺序 0, 1, 1, 2, 3, 5, 8, 等等。
如果你的语言支持迭代你可以做些什么，如：
def F():
a,b = 0,1
while True:
yield a
a, b = b, a + b
显示startNumber到endNumber仅从Fib的顺序。
一旦你知道如何生成的斐波那契数你只有周期低谷的数量和检查，如果他们确认给定的条件。
假设现在你写了一f(n)就返回的第n期的斐波那契数列(如与sqrt(5))
在大多数语言，你可以做一些事情，如：
def SubFib(startNumber, endNumber):
n = 0
cur = f(n)
while cur <= endNumber:
if startNumber <= cur:
print cur
n += 1
cur = f(n)
在python我会使用的迭代的形式和转用于：
def SubFib(startNumber, endNumber):
for cur in F():
if cur > endNumber: return
if cur >= startNumber:
yield cur
for i in SubFib(10, 200):
print i
我的提示 学习阅读 你需要什么。项目的欧拉(google为它)将训练你要做到这一点：P 运气好，有趣！
其他提示
有效的Python发生的斐波那契数列
我发现这个问题，同时试图获得最短的Python代的这个顺序(后来意识到我已经看到类似的一个中一个 蟒蛇增强的提案)，和我有没有注意到任何其他人来我的特定解决方案(尽管顶部回答接近，但仍然不太优雅)，因此这里就是，有评论意见中描述的第一次迭代，因为我认为，可帮助读者理解：
def fib():
a, b = 0, 1
while True: # First iteration:
yield a # yield 0 to start with and then
a, b = b, a + b # a will now be 1, and b will also be 1, (0 + 1)
和使用情况：
for index, fibonacci_number in zip(range(10), fib()):
print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))
打印：
0: 0
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55
(用于归属目的，我最近注意到一个 类似的执行情况 在Python文件上模块，即使使用的变量 a 和 b, 我现在记得有见过之前写这个的答案。但我认为这个答案表明更好地使用的语言。)
递归的定义的执行情况
的 网上百科全书的序列整数 定义的斐波那契数列的递归为
F(n)=F(n-1)+F(n-2)F(0)=0和F(1)=1
简明扼要地定义这一递归在蟒蛇可以做到如下：
def rec_fib(n):
'''inefficient recursive function as defined, returns Fibonacci number'''
if n > 1:
return rec_fib(n-1) + rec_fib(n-2)
return n
但是这种确切表示的数学定义是令人难以置信的效率低下的数字远远大于30的，因为每个数字计算还必须计算每个数目以下。你可以演示如何缓慢，这是通过使用如下：
for i in range(40):
print(i, rec_fib(i))
Memoized递归的效率
它可以memoized提高速度(这个例子利用的一个事实，即默认的关键参数是相同的对象的每一次的功能，但通常你不会用一个可变的默认的论据正是这个原因):
def mem_fib(n, _cache={}):
'''efficiently memoized recursive function, returns a Fibonacci number'''
if n in _cache:
return _cache[n]
elif n > 1:
return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
return n
你会找到memoized版本是要快得多，并将迅速超过了你的最大递归的深入之前你甚至可以认为得到了咖啡。你可以看到如何更快，这是在视觉上通过这样做：
for i in range(40):
print(i, mem_fib(i))
(它可能看起来喜欢我们可以做的如下，但是它实际上并没有让我们利用高速缓冲，因为它要求本身之前setdefault。)
def mem_fib(n, _cache={}):
'''don't do this'''
if n > 1:
return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
return n
递归定义发生器：
因为我已经学习Haskell，我遇到了这个执行在Haskell:
fib@(0:tfib) = 0:1: zipWith (+) fib tfib
最近的我想我可以得到这蟒蛇在的时刻是：
from itertools import tee
def fib():
yield 0
yield 1
# tee required, else with two fib()'s algorithm becomes quadratic
f, tf = tee(fib())
next(tf)
for a, b in zip(f, tf):
yield a + b
这表明：
[f for _, f in zip(range(999), fib())]
它只能去递归的限制，虽然。通常,1000,而Haskell的版本可以达到100万，尽管它使用的所有8个我的笔记本电脑的内存来这样做：
> length $ take 100000000 fib
100000000
为什么不只做以下?
x = [1,1]
for i in range(2, 10):
x.append(x[-1] + x[-2])
print(', '.join(str(y) for y in x))
背后的想法斐波纳契数列示在以下代码:
def fib(n):
if n == 1:
return 1
elif n == 0:
return 0
else:
return fib(n-1) + fib(n-2)
这意味着fib是一个功能，可以做到三件事情之一。它定义了fib(1)==1,fib(0)==0，并fib(n)：
fib(n-1)+fib(n-2)
其中n为任意整数。这意味着fib(2)例如，扩大了以下运算：
fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1
我们可以计算出fib(3)同样的方式运算下所示：
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0
重要的是要意识到这是fib(3)不可能计算不算撒谎(2),其中计算知道该定义的fib(1)和fib(0).具有功能称自己喜欢的斐波那契数被称为递归，这是一个重要的议题在方案编制。
这听起来像家庭作业所以我不打算这样做的起点/终点的一部分用于你。蟒蛇是一个奇妙的语言表达对这个不过，这应该是有意义的，如果你了解数学，并希望能教给你的关于递归。祝你好运！
编辑：一个潜在批评我的代码，它不会使用超级-方便Python功能产率，这使得撒谎(n)的功能很短。我的例子是一点点更为通用，虽然，由于没有很多种语言之外Python实际产量。
时间的复杂性：
缓冲功能，减少了正常的方式计算斐波那契数列从 O(2^n) 要 O(n) 通过消除重复在递归树的斐波那契数列:
代码:
import sys
table = [0]*1000
def FastFib(n):
if n<=1:
return n
else:
if(table[n-1]==0):
table[n-1] = FastFib(n-1)
if(table[n-2]==0):
table[n-2] = FastFib(n-2)
table[n] = table[n-1] + table[n-2]
return table[n]
def main():
print('Enter a number : ')
num = int(sys.stdin.readline())
print(FastFib(num))
if __name__=='__main__':
main()
这是相当有效的，使用O(日志n)基本的算术运算。
def fib(n):
return pow(2 << n, n + 1, (4 << 2*n) - (2 << n) - 1) % (2 << n)
这一个使用O(1)基本的算术运算，但大小的中间结果是大型和所以是不是在所有有效的。
def fib(n):
return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)
这一计算X^正在多项环Z[X]/(X^2-X-1)使用指数的平方。结果计算是多项式Fib(n)X+Fib(n-1)，从其第n斐波那契数可以阅读。
再次，这种使用O(日志n)的算术运算和是非常高效的。
def mul(a, b):
return a[0]*b[1]+a[1]*b[0]+a[0]*b[0], a[0]*b[0]+a[1]*b[1]
def fib(n):
x, r = (1, 0), (0, 1)
while n:
if n & 1: r = mul(r, x)
x = mul(x, x)
n >>= 1
return r[0]
典型代码，以印刷斐波纳契数列:
a,b=1,1
while True:
print a,
a,b=b,a+b # Could also use b=a+b;a=b-a
对问题"的打印的第一个斐波纳契数大于1000的数字长的":
a,b=1,1
i=1
while len(str(a))<=1000:
i=i+1
a,b=b,a+b
print i,len(str(a)),a
使用递归:
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
x=input('which fibonnaci do you want?')
print fib(x)
我们知道
，N力的矩阵，为我们提供了:
因此，我们可以实现的功能，简单地计算源的矩阵的第n-1的权力。
如我们所知道的电a^n等于
因此，在结束斐波纳契数职能将O(n)...真的没什么不同于一种更容易的执行情况，如果不是因为事实上，我们也知道， x^n * x^n = x^2n 和评价 x^n 因此可以完成的复杂性O(日志n)
这里是我的斐波那契执行swift使用编程语言：
struct Mat {
var m00: Int
var m01: Int
var m10: Int
var m11: Int
}
func pow(m: Mat, n: Int) -> Mat {
guard n > 1 else { return m }
let temp = pow(m: m, n: n/2)
var result = matMultiply(a: temp, b: temp)
if n%2 != 0 {
result = matMultiply(a: result, b: Mat(m00: 1, m01: 1, m10: 1, m11: 0))
}
return result
}
func matMultiply(a: Mat, b: Mat) -> Mat {
let m00 = a.m00 * b.m00 + a.m01 * b.m10
let m01 = a.m00 * b.m01 + a.m01 * b.m11
let m10 = a.m10 * b.m00 + a.m11 * b.m10
let m11 = a.m10 * b.m01 + a.m11 * b.m11
return Mat(m00: m00, m01: m01, m10: m10, m11: m11)
}
func fibonacciFast(n: Int) -> Int {
guard n > 0 else { return 0 }
let m = Mat(m00: 1, m01: 1, m10: 1, m11: 0)
return pow(m: m, n: n-1).m00
}
这个具有复杂性O(日志n)。我们计算oìpower的问与指数n-1然后我们把元素m00其Fn+1在权力指数n-1是完全n斐波那契数，我们想要的。
一旦你有了快速的斐波那契数功能可以重从起始号码和结束号码，以获得的一部分，斐波纳契数列。
let sequence = (start...end).map(fibonacciFast)
当然首先执行一些检查开始和结束，以确保它们可以形成一个有效范围。
我知道问题是8岁，但我必须有趣的回答。:)
def fib():
a,b = 1,1
num=eval(input("Please input what Fib number you want to be calculated: "))
num_int=int(num-2)
for i in range (num_int):
a,b=b,a+b
print(b)
所有这些看起来有点复杂得多，他们需要的人。我的代码是非常简单和快速：
def fibonacci(x):
List = []
f = 1
List.append(f)
List.append(f) #because the fibonacci sequence has two 1's at first
while f<=x:
f = List[-1] + List[-2] #says that f = the sum of the last two f's in the series
List.append(f)
else:
List.remove(List[-1]) #because the code lists the fibonacci number one past x. Not necessary, but defines the code better
for i in range(0, len(List)):
print List[i] #prints it in series form instead of list form. Also not necessary
另一种方式这样做:
a,n=[0,1],10
map(lambda i: reduce(lambda x,y: a.append(x+y),a[-2:]),range(n-2))
分配名单的'a'，将整数为'n' 地图和减少2的三个最强大的功能在蟒蛇。地图在这里是用来循环'n-2'倍。一个[-2:]将获得最后两个要素的一个阵列。a.append(x+y)将添加的最后二个要件，并将追加的阵列
好..后疲倦的参考所有的冗长的答案，现在找到下面的排序和甜，非常直接的方式实现的斐波那契素。你可以增强它你想要的方式获得通过一种参数或得到用户输入...或改变限制从10000次。因为你需要......
def fibonacci():
start = 0
i = 1
lt = []
lt.append(start)
while start < 10000:
start += i
lt.append(start)
i = sum(lt[-2:])
lt.append(i)
print "The Fibonaccii series: ", lt
这种方法还执行良好。找到运行的分析下
In [10]: %timeit fibonacci
10000000 loops, best of 3: 26.3 ns per loop
斐波那契数列的是： 1, 1, 2, 3, 5, 8, ....
就是 f(1) = 1, f(2) = 1, f(3) = 2, ..., f(n) = f(n-1) + f(n-2).
我最喜欢的执行情况(最简单的和尚未实现一个光速度比其他的实现)是这样的：
def fibonacci(n):
a, b = 0, 1
for _ in range(1, n):
a, b = b, a + b
return b
测试
>>> [fibonacci(i) for i in range(1, 10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34]
时间
>>> %%time
>>> fibonacci(100**3)
CPU times: user 9.65 s, sys: 9.44 ms, total: 9.66 s
Wall time: 9.66 s
编辑： 一个例子可视化 为这实现的。
这是一个改善马修*亨利的回答：
def fib(n):
a = 0
b = 1
for i in range(1,n+1):
c = a + b
print b
a = b
b = c
该代码应该打印b，而不是印刷c
输出：1,1,2,3,5....
使用对环和打印结果
def fib(n:'upto n number')->int:
if n==0:
return 0
elif n==1:
return 1
a=0
b=1
for i in range(0,n-1):
b=a+b
a=b-a
return b
结果，
>>>fib(50)
12586269025
>>>>
>>> fib(100)
354224848179261915075
>>>
印 list 包含所有的号码
def fib(n:'upto n number')->int:
l=[0,1]
if n==0:
return l[0]
elif n==1:
return l
a=0
b=1
for i in range(0,n-1):
b=a+b
a=b-a
l.append(b)
return l
结果，
>>> fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
import time
start_time = time.time()
#recursive solution
def fib(x, y, upperLimit):
return [x] + fib(y, (x+y), upperLimit) if x < upperLimit else [x]
#To test :
print(fib(0,1,40000000000000))
print("run time: " + str(time.time() - start_time))
结果，
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853]
运行时间： 0.04298138618469238
有一个非常简单的方法来实现这一点！
你可以运行，这个代码网上自由使用 http://www.learnpython.org/
# Set the variable brian on line 3!
def fib(n):
"""This is documentation string for function. It'll be available by fib.__doc__()
Return a list containing the Fibonacci series up to n."""
result = []
a = 0
b = 1
while a < n:
result.append(a) # 0 1 1 2 3 5 8 (13) break
tmp_var = b # 1 1 2 3 5 8 13
b = a + b # 1 2 3 5 8 13 21
a = tmp_var # 1 1 2 3 5 8 13
# print(a)
return result
print(fib(10))
# result should be this: [0, 1, 1, 2, 3, 5, 8]
基本上翻译从红宝石：
def fib(n):
a = 0
b = 1
for i in range(1,n+1):
c = a + b
print c
a = b
b = c
...
def fib(lowerbound, upperbound):
x = 0
y = 1
while x <= upperbound:
if (x >= lowerbound):
yield x
x, y = y, x + y
startNumber = 10
endNumber = 100
for fib_sequence in fib(startNumber, endNumber):
print "And the next number is... %d!" % fib_sequence
递归增加的时间。消灭的循环，首先 import math.然后使用 math.sqrt 和黄金比率中的一种功能：
#!/usr/bin/env python3
import math
def fib(n):
gr = (1 + math.sqrt(5)) / 2
fib_first = (gr**n - (1 - gr)**n) / math.sqrt(5)
return int(round(fib_first))
fib_final = fib(100)
print(fib_final)
ref: 斐波那契数字在蟒蛇
这是最简单的一个python为斐波那契数列，但调整[0]在输出阵列的追加()导致的结果列表的第二个变量 result.append(second)
def fibo(num):
first = 0
second = 1
result = [0]
print('Fibonacci series is')
for i in range(0,num):
third = first + second
#print(second)
result.append(second)
first = second
second = third
print(result)
return
fibo(7)
输出
Fibonacci series is
[0, 1, 1, 2, 3, 5, 8, 13]
使用的附加功能，以产生第一个100的要素。
def generate():
series = [0, 1]
for i in range(0, 100):
series.append(series[i] + series[i+1])
return series
print(generate())
15分钟到我教程时所使用的学习蟒蛇，它要求读者编写一个计划，将计算一个斐波纳契数列从3输入的数字(第斐波那契数量、第二号和数量，在其停止序列)。该教程只复盖的变量，如果/处和循环到这一点。没有功能。我想出了下列代码：
sum = 0
endingnumber = 1
print "\n.:Fibonacci sequence:.\n"
firstnumber = input("Enter the first number: ")
secondnumber = input("Enter the second number: ")
endingnumber = input("Enter the number to stop at: ")
if secondnumber < firstnumber:
print "\nSecond number must be bigger than the first number!!!\n"
else:
while sum <= endingnumber:
print firstnumber
if secondnumber > endingnumber:
break
else:
print secondnumber
sum = firstnumber + secondnumber
firstnumber = sum
secondnumber = secondnumber + sum
正如你可以看到，这是真的效率很低，但它的工作。
只是走过 http://projecteuler.net/problem=2 这是我带上它
# Even Fibonacci numbers
# Problem 2
def get_fibonacci(size):
numbers = [1,2]
while size > len(numbers):
next_fibonacci = numbers[-1]+numbers[-2]
numbers.append(next_fibonacci)
print numbers
get_fibonacci(20)
def fib(x, y, n):
if n < 1:
return x, y, n
else:
return fib(y, x + y, n - 1)
print fib(0, 1, 4)
(3, 5, 0)
#
def fib(x, y, n):
if n > 1:
for item in fib(y, x + y, n - 1):
yield item
yield x, y, n
f = fib(0, 1, 12)
f.next()
(89, 144, 1)
f.next()[0]
55
也许这将帮助
def fibo(n):
result = []
a, b = 0, 1
while b < n:
result.append(b)
a, b = b, b + a
return result
试试这个：
def nth_fib(n):
if n == 0:
return 1
elif n == 1:
return 0
else:
return nth_fib(n - 1) + nth_fib(n - 2)
根据经典的斐波那契数列的，只是为了一个派
如果你只是需要数量的索引，可以使用的减少 (即使 减少 这不是最适合这个它可以是一个很好的锻炼)
def fibonacci(index):
return reduce(lambda r,v: r.append(r[-1]+r[-2]) or (r.pop(0) and 0) or r , xrange(index), [0, 1])[1]
并且以获得完整的阵只是删除了 或者(r.pop(0)0)
reduce(lambda r,v: r.append(r[-1]+r[-2]) or r , xrange(last_index), [0, 1])
这个怎么样？我猜这不是因为看中的其他建议，因为它要求的初步说明以前的结果，以产生预期的产出，但我的感觉是一个可读性很强的选择，即，它所做的是提供结果和以前的结果递归。
#count the number of recursions
num_rec = 0
def fibonacci(num, prev, num_rec, cycles):
num_rec = num_rec + 1
if num == 0 and prev == 0:
result = 0;
num = 1;
else:
result = num + prev
print(result)
if num_rec == cycles:
print("done")
else:
fibonacci(result, num, num_rec, cycles)
#Run the fibonacci function 10 times
fibonacci(0, 0, num_rec, 10)
这里的输出：
0
1
1
2
3
5
8
13
21
34
done
