366. 피보나치 수열

2255 단어
피보나치 수열의 N번째 수를 찾아라.
이른바 피보나치 수열이란
앞의 두 수는 0과 1이다.i번째 수는 i-1번째 수와 i-2번째 수의 합이다.피보나치 수열의 10위 숫자는 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

귀속과 교체의 차이


차례로 돌아가다


기본 개념:
프로그램 호출 자체의 프로그래밍 기교를 귀속이라고 하는데 함수 자체가 자신을 호출하는 것이다.하나의 함수는 그 정의에서 자신의 방법을 직접 또는 간접적으로 호출하는데 보통 하나의 대형 복잡한 문제를 원 문제와 비슷한 규모가 비교적 작은 문제로 바꾸어 해결하면 코드량을 크게 줄일 수 있다.귀속의 능력은 유한한 문장으로 대상의 무한 집합을 정의하는 데 있다.귀속을 사용하는 데 주의해야 할 것은 두 가지가 있다. 1) 귀속은 과정이나 함수에서 자신을 호출하는 것이다.2) 귀속을 사용할 때 귀속 종료 조건이 명확해야 한다. 이를 귀속 출구라고 한다.
귀속은 다음 두 단계로 나뉩니다.
1) 점차적으로 추론: 복잡한 문제의 해답을 원래의 문제보다 간단한 문제의 해답으로 추론한다.2) 회귀: 가장 간단한 상황을 얻은 후에 점차적으로 되돌아와 순서대로 복잡한 해를 얻는다.

교체:


변수의 원값을 이용하여 변수의 새로운 값을 추산해 내다.만약에 귀속이 자신이 자신을 호출한다면 교체는 A가 끊임없이 호출되는 것이다. B. 귀속 중에는 반드시 교체가 있지만 교체 중에는 반드시 귀속이 있는 것이 아니라 대부분이 서로 전환할 수 있다.반복적으로 사용할 수 있는 것은 귀속되지 않고 귀속 호출 함수로 공간을 낭비하고 귀속이 너무 깊어서 창고의 넘침을 초래하기 쉽다.

1. 수조법

public class Solution {
    /*
     * @param n: an integer
     * @return: an integer f(n)
     */
    public int fibonacci(int n) {
        if(1 == n || 2 == n) {
            return n-1;
        }
        int[] fib = new int[n];
        fib[0] = 0;
        fib[1] = 1;
        for(int i = 2;i

2. 귀속법

public class Solution {
    /*
     * @param n: an integer
     * @return: an integer f(n)
     */
    public static int fibonacci(int n) {
        if(n < 0) {
            return -1;
        }
        else if(1== n) {
            return 0;
        }
        else if(2 == n) {
            return 1;
        }
        else{
            return fibonacci(n-1)+fibonacci(n-2);
        }
        // write your code here
}

3. 교체법(변수법)

public class Solution {
    /*
     * @param n: an integer
     * @return: an integer f(n)
     */
    public static int fibonacci(int n) {
        int a = 0;
        int b = 1;
        int tmp = 0;
        if(1 == n) {
            tmp = a;
        }
        if(2 == n) {
            tmp = b;
        }
        if(n>2) {
            for(int i = 2;i

좋은 웹페이지 즐겨찾기