어떻게 학습의 귀속을 합니까?

귀속 3 요소

1. 내 함수가 무엇을 하고 싶은지 명확히 하기

귀환에 있어서 가장 중요한 것은'이 함수의 기능이 무엇인지'를 분명히 하는 것이다.그것이 어떤 결과를 원하는지는 완전히 내가 정의한 것이다.
예를 들어 나는 먼저 함수를 정의했다.

    // n 
    int f(int n){
		return 0;
    }

목적성이 있는 함수가 생겼다. 다음은 두 번째 요소를 보자.

2. 귀속 종료 조건 찾기

정의된 함수 코드에서 자신을 호출하는 것이 바로 귀속이다.따라서 우리는 반드시 귀속되는 종결 조건을 명확히 해야 한다. 그렇지 않으면 블랙홀에 빠져 스스로 빠져나오기 어렵다.다시 말하면 매개 변수가 어떤 조건을 충족시킬 때 귀속이 끝나고 결과를 되돌려준다는 것이다.
이때 우리는 요소 2를 우리가 방금 정의한 함수에 섞었다.

// n 
    int f(int n){
        if (n==1){
            return 1;
        }
        return 0;
    }

3. 함수의 등가 관계식을 찾아라

함수 범위를 정확하게 축소하여 정확한 결과를 얻다.만일 우리의 등가 관계식이 f(n)=n*f(n-1)이라면

// n 
    int f(int n){
        if (n<=2){
            return n;
        }
        return n*f(n-1);
    }

다음은 몇 가지 사례를 통해 연습을 하겠습니다.

연습페보나체 수열

피보나치의 수열은 다음과 같은 수열이다. 1, 1, 2, 3, 5, 8, 13, 21, 34...즉 첫 번째 f(1)=1, 두 번째 f(2)=1..., n번째 항목은 f(n)=f(n-1)+f(n-2)이다.n항의 값이 얼마인지 구하다.
step1: 함수 기능 확인
f(n)의 목적은 n항의 값을 구하는 것이다.

int f(int n){
        
    }

step2: 반복 종료 조건 찾기
n<=2일 때 f(n)의 결과는 모두 1이기 때문에 귀속 종료 조건은 n<=2:

int f(int n){
        if (n<=2){
            return 1;
        }
    }

step3: 함수의 등가 관계식 찾기
제목의 등가 관계식은 f(n)=f(n-1)+f(n-2)이므로 최종 코드:

int f(int n){
        // 
        if (n<=2){
            return 1;
        }
        // 
        return f(n-1)+f(n-2);
    }

연습개구리가 계단을 뛰어내리다.

개구리 한 마리는 한 번에 1계단을 올라갈 수도 있고 2계단을 올라갈 수도 있다.이 개구리가 n급 계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해 보세요.
step1: 함수 기능 명확화
f(n)의 기능은 개구리가 n급 계단을 오르는 데 몇 가지 방법이 있다.

int f(int n){
        
    }

step2: 귀속 종료 조건 명시
n이 작을수록 f(n)의 결과는 직관적이다.n==1로 가정합니다.

int f(int n){
        if (n==1){
            return 1;
        }
    }

step3: 등가 관계식 찾기
여기에 모두 두 가지 점프법이 있는데 처음에 1급을 뛰거나 나머지 계단은 f(n-1)개 방안이 있다.아니면 2단계를 뛰기 시작했거나 나머지 계단은 f(n-2)개 방안이 있다.그래서 모든 방안은 두 가지 방식의 합이다.즉 f(n)=f(n-1)+f(n-2);

int f(int n){
    //f(0) = 0,f(1) = 1，  n<=1 ，f(n) = n。
    if(n <= 1){
        return n;
    }
    ruturn f(n-1) + f(n-2);
}

연습체인 테이블 반전

먼저 체인 테이블 노드를 정의합니다.

class Node{
        int data;
        Node next;
    }

step1.함수 기능을 정의하려면 다음과 같이 하십시오.
함수의 기능은 단일 체인 테이블을 반전시키는 것입니다.

Node reverseList(Node head){

}

step2.종료 조건 찾기:
체인 테이블의 노드 개수<=1일 때head로 되돌아오기

Node reverseList(Node head){
    if(head == null || head.next == null){
        return head;
    }
}

step3.등가 관계 결정:
reverseList(head) 등가reverseList(head.next) + 1, 2 두 노드의 지향 바꾸기

// 
 public static Node reverseList2(Node head){
     // 1. 
     if (head == null || head.next == null) {
              return head;
          }
         //    
          Node newList = reverseList2(head.next);
          //   1，2 。
         //   head.next 2
         Node t1  = head.next;
         //   2   next   2
         t1.next = head;
         // 1   next   null.
        head.next = null;
        //  。
        return newList;
    }

귀속 최적화

1. 반복 계산 문제

f(n)=f(n-1)+f(n-2) 과정에서 어떤 하위 원소는 여러 차례 중복 계산되었다.또한 n이 클수록 중복 계산의 횟수가 많고 범위가 넓어진다.일단 앞의 수치가 계산된 후에 우리는 다시 반복해서 계산할 필요가 없다.계산 결과에 대한 저장은 수조나 집합을 사용할 수 있습니다.

int f(int n){
     if(n <= 1){
         return n;
     }
     // 
     if(arr[n] != -1){
         // ， 
         return arr[n];
    }else{
        //  ， ,  arr 
        arr[n] = f(n-1) + f(n-1);
        reutrn arr[n];
    }
}

2. 사고를 역전시켜 아래에서 위로

귀속에 대해 우리의 사고방식은 대체로 위에서 아래로 귀착된다.만약 n이 무한히 크면 창고 공간이 부족한 문제를 초래할 수 있다.이러한 솔루션을 점진적이라고 합니다.

public int f(int n) {
        if(n <= 2)
            return n;
        int f1 = 1;
        int f2 = 2;
        int sum = 0;
 
        for (int i = 3; i <= n; i++) {
            sum = f1 + f2;
           f1 = f2;
           f2 = sum;
       }
       return sum;
   }