직접 수식을 사용하여 처음 n개의 피보나치 수를 인쇄합니다.

이 기사에서는 직접 공식을 사용하여 첫 번째 n 피보나치 수를 인쇄하는 문제를 해결합니다.

수학에서 피보나치 수는 종종 Fn(n번째 피보나치 수)으로 표시되며, 각 숫자가 이전 두 숫자의 합과 동일한 수열을 형성합니다. n번째 피보나치 수는 다음과 같이 표현될 수 있습니다 -

$$mathrm{Fn:=:F_{n-1}:+:F_{n-2}}$$

시리즈는 0과 1로 시작됩니다. 0과 1로 시작하는 피보나치 수열의 처음 몇 가지 값은 -

으아아아

그래서 이 문제에서는 숫자 N이 주어지며 직접 공식을 사용하여 첫 번째 N개의 피보나치 수열을 출력해야 합니다.

예

입력 : 4

출력: 0 1 1 2

입력 : 8

출력: 0 1 1 2 3 5 8 13

이 질문에 대해 우리는 n번째 피보나치 수를 얻기 위한 직접적인 공식을 제공하는 비네 공식의 개념을 이해해야 하며, 이에 대해서는 알고리즘 섹션에서 자세히 논의할 것입니다.

알고리즘

$mathrm{Fn:=:F_{n-1}:+:F_{n-2}}$ 공식에 따르면 (n-1)번째 항목과 (n- 2)번째 항목이 필요하고 이를 추가합니다. n번째 항목을 가져옵니다. 왜냐하면 이 문제에서는 n 번째 피보나치 수를 얻기 위해 직접 공식을 사용하여 처음 n 피보나치 수를 인쇄해야 하기 때문입니다.

피보나치 수열에서 n번째 피보나치 수를 얻으려면 Binet의 공식이라는 명시적 공식을 적용할 수 있습니다. 수학자 자크 필립 마리 비네(Jacques Philippe Marie Binet)가 창안했습니다.

공식

$mathrm{Fn}$이 피보나치 수열의 n번째 피보나치 수를 나타내는 경우 다음과 같이 표현할 수 있습니다.

$$mathrm{F_n:=:frac{1}{sqrt5}((frac{1+{sqrt5}}{2})^n:-:(frac{ 1-{sqrt5}}{2})^n )}$$

NOTE - 이 공식은 1과 1로 시작하는 피보나치 수열을 제공합니다. 0과 1에서 시작하는 피보나치 수열을 얻으려면 n-1을 사용하여 n번째 피보나치 수를 얻으십시오.

이차 방정식의 개념을 사용하여 이 공식을 유도할 수 있습니다. 이 공식을 사용하여 각 피보나치 수를 최대 n번째 피보나치 수까지 인쇄하여 첫 번째 n 피보나치 수를 인쇄합니다.

방법

• 0과 1부터 시작하는 피보나치 수열을 고려하므로 for 루프를 사용하여 0부터 n까지의 모든 N 피보나치 수열을 인쇄합니다.

• 변수를 피보나치 수로 초기화하고 i

• 계속해서 각 반복마다 피보나치 수를 인쇄하면 첫 번째 N 피보나치 수를 얻을 수 있습니다.

예

다음은 위 메서드를 C++로 구현한 것입니다.

으아아아

출력

으아아아

시간 복잡도: O(n), for 루프는 i가 n보다 작을 때까지 실행되기 때문입니다.

공간 복잡도: O(1), 추가 공간을 사용하지 않기 때문입니다.

결론

이 기사에서는 재귀를 사용하는 대신 직접 공식을 사용하여 첫 번째 N 피보나치 수를 인쇄하는 방법을 배웠습니다. 또한 피보나치 수열에서 n번째 피보나치 수를 직접 구할 수 있는 비네의 공식도 배웠습니다.

이 기사가 이 주제에 대한 모든 개념을 명확하게 하는 데 도움이 되었기를 바랍니다.

위 내용은 직접 수식을 사용하여 처음 n개의 피보나치 수를 인쇄합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!