[프로그래밍 문제] 제목:Fibonacci 수열 입력 n을 정의하고 가장 빠른 방법으로 이 수열의 n항을 구한다.
12232 단어 fibonacci
사고방식: 귀속과 비귀속의 아래 코드에 문제가 있는데 대수 경계를 고려하지 않았다.되돌아오는 값은 롱롱형으로 설정해야 한다
귀속 속도가 매우 느리다
/*
19 （ 、 ）：
： Fibonacci ：
/ 0 n=0
f(n)= 1 n=1
/ f(n-1)+f(n-2) n=2
n， n 。
start time 13:05
end time 13:16
*/
#include <stdio.h>
//
int Fibonacci(int n)
{
switch(n)
{
case 0:
return 0;
case 1:
return 1;
default:
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
//
int nonrecursionFibonacci(int n)
{
int a = 0, b = 1;
switch(n)
{
case 0:
return 0;
case 1:
return 1;
default:
{
for (int i = 0; i < n - 1; i++)
{
int c = a + b;
a = b;
b = c;
}
return b;
}
}
}
int main()
{
//int f = Fibonacci(10000);
int ff = nonrecursionFibonacci(10000);
return 0;
}인터넷에 O(logN) 해법이 있어요.
http://leowzy.iteye.com/blog/787947
이것은 아직 가장 빠른 방법이 아니다.다음은 시간 복잡도가 O(logn)인 방법을 소개한다.이런 방법을 소개하기 전에 먼저 수학 공식을 소개합니다. {f(n), f(n-1), f(n-1), f(n-2)} = {1, 1, 1,0} n-1(주: {f(n+1), f(n), f(n), f(n), f(n)}, f(n-1)}는 행렬을 나타냅니다.행렬에서 첫 번째 줄의 첫 번째 열은 f(n+1), 첫 번째 줄의 두 번째 열은 f(n), 두 번째 줄의 첫 번째 열은 f(n), 두 번째 줄의 두 번째 열은 f(n-1)이다.이 공식이 있으면 f(n)를 요구할 수 있다. 우리는 행렬 {1, 1, 1,0}의 n-1차방만 구할 수 있다. 왜냐하면 행렬 {1, 1, 1,0}의 n-1차방의 결과의 첫 번째 줄의 첫 번째 열은 f(n)이기 때문이다.이 수학 공식은 수학 귀납법으로 증명하기 어렵지 않다.관심 있는 친구는 스스로 증명해도 무방하다.현재 문제는 행렬 {1,1,1,0}의 곱셈으로 바뀌었습니다.만약 간단하게 0부터 순환하기 시작한다면 n차는 n차 연산을 필요로 할 것이며 앞의 방법보다 빠르지 않다.그러나 우리는 곱셈의 다음과 같은 성질을 고려할 수 있다./an/2*an/2n이 짝수일 때 an=\a(n-1)/2*a(n-1)/2n이 홀수일 때 n번을 요구한다. 우리는 먼저 n/2번을 구하고 n/2의 결과를 제곱한다.만약 n차원을 구하는 문제를 큰 문제로 간주한다면 n/2를 구하는 것을 비교적 작은 문제로 간주한다.이런 큰 문제를 하나 이상의 작은 문제로 분해하는 사고방식을 우리는 분치법이라고 부른다.이렇게 n차원을 구하면logn차 연산만 할 수 있다.이런 방식을 실현할 때, 우선 하나를 정의해야 한다.×2의 행렬, 그리고 행렬의 곱셈과 곱셈 연산을 정의한다.이 연산들이 정의되면 남은 일은 매우 간단해진다.완전한 실현 코드는 다음과 같다.
#include <cassert>
///////////////////////////////////////////////////////////////////////
// A 2 by 2 matrix
///////////////////////////////////////////////////////////////////////
struct Matrix2By2
{
Matrix2By2
(
long long m00 = 0,
long long m01 = 0,
long long m10 = 0,
long long m11 = 0
)
:m_00(m00), m_01(m01), m_10(m10), m_11(m11)
{
}
long long m_00;
long long m_01;
long long m_10;
long long m_11;
};
///////////////////////////////////////////////////////////////////////
// Multiply two matrices
// Input: matrix1 - the first matrix
// matrix2 - the second matrix
//Output: the production of two matrices
///////////////////////////////////////////////////////////////////////
Matrix2By2 MatrixMultiply
(
const Matrix2By2& matrix1,
const Matrix2By2& matrix2
)
{
return Matrix2By2(
matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
}
///////////////////////////////////////////////////////////////////////
// The nth power of matrix
// 1 1
// 1 0
///////////////////////////////////////////////////////////////////////
Matrix2By2 MatrixPower(unsigned int n)
{
assert(n > 0);
Matrix2By2 matrix;
if(n == 1)
{
matrix = Matrix2By2(1, 1, 1, 0);
}
else if(n % 2 == 0)
{
matrix = MatrixPower(n / 2);
matrix = MatrixMultiply(matrix, matrix);
}
else if(n % 2 == 1)
{
matrix = MatrixPower((n - 1) / 2);
matrix = MatrixMultiply(matrix, matrix);
matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
}
return matrix;
}
///////////////////////////////////////////////////////////////////////
// Calculate the nth item of Fibonacci Series using devide and conquer
///////////////////////////////////////////////////////////////////////
long long Fibonacci_Solution3(unsigned int n)
{
int result[2] = {0, 1};
if(n < 2)
return result[n];
Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
return PowerNMinus2.m_00;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
피보나치 (Programmers 12945)🧑💻 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예시 F(2) = F(0) + F(1) = 0 + 1 = 1 F...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
