검 지 Offer - 009 - 피 보 나치 수열

링크
우 객 OJ: 피 보 나치 수열
구도 OJ:http://ac.jobdu.com/problem.php?pid=1387
GitHub 코드: 009 - 피 보 나치 수열
CSDN 문제 풀이: 검 지 Offer – 009 - 피 보 나치 수열
우 객 OJ
구도 OJ
CSDN 문제 풀이
GitHub 코드
피 보 나치 수열
1387 - 피 보 나치 수열
검 지 Offer – 009 - 피 보 나치 수열
009 - 피 보 나치 수열
참고:
검 지 Offer 면접 문제 9 (자바 버 전) 피 보 나치 수열
O (logn) 시간 복잡 도 Fibonacci 수열 구하 기
검 지 offer 9 번 문제 및 확장 피 보 나치 수열
제목
제목 설명
모두 가 피 보 나치 수열 을 알 고 있 습 니 다. 지금 은 정수 n 을 입력 하 라 고 요구 하고 있 습 니 다. 피 보 나치 수열 의 n 번 째 항목 을 출력 해 주 십시오.
전달 공식
우 리 는 쉽게 전달 공식 f (n) = * = 0, n = 0 * = 1, n = 1 * = f (n - 1) + f (n - 2) 를 생각 했 기 때문에 우 리 는 바로 다음 과 같은 재 귀 코드 를 생각 했다.

    int Fibonacci(int n)
    {
        if(n <= 1)
        {
            return n;
        }
        else
        {
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }

근 데 죄송합니다.사실 재 귀적 인 방법 으로 계산 하 는 시간 복잡 도 는 n 의 지수 방식 으로 점점 증가한다.독자 들 은 피 보 나치 의 100 항 을 구 해도 무방 하 다.
재 귀적 전개 - 교체 방법 O (N)
그래서 우 리 는 가장 일반적인 방법 으로 전달 공식 을 펼 칠 수 밖 에 없다.

#include <iostream>

using namespace std;

//     
#define __tmain main

#ifdef __tmain

#define debug cout

#else

#define debug 0 && cout

#endif // __tmain


class Solution
{

public:
    int Fibonacci(int n)
    {
        if(n <= 1)
        {
            return n;
        }
        long one = 0;
        long two = 1;;
        long res = 0;

        for(int i = 2; i <= n; i++)
        {
            res = one + two;

            one = two;
            two = res;
        }

        return res;
    }
};

int __tmain( )
{
    Solution solu;
    cout <<solu.Fibonacci(3) <<endl;;

    return 0;
}

이 알고리즘 은 아직 가장 빠 른 방법 이 아니다.다음은 시간 복잡 도가 O (logn) 인 방법 을 소개 한다.
시간 복잡 도 는 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 - 1)} 은 행렬 을 표시 합 니 다. 행렬 에서 첫 번 째 줄 의 첫 번 째 열 은 f (n + 1) 이 고, 첫 번 째 줄 의 두 번 째 열 은 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/2                      n    
an=
        \  a(n-1)/2*a(n-1)/2            n    

n 제곱 을 요구 하면 우 리 는 먼저 n / 2 제곱 을 구하 고 n / 2 의 결 과 를 제곱 한다.n 을 구 하 는 문 제 를 큰 문제 로 본다 면 n / 2 를 구 하 는 것 을 작은 문제 로 본다.이런 큰 문 제 를 하나 또는 여러 개의 작은 문제 로 분해 하 는 사고방식 을 우 리 는 그것 을 분 치 법 이 라 고 부른다.이렇게 n 제곱 을 구하 면 logn 차 연산 만 필요 합 니 다.
이런 방식 을 실현 하려 면 먼저 2 를 정의 해 야 한다.×2 의 행렬, 그리고 행렬 의 곱셈 과 곱셈 연산 을 정의 합 니 다.이 연산 들 이 정 의 된 후에 남 은 일 은 매우 간단 해 졌 다.완전한 실현 코드 는 다음 과 같다.
원리: 관찰: a (n) = a (n - 1) + a (n - 1) + a (n - 2) = 2 * a (n - 2) + a (n - 3) = 3 * a (n - 3) + 2 * a (n - 3) + 2 * a (n - 4) = 5 * a (n - 4) + 3 * a (k) * a (n - k + 1) + a (n - k + 1) + a (n - k - 1) + a (k - 1) * a (n - k - 1) * a (n - k) 1) * a (n - k) 1 (n - k) 1) * a (n - k) 1) * a (k - k) 1) * a (k - k) 1) * a (k - k) 1) * a (k) 1) 1 (k (k) + a (k - 1)] + a (k - 1) * a (k) = a (k) ^ 2 + 2 * a (k) * a (k - 1) 2,만약 n = 2k - 1 득 a (2k - 1) = a (k) * a (k) + a (k - 1) * a (k - 1) = a (k) ^ 2 + a (k - 1) ^ 2
코드 는 다음 과 같다.

#include <iostream>

using namespace std;

//     
#define __tmain main

#ifdef __tmain

#define debug cout

#else

#define debug 0 && cout

#endif // __tmain


class Solution
{
public :
    static int pre;
    static int post;
    int temp;
    int Fibonacci(int n)
    {
        /** *   Fibonacci     : * pre:     Fibonacci(n)   * post:     Fibonacci(n-1)   */

        // if n = 0 #=> 0
        // else n = 1 || n = 2 #=> 1
        if(n <= 2)
        {
            if (n == 0) return 0;
            pre = 1;
            post = 1;
            return pre;
        }

        // n    ，       ，      
        // pre： f(n) = f(n - 1) + f(n - 2)
        // post： f(n - 1) = f(n) - f(n - 2)
        if(n%2 == 1)
        {
            Fibonacci(n-1);
            pre = pre + post;
            post = pre - post;
            return pre;
        }

        // n        
        //      ,f(n)    f(n/2)    :
        //
        //   n = 2k：
        // f(2k) = f(k) * f(k + 1) + f(k-1) * f(k)
        // = f(k) * [f(k) + f(k - 1)] + f(k-1) * f(k)
        // = f(k) ^ 2 + 2 * f(k) * f(k - 1)
        //   n = 2k-1：
        // f(2k - 1) = f(k) * f(k) + f(k - 1) * f(k - 1)
        // = f(k)^2 + f(k - 1)^2
        //
        Fibonacci(n/2);
        temp = pre;
        // f(2k) = f(k)^2 + 2 * f(k) * f(k - 1)
        pre = pre * pre + 2 * pre * post;
        // f(2k - 1) = f(k) * f(k) + f(k - 1) * f(k - 1)
        post = temp*temp + post*post;
        return pre;
    }
};

int Solution::pre = 0;
int Solution::post = 0;


int __tmain( )
{
    Solution solu;
    cout <<solu.Fibonacci(3) <<endl;;

    return 0;
}

한 단계 확장
제목 설명
개구리 한 마 리 는 한 번 에 1 단 계단 을 뛰 어 올 라 갈 수도 있 고 2 단 계단 을 뛰 어 올 라 갈 수도 있다.이 개구리 가 n 급 계단 을 뛰 어 올 라 가 는 데 는 모두 몇 가지 점프 방법 이 있 습 니까?
분석 하 다.
한 번 에 한 단계 만 뛰 거나 두 단계 만 뛰 면 N 단계 로 나 눌 수 있 습 니 다.

1 단 계 를 먼저 뛰 고 나머지 는 N - 1 단 계 를 뛰 는 것 이다.

2 단 계 를 먼저 뛰 고 나머지 는 N - 2 단 계 를 뛰 는 것 이다.

그러면 그것 의 전달 공식 은?

= 0, n = 0

= 1, n = 1

= 2, n = 2

= f (n - 1) + f (n - 2), 기타

코드

#include <iostream>

using namespace std;

//     
#define __tmain main

#ifdef __tmain

#define debug cout

#else

#define debug 0 && cout

#endif // __tmain


class Solution
{

public:
    int jumpFloor(int n)
    {
        if(n <= 2)
        {
            return n;
        }
        long one = 1;
        long two = 2;;
        long res = 0;

        for(int i = 3; i <= n; i++)
        {
            res = one + two;

            one = two;
            two = res;
        }

        return res;
    }


};

int __tmain( )
{
    Solution solu;
    cout <<solu.jumpFloor(2) <<endl;;

    return 0;
}

확장 2 – 변태 계단 뛰 어 내리 기
제목 설명
개구리 한 마리 가 한 번 에 1 단 계단 을 올 라 갈 수도 있 고, 2 단 계단 을 올 라 갈 수도 있 고, n 단 계단 을 올 라 갈 수도 있다.이 개구리 가 n 급 계단 을 뛰 어 올 라 가 는 데 는 모두 몇 가지 점프 방법 이 있 습 니까?
분석 하 다.
본 문제 에 대하 여 전 제 는 n 개의 계단 에 n 단계 의 도약 법 이 있다 는 것 이다.분석 은 다음 과 같다.
f (1) = 1 f (2) = f (2 - 1) + f (2 - 2) / / f (2 - 2) 는 2 단계 1 회 2 단계 점프 횟수 를 나타 낸다.f(3) = f(3-1) + f(3-2) + f(3-3) … f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n)
설명:

이곳 의 f (n) 는 n 개의 계단 이 1, 2, n 단계 의 점프 수 를 대표 한다.

n = 1 시 1 가지 점프 법 만 있 고 f (1) = 1

n = 2 시 에 두 가지 점프 방식 이 있 는데 한 번 에 1 단계 또는 2 단계 가 있 는데 이것 은 문제 (1), f (2) = f (2 - 1) + f (2 - 2)

로 돌 아 왔 다.

n = 3 시 3 가지 점프 방법 이 있 습 니 다. 1 단계, 2 단계, 3 단계, 그러면 첫 번 째 1 단계 점프 후 남 은 것 은 f (3 - 1) 입 니 다.첫 2 단계 뛰 기, f (3 - 2) 남 음;첫 번 째 3 단계, 그러면 f (3 - 3) 가 남 았 기 때문에 결론 은 f (3) = f (3 - 1) + f (3 - 2) + f (3 - 3)

이다.

n = n 시 n 중 뛰 기 방식, 1 단계, 2 단계... n 단계, 결론: f (n) = f (n - 1) + f (n - 2) +... + f (n - 1) + f (n - n) = > f (0) + f (1) + f (2) + f (3) +... + f (n - 1)

이상 은 이미 하나의 결론 이지 만, 간단 하기 위해 서 는 계속 간소화 할 수 있다: f (n - 1) = f (0) + f (1) + f (1) + f (2) + f (2) + f (3) + f (n - 1) = f (0) + f (1) + f (2) + f (3) + f (3) +... + f (n - 2) f (n) f (n) = f (0) + f (0) + f (1) + f (2) + f (2) + f (n - 2) + f (n - 2) + f (n - 2) + f (n - 1) + f (n - 1) + f (n - 1) + f (n - 1) f (n - f (n - 2) = f (n - f (n - 1)

최종 결론 을 내 렸 다. n 단계 계단 에서 한 번 에 1, 2, n 단계 의 점프 방식 이 있 을 때 반드시 점프 하 는 방법 은 다음 과 같다.

1 ,(n=0 )

1 ,(n=1 )

2*f(n-1),(n>=2)

코드

#include <iostream>

using namespace std;

//     
#define __tmain main

#ifdef __tmain

#define debug cout

#else

#define debug 0 && cout

#endif // __tmain


class Solution
{

public :
    int jumpFloorII(int target)
    {
        if (target <= 0)
        {
            return -1;
        }
        else if (target == 1)
        {
            return 1;
        }
        else
        {
            return 2 * jumpFloorII(target - 1);
        }
    }
};



int __tmain( )
{
    Solution solu;
    cout <<solu.jumpFloorII(2) <<endl;;

    return 0;
}

혹은

class Solution
{

public :
    int jumpFloorII(int target)
    {
        if (target <= 0)
        {
            return -1;
        }
        else
        {
            return pow(2, target - 1);
        }
    }
};

아니면 더 효율 적 인...

#include <iostream>

using namespace std;

//     
#define __tmain main

#ifdef __tmain

#define debug cout

#else

#define debug 0 && cout

#endif // __tmain


class Solution
{

public :
    int jumpFloorII(int target)
    {
        long long ret;
        if(target >= 32)//  8   ，       ，    
        {
            ret = 1 << 30;
            ret = ret << (target - 31);
        }
        else
        {
            ret = 1 << (target - 1);
        }

        return ret;
    }
};



int __tmain( )
{
    Solution solu;
    cout <<solu.jumpFloorII(2) <<endl;;

    return 0;
}

확장 3 – 사각형 덮어 쓰기
제목 설명
우 리 는 2 * 1 의 작은 사각형 으로 가로 또는 세로 로 더 큰 사각형 을 덮 을 수 있다.n 개 2 * 1 의 작은 사각형 으로 2 * n 의 큰 사각형 을 중첩 없 이 덮 는 방법 은 모두 몇 가지 가 있 습 니까?
분석 하 다.
2 * n 의 직사각형 방법 수 는 f (n) 로 정의 합 니 다.
첫 번 째 2 * 1 의 작은 사각형 은 큰 사각형 의 왼쪽 을 덮 고,

세로 로 놓 거나 f (n - 1) 로 바 꾸 거나

가로로 두 번 놓 거나 f (n - 2) 로 전환

따라서 f (n) = f (n - 1) + f (n - 2)

1 n = 0

1 n = 1

f(n - 1) + f(n - 2)

코드

#include <iostream>

using namespace std;

//     
#define __tmain main

#ifdef __tmain

#define debug cout

#else

#define debug 0 && cout

#endif // __tmain


class Solution
{

public:
    int rectCover(int n)
    {
        if(n  == 0)
        {
            return 1;
        }
        else if(n == 1)
        {
            return 1;
        }

        long one = 1;
        long two = 1;
        long res = 0;

        for(int i = 2; i <= n; i++)
        {
            res = one + two;

            one = two;
            two = res;
        }

        return res;
    }


};

int __tmain( )
{
    Solution solu;
    cout <<solu.rectCover(2) <<endl;;

    return 0;
}