피보나치 시퀀스를 작성하는 방법?
원래 프로그램을 잘못 코딩했습니다. 범위 (예 : startNumber 1, endNumber 20 = 1과 20 사이의 숫자 만) 사이에 피보나치 숫자를 반환하는 대신 프로그램이 범위 사이의 모든 피보나치 숫자 (예 : startNumber 1, endNumber 20)를 표시하도록 작성했습니다 표시 = 첫 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))
누군가 내 파트 II에서 지적했습니다 (이것은 복제로 인해 폐쇄되었습니다-https: //stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ) while 루프를 사용하여 생성기를 통해 startNumber 및 endNumber를 전달해야합니다. 누군가이 작업을 수행하는 방법에 대해 알려주십시오. 도움을 환영합니다.
저는 학습 프로그래머이며 약간 혼란에 빠졌습니다. 사용자가 입력 한 시작 번호와 끝 번호 (예 : startNumber = 20 endNumber = 100)로 피보나치 시퀀스를 계산하고 표시하는 프로그램을 작성하라는 메시지가 표시됩니다 (즉, 해당 범위 사이의 숫자 만 표시 함). 비결은 그것을 포괄적으로 사용하는 것입니다 (파이썬에서 어떻게 해야할지 모르겠습니까?-이것이 포괄적 인 범위를 사용한다고 가정합니다).
지금까지 내가 가진 것은 실제 코딩이 아니라 오히려 :
- Fib 시퀀스 수식을 무한대로 쓰기
- Fib 시퀀스에서만 startNumber를 endNumber로 표시합니다.
어디서부터 시작해야할지 전혀 몰라서 작성 방법에 대한 아이디어 나 통찰력을 요구하고 있습니다. 나는 또한 Fib 시퀀스 포럼을 작성하려고 시도했지만 그것도 잃어 버렸습니다.
Wikipedia 와 wolfram 에는 피보나치 수열에 관한 많은 정보가 있습니다. 필요한 것보다 훨씬 더. 어쨌든 이러한 리소스를 사용하여 필요한 것을 빨리 찾을 수있는 방법을 배우는 것이 좋습니다.
Fib 시퀀스 수식을 무한대로 쓰기
수학에서는 재귀 형태로 제공됩니다.
프로그래밍에는 무한대 가 존재하지 않습니다. 당신은 당신의 언어로 직접 수학 양식을 번역하는 재귀 양식을 사용할 수 있습니다.
def F(n):
if n == 0: return 0
elif n == 1: return 1
else: return F(n-1)+F(n-2)
좋아하는 언어로 시도하고 n이 커질수록 이 양식 에 많은 시간 이 필요하다는 것을 알 수 있습니다. 실제로 이것은 시간이 O (2 n )입니다.
내가 당신에게 링크 한 사이트로 이동하면 이것을 볼 수 있습니다 ( wolfram ) :
이것은 파이썬에서 구현하기 쉽고 계산하기가 매우 빠릅니다.
from math import sqrt
def F(n):
return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))
다른 방법은 wikipedia 의 정의를 따르는 것입니다 .
시퀀스의 첫 번째 숫자는 0이고 두 번째 숫자는 1이며 이후의 각 숫자는 시퀀스 자체의 이전 두 숫자의 합과 같으며 시퀀스 0, 1, 1, 2, 3, 5, 8을 생성합니다. 등
언어가 반복자를 지원하는 경우 다음과 같은 작업을 수행 할 수 있습니다.
def F():
a,b = 0,1
while True:
yield a
a, b = b, a + b
Fib 시퀀스에서만 startNumber를 endNumber로 표시합니다.
피보나치 수를 생성하는 방법을 알면 수를 순환하여 주어진 조건을 확인해야합니다.
이제 피보나치 수열의 n 번째 항 (sqrt (5)가있는 항)을 반환하는 af (n)을 작성했다고 가정하십시오.
대부분의 언어에서 다음과 같은 작업을 수행 할 수 있습니다.
def SubFib(startNumber, endNumber):
n = 0
cur = f(n)
while cur <= endNumber:
if startNumber <= cur:
print cur
n += 1
cur = f(n)
파이썬에서는 반복자 형식을 사용하고 다음을 수행합니다.
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 for it)가 다음과 같이 교육합니다 : P 행운을 즐겁게 보내십시오!
피보나치 시퀀스의 효율적인 파이썬 생성기
이 시퀀스의 가장 짧은 Pythonic 생성을 얻으려고 노력 하면서이 질문을 찾았습니다 (나중에 Python Enhancement Proposal 에서 비슷한 것을 보았습니다 ). 그리고 다른 사람이 내 특정 솔루션을 생각해 낸 것을 보지 못했습니다 (최상의 답변이지만) 가까워 지지만 여전히 우아하지는 않습니다.) 독자가 이해하는 데 도움이 될 수 있다고 생각하기 때문에 첫 번째 반복을 설명하는 주석이 있습니다.
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
(저는 저작자 표시를 위해 최근 에 모듈에 대한 파이썬 문서에서 변수 와를 사용하여 유사한 구현 을 발견했습니다 .이 답변을 작성하기 전에 보았던 것을 기억합니다. 그러나이 답변은 언어의 더 나은 사용법을 보여줍니다.)ab
재귀 적으로 정의 된 구현
정수 시퀀스 의 온라인 백과 사전은 피보나치 시퀀스를 다음과 같이 재귀 적으로 정의합니다.
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))
효율성을위한 메모 된 재귀
속도를 높이기 위해 메모 할 수 있습니다 (이 예제는 함수가 호출 될 때마다 기본 키워드 인수가 동일한 객체라는 사실을 이용하지만 일반적으로 정확하게 이러한 이유로 변경 가능한 기본 인수를 사용하지 않습니다).
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
메모 버전은 훨씬 빠르며 커피를 마시기 전에 최대 재귀 깊이를 빠르게 초과합니다. 이렇게하면 시각적으로 얼마나 빠른지 알 수 있습니다.
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())]
그러나 재귀 한계까지만 올라갈 수 있습니다. Haskell 버전은 최대 8 억 개까지 올라갈 수 있지만 노트북의 메모리는 8GB를 모두 사용하지만 일반적으로 1000입니다.
> 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))
피보나치 수열의 기본 개념은 다음 Python 코드에 나와 있습니다.
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 (1) 및 fib (0)의 정의를 알고 계산하여 fib (2)를 계산하지 않고 fib (3)을 계산할 수 없다는 것입니다. 피보나치 함수와 같이 함수 호출 자체를 재귀라고하며 프로그래밍에서 중요한 주제입니다.
숙제처럼 들리므로 시작 / 종료 부분은하지 않겠습니다. 파이썬은 이것에 대해 놀랍도록 표현적인 언어이므로 수학을 이해하면 재귀에 대해 가르쳐 줄 것입니다. 행운을 빕니다!
편집 : 내 코드에 대한 잠재적 비판 중 하나는 매우 유용한 Python 함수 수율을 사용하지 않으므로 fib (n) 함수가 훨씬 짧아진다는 것입니다. 파이썬 외부의 많은 언어가 실제로 수확량을 가지지 않기 때문에 내 예제는 조금 더 일반적입니다.
시간 복잡성 :
캐싱 기능은 피보나치 시리즈 의 재귀 트리에서 반복을 제거하여 피보나치 시리즈를 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 (log 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)
이것은 제곱에 의한 지수를 사용하여 다항식 고리 Z [X] / (X ^ 2-X-1)에서 X ^ n을 계산합니다. 이 계산의 결과는 다항식 Fib (n) X + Fib (n-1)이며 n 번째 피보나치 수를 읽을 수 있습니다.
다시, 이것은 O (log 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
우리는 알고
그리고 그 행렬의 n 번째 제곱은 다음과 같습니다.
따라서 우리는 n--1 -1 거듭 제곱으로 해당 행렬의 거듭 제곱을 간단히 계산하는 함수를 구현할 수 있습니다.
우리가 아는 바와 같이 a ^ n은
결국 피보나치 함수는 O (n) 일 것입니다 ... 우리가 알고 있고 따라서 복잡성으로 x^n * x^n = x^2n평가할 x^n수 있다는 사실이 아니라면 더 쉬운 구현과 크게 다르지 않습니다. )
신속한 프로그래밍 언어를 사용한 피보나치 구현은 다음과 같습니다.
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 (log n)를 갖습니다. 우리는 지수 n-1로 Q의 oìpower를 계산 한 다음 Fn + 1 인 m00 요소를 취합니다. n-1은 정확히 n 번째 피보나치 수입니다.
빠른 피보나치 기능이 있으면 시작 번호와 끝 번호를 반복하여 원하는 피보나치 시퀀스의 일부를 얻을 수 있습니다.
let sequence = (start...end).map(fibonacciFast)
물론 시작과 끝에서 몇 가지 검사를 수행하여 유효한 범위를 형성 할 수 있는지 확인하십시오.
나는 그 질문이 8 살이라는 것을 알고 있지만 어쨌든 대답하는 것은 즐거웠다. :)
재귀 사용 :
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)
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'에 할당하고 감소시키는 것은 파이썬에서 가장 강력한 세 가지 기능 중 두 가지입니다. 여기에서지도는 'n-2'번 반복하기 위해 사용됩니다. a [-2 :]는 배열의 마지막 두 요소를 가져옵니다. a.append (x + y)는 마지막 두 요소를 추가하고 배열에 추가합니다
OK .. 긴 답변을 모두 언급하는 데 지친 후 이제 피보나치를 파이썬으로 구현하는 아래의 정렬 및 달콤하고 매우 직선적 인 방법을 찾으십시오. 인수를 얻거나 사용자 입력을 가져 와서 원하는 방식으로 향상시킬 수 있습니다. 또는 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
편집 : 이 구현을위한 시각화 예 .
이것은 mathew henry의 답변을 개선했습니다.
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 ....
for 루프를 사용하여 결과 만 인쇄
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, 1712631191 , 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 106102098577523, 7806770072, 793676801, 793676801, 79367680190085
런타임 : 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 : 파이썬의 피보나치 수
이것은 피보나치 시리즈를 위해 파이썬에서 가장 간단한 것이지만 add ()에 의해 출력 배열에서 [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 개의 입력 숫자 (첫 번째 피보나치 수, 두 번째 숫자 및 시퀀스를 중단 할 수있는 숫자)에서 피보나치 시퀀스를 계산하는 프로그램을 작성하도록 요청했습니다. 이 튜토리얼에서는 if / thens 변수 만 다루었 고 그 시점까지 반복됩니다. 아직 기능이 없습니다. 다음 코드를 생각해 냈습니다.
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)
클래식 피보나치 수열을 기반으로 한 라이너를 위해
인덱스의 수만 필요하면 reduce를 사용할 수 있습니다 ( reduce 가 가장 적합하지 않더라도 좋은 연습이 될 수 있습니다)
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]
완전한 배열을 얻으려면 or (r.pop (0) and 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
참고 URL : https://stackoverflow.com/questions/494594/how-to-write-the-fibonacci-sequence
'Programing' 카테고리의 다른 글
| Json.NET은 스트림을 직렬화 / 역 직렬화 할 수 있습니까? (0) | 2020.06.27 |
|---|---|
| geoJSON 객체가 주어지면 d3에서지도 중앙에 (0) | 2020.06.27 |
| if 문의 할당 (0) | 2020.06.27 |
| JavaScript에서 텍스트를 바꾸어 JavaScript에서 str_replace를 수행하려면 어떻게해야합니까? (0) | 2020.06.27 |
| SVG에서 텍스트 요소의 수직 정렬 (0) | 2020.06.27 |