Python 언어의 피보나치 수

피보나치 수는 첫 번째 값이 0으로 미리 선언되고 두 번째 값이 1로 미리 선언된 특정 시퀀스입니다. 나머지 숫자는 앞의 두 숫자를 더하여 이 두 숫자에서 생성됩니다. 모든 피보나치 수는 0부터 시작하는 양의 정수입니다. 처음 12개의 피보나치 수와 구하는 방법은 다음과 같습니다.

0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89

합계 표현식이 없으면 이러한 피보나치 수를 다음과 같이 표에 넣을 수 있습니다.

첫 번째 행은 피보나치 수입니다. 두 번째 행은 피보나치 숫자가 배열에 있다고 가정할 때 0부터 시작하는 인덱스를 갖습니다.

피보나치 수는 O(n) 시간과 O(1) 시간에 생성할 수 있습니다. 이러한 시간 복잡도 표현에서 n은 n개의 주요 연산을 의미하고 1은 1개의 주요 연산을 의미한다. O(n)을 사용하면 0부터 시작하여 n개의 피보나치 수를 생성합니다. O(1)을 사용하면 해당 인덱스에서 하나의 피보나치 수를 생성합니다. 그렇기 때문에 n개의 주요 작업 대신 하나의 주요 작업만 필요합니다.

이 기사의 목적은 Python을 사용하여 피보나치 수를 생성하는 방법을 설명하는 것입니다.

피보나치 수 공식

피보나치 수의 공식 정의는 다음과 같습니다.

여기서 F _N 0부터 시작하는 n

O(n) 시간에 피보나치 수 생성하기

n이 1이면 0만 피보나치 수로 인쇄됩니다. n이 2이면 0과 1이 순서대로 피보나치 수로 인쇄됩니다. n이 3이면 0, 1, 1이 순서대로 피보나치 수로 인쇄됩니다. n이 4이면 0, 1, 1, 2가 그 순서대로 피보나치 수로 인쇄됩니다. n이 5이면 0, 1, 1, 2, 3이 순서대로 피보나치 수로 인쇄됩니다. n이 6이면 0, 1, 1, 2, 3, 5가 그 순서대로 피보나치 수로 인쇄됩니다.

처음 n개의 피보나치 수를 생성하는 Python 함수는 다음과 같습니다.

모두 0으로 초기화된 n개 요소의 배열을 만드는 것으로 시작합니다. 이 배열은 피보나치 수를 보유합니다. 첫 번째 피보나치 수인 0이 이미 있습니다. 두 번째 피보나치 수인 1은 (함수에서) 다음 명령문에 의해 할당됩니다. 그런 다음 인덱스 2에서 시작하여 n 바로 앞에 있는 for 루프가 있습니다. 다음과 같은 진술이 있습니다.

이것은 바로 앞의 두 숫자를 더합니다.

함수를 호출하고 처음 12개의 피보나치 수를 인쇄하는 코드는 다음과 같습니다.

N = 12
A = 피보나치(N)
범위(N)의 i에 대해:
인쇄(A[i], 끝=' ')
인쇄()

출력은 다음과 같습니다.

일정한 시간에 하나의 피보나치 수 생성하기

0부터 시작하는 인덱스를 해당 피보나치 수와 연결하는 수학 공식이 있습니다. 공식은 다음과 같습니다.

방정식의 오른쪽에서 n의 거듭제곱은 5의 제곱근이 아닙니다. n의 거듭제곱은 괄호 안의 표현식입니다. 그런 표현이 두 가지 있습니다.

n이 0이면 Fibn은 0이 됩니다. n이 1이면 Fib _N 1이 됩니다. n이 2이면 Fib _N 1이 됩니다. n이 3이면 Fib _N n이 4이면 Fib _N 3 등일 것입니다. 독자는 n에 다른 값을 대입하고 평가하여 이 공식을 수학적으로 확인할 수 있습니다. n은 이 공식에서 0부터 시작하는 인덱스입니다.

이 수식에 대한 Python 코드는 다음과 같습니다.

수입 수학

수학 모듈을 가져왔습니다. 제곱근 기능이 있습니다. 연산자 **는 전원에 사용됩니다. fibNo() 함수는 공식을 직접 구현합니다. fibNo() 함수에 대한 적절한 호출 및 인쇄는 다음과 같습니다.

N = 11
오른쪽 = fibNo(N)
인쇄(ret)

출력은 다음과 같습니다.

답에서 불필요한 소수 자릿수를 제거하는 것이 가능합니다. 그러나 그것은 다른 시간 동안의 논의입니다.

서로 다른 n개의 인덱스에 대해 서로 다른 피보나치 수가 필요한 경우 함수 fibNo()는 서로 다른 해당 피보나치 수를 반환하기 위해 n개의 인덱스 각각에 대해 한 번 호출되어야 합니다. 다음 프로그램은 0부터 시작하는 인덱스, 7에서 9(포함)에 대해 이 작업을 수행합니다.

수입 수학

출력은 다음과 같습니다.

for 루프가 Python에서 코딩된 방식에 유의하십시오. 첫 번째 인덱스는 7입니다. 다음 인덱스는 8이고 마지막 인덱스는 9입니다. range 인수의 10은 9 + 1입니다. 10 위치의 값은 마지막 0부터 시작하는 인덱스에 1을 더한 값이어야 합니다. 인수 7은 0부터 시작하는 인덱스입니다.

결론

피보나치 수는 정수(양의 정수)의 특정 시퀀스입니다. 0으로 시작하고 무조건 1이 따라옵니다. 나머지 숫자는 바로 앞의 두 숫자를 더하여 거기에서 개발됩니다.

처음 n개의 피보나치 수를 얻으려면 0과 1을 처음 두 개로 받아들이고 나머지에 대해서는 다음과 같은 문과 함께 for 루프를 사용합니다.

바로 앞의 두 숫자를 더합니다.

0부터 시작하는 인덱스 n에서 단 하나의 피보나치 수를 얻으려면 다음 공식을 사용하십시오.