import math
import sys
sys.setrecursionlimit(8000000)
f = {1:2,2:3,3:5}
def fib(n):
if n in f:
return f[n]
if n == 1:
return 2
if n == 2:
return 3
if n == 3:
return 5
val = fib(n-1) + fib(n-2)
if n not in f:
f[n] = val
return f[n]%1000000007
print(fib(4000))
이 코드를 완료하지 못하거나 명령 프롬프트가 충돌합니다. 어떻게하면 더 좋을까요?
이 프로그램을 완료하기 위해 활성화해야하는 설정이 있습니까?
수학적 정의에서 직접 피보나치 수열을 구현하는 것은 재귀 솔루션의 문제를 보여주는 연습입니다. 현대 컴퓨터조차도 처리 할 수없는 재귀 함수 호출의 폭발적인 폭발로 이어집니다. 가장 큰 문제는의 큰 값에 대해 지수 횟수를 n계산 fib(1)한다는 것 입니다.
이 문제에 대한 몇 가지 해결책이 있습니다.
메모를 사용하여 이미 계산 된 값을 저장합니다. 그런 다음 계산 된 값을 찾아 추가 계산을 수행하지 않고 즉시 반환합니다. 이것은 메모가 어떻게 작동하는지 배우는 좋은 연습입니다. 그러나 여전히 불필요하게 재귀 함수 호출을 실행하기 때문에 여전히 비효율적입니다.
반복적 인 솔루션을 구현하십시오. 여기서는 자세히 설명하지 않겠습니다. fib(n)지수 시간 대신 선형 시간으로 구현할 반복 솔루션을 찾기 위해 몇 가지 연구를 수행하는 것이 좋습니다 .
닫힌 공식을 구현하십시오. 수학자들은 이미 fib(n)닫힌 공식으로 풀었 습니다. 이 솔루션은 아무리 많이 n사용 하더라도 일정한 시간이 걸립니다 .
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다