피보나치 수: 루프 및 재귀. 합리적인 시간에 3가지 방법으로 N번째 피보나치 수 찾기: 동적 프로그래밍 기본 사항
이 코드는 Python 3용이지만 Python 2에서도 작동해야 합니다.
먼저 정의를 상기시켜 드리겠습니다.
Fn \u003d Fn-1 + Fn-2
그리고 F 1 \u003d F 2 \u003d 1.
닫힌 공식
자세한 내용은 건너뛰겠지만 원하는 사람은 공식 유도에 익숙해질 수 있습니다. 아이디어는 F n = x n 인 x가 있다고 가정하고 x를 찾는 것입니다.무엇을
우리는 x n-2를 줄입니다.
이차 방정식을 풉니다.
여기서 "골든 섹션" ϕ=(1+√5)/2가 커집니다. 원래 값을 대체하고 더 많은 계산을 수행하면 다음을 얻습니다.
이것이 우리가 F n 을 계산하는 데 사용하는 것입니다.
__future__ import division import math def fib(n)에서: SQRT5 = math.sqrt(5) PHI = (SQRT5 + 1) / 2 return int(PHI ** n / SQRT5 + 0.5)
좋은:
소규모 n을 위한 빠르고 쉬운
나쁜:
부동 소수점 연산이 필요합니다. n이 클수록 더 많은 정밀도가 필요합니다.
사악한:
복소수를 사용하여 F n을 계산하는 것은 수학적 관점에서 보면 아름답지만 컴퓨터 관점에서는 보기 흉합니다.
재귀
이미 여러 번 본 가장 확실한 해결책은 재귀가 무엇인지에 대한 예일 가능성이 큽니다. 완전성을 위해 다시 반복하겠습니다. Python에서는 한 줄로 작성할 수 있습니다.fib = 람다 n: fib(n - 1) + fib(n - 2) if n > 2 else 1
좋은:
수학적 정의를 반복하는 매우 간단한 구현
나쁜:
기하급수적인 런타임. 큰 n의 경우 매우 느리게
사악한:
스택 오버플로
암기
재귀 솔루션에는 중복 계산이라는 큰 문제가 있습니다. fib(n)이 호출되면 fib(n-1) 및 fib(n-2)가 계산됩니다. 그러나 fib(n-1)이 계산되면 fib(n-2)가 독립적으로 다시 계산됩니다. 즉, fib(n-2)가 두 번 계산됩니다. 추론을 계속하면 fib(n-3)이 세 번 계산된다는 것을 알 수 있습니다. 교차로가 너무 많습니다.따라서 다시 계산하지 않도록 결과를 기억하면 됩니다. 이 솔루션은 선형 방식으로 시간과 메모리를 소비합니다. 솔루션에서 사전을 사용하고 있지만 간단한 배열도 사용할 수 있습니다.
M = (0: 0, 1: 1) def fib(n): if n in M: return M[n] M[n] = fib(n - 1) + fib(n - 2) return M[n]
(Python에서는 데코레이터 functools.lru_cache를 사용하여 이 작업을 수행할 수도 있습니다.)
좋은:
재귀를 기억 솔루션으로 바꾸십시오. 기하급수적 실행 시간을 더 많은 메모리를 소비하는 선형 실행 시간으로 바꿉니다.
나쁜:
많은 메모리 낭비
사악한:
재귀와 같은 가능한 스택 오버플로
동적 프로그래밍
암기로 풀면 이전 결과가 모두 필요하지 않고 마지막 두 개만 필요하다는 것이 분명해집니다. 또한 fib(n)에서 시작하여 뒤로 이동하는 대신 fib(0)에서 시작하여 앞으로 이동할 수 있습니다. 다음 코드에는 선형 실행 시간과 고정된 메모리 사용량이 있습니다. 실제로는 재귀 함수 호출 및 관련 작업이 없기 때문에 솔루션 속도가 훨씬 빠릅니다. 그리고 코드가 더 간단해 보입니다.이 솔루션은 종종 동적 프로그래밍의 예로 인용됩니다.
Def fib(n): a = 0 b = 1 for __ in range(n): a, b = b, a + b return a
좋은:
작은 n의 경우 빠르고 간단한 코드
나쁜:
여전히 선형 런타임
사악한:
예, 특별한 것은 없습니다.
행렬 대수학
마지막으로 가장 적게 다루었지만 시간과 메모리를 지능적으로 사용하는 가장 정확한 솔루션입니다. 또한 모든 균일한 선형 시퀀스로 확장할 수 있습니다. 아이디어는 행렬을 사용하는 것입니다. 그것만으로도 충분하다.
그리고 이것의 일반화는
우리가 이전에 얻은 x에 대한 두 값 중 하나는 황금비였으며 행렬의 고유값입니다. 따라서 닫힌 공식을 유도하는 또 다른 방법은 행렬 방정식과 선형 대수학을 사용하는 것입니다.
그렇다면 이 문구가 유용한 이유는 무엇입니까? 지수화는 대수 시간으로 수행될 수 있다는 사실. 이것은 제곱을 통해 이루어집니다. 결론은
여기서 첫 번째 표현식은 짝수 A에 사용되고 두 번째 표현식은 홀수에 사용됩니다. 행렬의 곱셈을 구성하는 것만 남아 있으며 모든 것이 준비되었습니다. 다음 코드가 나옵니다. 이해하기 쉽기 때문에 pow의 재귀 구현을 정리했습니다. 여기에서 반복 버전을 참조하십시오.
Def pow(x, n, I, mult): """ x를 n의 거듭제곱으로 반환합니다. I는 mult와 곱하는 항등 행렬이고 n은 양의 정수라고 가정합니다. """ if n == 0: return I elif n == 1: x 반환 else: y = pow(x, n // 2, I, mult) y = mult(y, y) if n % 2: y = mult(x, y) 반환 y def identity_matrix (n): """n x n 항등 행렬을 반환합니다.""" r = list(range(n)) return [ for j in r] def matrix_multiply(A, B): BT = list(zip(*B) ) return [ for row_a in A] def fib(n): F = pow([, ], n, identity_matrix(2), matrix_multiply) return F
좋은:
고정 메모리 크기, 로그 시간
나쁜:
코드가 더 복잡하다
사악한:
그렇게 나쁘지는 않지만 매트릭스로 작업해야합니다
성능 비교
동적 프로그래밍의 변형과 행렬만 비교할 가치가 있습니다. 숫자 n의 자릿수로 비교하면 행렬 솔루션이 선형이고 동적 프로그래밍을 사용한 솔루션이 지수함수임을 알 수 있습니다. 실용적인 예는 fib(10 ** 6)의 계산이며, 이 숫자는 20만 문자 이상을 포함합니다.N=10**6
fib_matrix 계산: fib(n)은 총 208988자리이며 계산에는 0.24993초가 걸렸습니다.
fib_dynamic 계산: fib(n)은 총 208988자리이며 계산에는 11.83377초가 걸렸습니다.
이론적 설명
위의 코드와 직접적인 관련이 없지만 이 설명은 여전히 흥미롭습니다. 다음 그래프를 고려하십시오.
A에서 B까지 길이가 n인 경로의 수를 세어 봅시다. 예를 들어, n = 1인 경우 하나의 경로인 1이 있습니다. n = 2인 경우 다시 하나의 경로인 01이 있습니다. n = 3인 경우 두 개의 경로가 있습니다. , 001 및 101 A에서 B까지의 길이가 n인 경로의 수가 정확히 F n임을 아주 간단하게 나타낼 수 있습니다. 그래프에 대한 인접 행렬을 작성하면 위에서 설명한 것과 동일한 행렬을 얻을 수 있습니다. 주어진 인접 행렬 A에 대해 An의 발생이 그래프에서 길이 n인 경로의 수라는 것은 그래프 이론에서 잘 알려진 결과입니다(영화 Good Will Hunting에서 언급된 문제 중 하나).
가장자리에 그러한 지정이 있는 이유는 무엇입니까? 그래프의 양방향 경로 시퀀스에서 무한한 기호의 무한 시퀀스를 고려할 때 기호 동역학 시스템의 유형인 "유한 유형의 하위 이동"이라는 것을 얻습니다. 구체적으로, 이 유한 유형의 하위 이동은 "황금 비율 이동"으로 알려져 있으며 "금지된 단어" 세트로 제공됩니다(11). 즉, 우리는 양방향으로 무한한 이진 시퀀스를 얻을 것이며 그 쌍은 인접하지 않을 것입니다. 이 동적 시스템의 위상 엔트로피는 황금비 φ와 같습니다. 이 숫자가 수학의 다른 영역에서 주기적으로 어떻게 나타나는지 흥미롭습니다.
피보나치 수- 이것은 각 다음 숫자가 이전 두 숫자의 합과 같은 일련의 숫자입니다: 1, 1, 2, 3, 5, 8, 13, .... 때때로 시리즈는 0부터 시작합니다: 0, 1, 1, 2, 3, 5, .... 이 경우 첫 번째 옵션을 고수합니다.
공식:
F1=1
F2 = 1
Fn \u003d Fn-1 + Fn-2
계산 예:
에프 3 \u003d 에프 2 + 에프 1 \u003d 1 + 1 \u003d 2
에프 4 \u003d 에프 3 + 에프 2 \u003d 2 + 1 \u003d 3
에프 5 \u003d 에프 4 + 에프 3 \u003d 3 + 2 \u003d 5
에프 6 \u003d 에프 5 + 에프 4 \u003d 5 + 3 \u003d 8
...
while 루프를 사용하여 피보나치 수열의 n번째 숫자 계산
- 변수 fib1 및 fib2에 계열의 처음 두 요소 값을 할당합니다. 즉, 변수에 단위를 할당합니다.
- 값을 얻고자 하는 요소의 번호를 사용자에게 요청합니다. 변수 n 에 숫자를 할당합니다.
- 처음 두 요소가 이미 고려되었으므로 다음 단계를 n - 2번 수행하십시오.
- fib1 및 fib2 를 추가하여 결과를 fib_sum 과 같은 임시 저장 변수에 할당합니다.
- fib1 을 fib2 로 설정합니다.
- fib2를 fib_sum으로 설정합니다.
- fib2 의 값을 표시합니다.
메모.사용자가 1 또는 2를 입력하면 루프 본문이 실행되지 않고 fib2의 원래 값이 표시됩니다.
fib1=1 fib2=1 n=input() n=int(n) i=0 동안 i< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)
코드의 압축 버전:
fib1 = fib2 = 1n = int(입력( "피보나치 수열의 요소 번호: ") ) - 2 n > 0인 경우: fib1, fib2 = fib2, fib1 + fib2 n -= 1 인쇄(fib2)
for 루프로 피보나치 수열 출력
이 경우 피보나치 수열의 원하는 요소 값뿐만 아니라 이를 포함하는 모든 숫자가 표시됩니다. 이를 위해 fib2 값의 출력이 루프에 배치됩니다.
fib1 = fib2 = 1 n = int (입력 () ) if n< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()
실행 예:
10 1 1 2 3 5 8 13 21 34 55
피보나치 수열의 n번째 숫자 재귀 계산
- n = 1 또는 n = 2이면 피보나치 수열의 첫 번째 요소와 두 번째 요소가 1이므로 호출 분기에 1을 반환합니다.
- 다른 모든 경우에는 인수 n - 1 및 n - 2를 사용하여 동일한 함수를 호출합니다. 두 호출의 결과를 추가하고 프로그램의 호출 분기로 반환합니다.
def fibonacci(n) : if n in (1 , 2 ) : return 1 return fibonacci(n - 1 ) + fibonacci(n - 2 ) print (fibonacci(10 ) )
n = 4라고 합시다. 그러면 fibonacci(3)과 fibonacci(2)가 재귀적으로 호출됩니다. 두 번째는 1을 반환하고 첫 번째는 fibonacci(2) 및 fibonacci(1)라는 함수 호출을 두 번 더 수행합니다. 두 호출 모두 하나를 반환하여 총 2개를 반환합니다. 따라서 fibonacci(3)에 대한 호출은 fibonacci(2)에 대한 호출의 숫자 1에 더해진 숫자 2를 반환합니다. 결과 3은 프로그램의 기본 분기로 반환됩니다. 피보나치 수열의 네 번째 요소는 3: 1 1 2 3입니다.
매우 자주 다양한 올림피아드에서 이와 같은 문제가 발생하는데, 언뜻보기에는 간단한 열거로 해결할 수 있습니다. 그러나 가능한 옵션의 수를 세면 우리는 이 접근 방식의 비효율성을 즉시 확신하게 될 것입니다. 예를 들어 아래의 간단한 재귀 함수는 이미 30번째 피보나치 수에서 상당한 리소스를 소비하는 반면 Olympiads에서는 솔루션 시간이 종종 제한됩니다. 1~5초.
int fibo(int n) ( if (n == 1 || n == 2) ( return 1; ) else ( return fibo(n - 1) + fibo(n - 2); ) )
왜 이런 일이 일어나는지 생각해 봅시다. 예를 들어, fibo(30)을 계산하려면 먼저 fibo(29) 및 fibo(28)를 계산합니다. 그러나 동시에 우리 프로그램은 우리가 fibo(28) 이미 계산 fibo(29)를 찾을 때.
이 정면 접근 방식의 주요 실수는 함수 인수의 동일한 값이 여러 번 계산된다는 것입니다. 이는 리소스 집약적 작업입니다. 동적 프로그래밍 방법은 반복적 인 계산을 제거하는 데 도움이 될 것입니다. 이것은 작업이 일반 및 반복적 하위 작업으로 나뉘는 기술이며 각 하위 작업은 한 번만 해결되므로 프로그램의 효율성이 크게 향상됩니다. 이 방법은 에 자세히 설명되어 있으며 다른 문제를 해결하는 예도 있습니다.
함수를 개선하는 가장 쉬운 방법은 이미 계산한 값을 기억하는 것입니다. 이렇게 하려면 계산을 위한 일종의 "캐시" 역할을 할 추가 배열을 도입해야 합니다. 새 값을 계산하기 전에 이전에 계산된 적이 있는지 확인합니다. 계산한 경우 배열에서 준비된 값을 가져오고 계산하지 않은 경우 이전 값을 기반으로 계산하고 미래를 위해 기억해야 합니다.
내부 캐시; int fibo(int n) ( if (cache[n] == 0) ( if (n == 1 || n == 2) ( cache[n] = 1; ) else ( cache[n] = fibo(n - 1) + fibo(n - 2); ) ) 반환 캐시[n]; )
이 작업에서 N번째 값을 계산하려면 (N-1)번째 값이 필요하므로 반복 형식으로 수식을 다시 작성하는 것은 어렵지 않습니다. 원하는 값에 도달할 때까지 배열을 한 행으로 채우기만 하면 됩니다. 셀:
<= n; i++) { cache[i] = cache + cache; } cout << cache;
이제 우리는 F(N)의 값을 계산할 때 F(N-3)의 값이 이미 우리에게 보장된다는 것을 알 수 있습니다. 절대필요하지 않습니다. 즉, 메모리에 F(N-1) 및 F(N-2) 의 두 값만 저장하면 충분합니다. 더욱이 F(N)을 계산하자마자 F(N-2)를 저장하는 것은 모든 의미를 잃습니다. 이러한 생각을 코드 형식으로 작성해 보겠습니다.
//두 개의 이전 값: int cache1 = 1; 정수 캐시2 = 1; //새 값 int cache3; for (int i = 2; i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 =>반복을 통해 cache2는 관련성을 잃습니다. 그것은 cache1 //즉, cache1 -- f(n-2), cache2 -- f(n-1), cache3 -- f(n)이 되어야 합니다. //N=n+1로 둡니다(다음 반복에서 계산할 숫자). 그러면 n-2=N-3, n-1=N-2, n=N-1입니다. //새로운 현실에 따라 변수 값을 다시 씁니다. cache1 = cache2; 캐시2 = 캐시3; ) 자르다<< cache3;
숙련된 프로그래머는 cache3이 사용되지 않고(즉시 cache2에 기록됨) 위의 코드가 일반적으로 말도 안 된다는 것을 이해하고 전체 반복은 단 하나의 표현식을 사용하여 다시 작성할 수 있습니다.
캐시=1; 캐시=1; for (int i = 2; i<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;
모듈로 마법이 어떻게 작동하는지 이해할 수 없거나 더 명확하지 않은 공식을 보고 싶은 사람들을 위해 다른 솔루션이 있습니다.
정수 x = 1; 정수 y = 1; for (int i = 2; i< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;
이 프로그램의 실행을 따르십시오. 알고리즘의 정확성을 확신하게 될 것입니다.
추신 일반적으로 반복이나 재귀가 필요하지 않은 피보나치 수를 계산하는 단일 공식이 있습니다.
Const double SQRT5 = sqrt(5); const 이중 PHI = (SQRT5 + 1) / 2; int fibo(int n)( return int(pow(PHI, n) / SQRT5 + 0.5); )
그러나 짐작할 수 있듯이 정수가 아닌 숫자의 거듭제곱을 계산하는 데 드는 비용과 오류가 상당히 큽니다.