추이와 귀속(구별)

4958 단어 프로그램 지식차례차례

차례로 미루고 귀속시키다


본고의 일부 내용은 다른 사람의 블로그에서 옮겨졌고 작가의 관련 정보와 블로그 주소는 글 끝에 있다.
 

콘셉트

  • 귀속: 이미 알고 있는 문제의 결과에서 출발하여 교체 표현식으로 문제의 시작 조건, 즉 순추법의 역과정을 점차적으로 추산하여 귀속이라고 한다.

    •  
  • 귀속의 정의: 한 함수의 정의에서 직접 또는 간접적으로 그 자체를 호출한다.

    •  
  • 귀속사상: 규모가 크고 해결하기 어려운 문제를 규모가 작고 해결하기 쉬운 동일한 문제로 바꾸었다.규모가 비교적 작은 문제는 규모가 더 작은 문제로 변하고 어느 정도에 그 해를 직접 얻어 원래의 문제를 풀 수 있다.

    •  
  • 귀속 장점: 사람의 사고방식에 부합되고 귀속 절차의 구조가 뚜렷하며 읽을 수 있고 이해하기 쉽다
    •  
  • 귀속 결점: 호출 함수를 통해 귀속 층수가 너무 많으면 프로그램의 효율이 낮다.예를 들어 Fibonacii 수열의 1000항?

    •  
  • 귀속의 응용 장소:
    • 1. 데이터의 정의 형식은 귀속적이다. 예를 들어Fibonacii 수열의 n항을 구한다.
    2. 데이터 간의 논리적 관계(즉 데이터 구조)는 트리, 그림 등 정의와 조작에 귀속된다.
    3. 일부 문제는 뚜렷한 귀속 관계나 구조가 없지만 문제의 해법은 한 조의 조작을 계속 반복적으로 집행하는 것이다. 단지 문제의 규모가 커지고 작아지면서 특정한 원 조작(기본 조작)이 끝날 때까지 한다.예컨대 한노타 문제.
  • 귀속 디자인의 요소:
    • 1. 함수에 자신의 문장을 직접 또는 간접적으로 호출해야 한다.
    2. 귀속 전략을 사용할 때 반드시 명확한 귀속 종결 조건이 있어야 한다. 이를 귀속 수출(또는 귀속 경계)이라고 한다.

     


    반복 알고리즘을 작성할 때는 먼저 다음 세 가지 문제를 분석해야 합니다.

  • 문제 규모를 결정하는 매개 변수.     

    • 귀속 알고리즘으로 해결해야 할 문제는 그 규모가 보통 비교적 큰데 문제에서 규모의 크기(또는 문제의 복잡도)를 결정하는 양은 어떤 것들이 있습니까?찾아내.
  • 문제의 경계 조건과 경계 값.     

    • 어떤 상황에서 문제의 해답을 직접 얻어낼 수 있습니까?이것이 바로 문제의 경계 조건과 경계 값이다.
  • 문제 해결의 통식.     

    • 규모가 크고 해결하기 어려운 문제를 규모가 작고 해결하기 쉬운 동일한 문제로 바꾸려면 어떤 절차나 공식을 통해 실현해야 합니까?이것은 귀속 문제를 해결하는 난점이다.이 절차나 공식을 확정해라.
     
     
  • 추이: 추이 알고리즘은 몇 걸음의 반복 연산으로 복잡한 문제를 묘사하는 방법이다.추이는 서열 계산에서 자주 사용하는 알고리즘이다.일반적으로 컴퓨터 앞의 일부 항목을 통해 서열에 지정된 이미지의 값을 얻어낸다.

    •  
  • 추이: 수학 추도 발견 규칙 중복 단순 연산
    •  
  • 귀속과 추이의 차이: 추이 알고리즘에 비해 추이 알고리즘은 데이터가 창고에 들어오는 과정을 면제한다. 즉, 함수가 끊임없이 경계값에 접근할 필요가 없고 경계에서 출발하여 함수값을 구할 때까지 직접적으로 경계값을 구한다.

    • 알고리즘 예1


     
  • 피보나치 수열: 이미 알고 있는 f(1)=1, f(2)=1, 관계식 f(n)=f(n-1)+f(n-2)를 만족시키면 f(50)는 얼마입니까?

    •  
  • 분석: 초기 조건 f(1)=1, f(2)=1과 관계식 f(n)=f(n)=f(n-1)+f(n-2)를 보면 알 수 있듯이 f(3)=f(2)+f(1), f(3)=f(2)+f(1)......

    •  
  • 코드 작성(귀속)
    • public class Fibonacci {

    static int fun(int n){
        if(n == 1 || n == 2){
            return 1 ;
        }else{
            return fun(n-1) + fun(n-2) ;
        }
    }
    public static void main(String[] args) {
        for(int i = 1 ; i <= 15 ; ++i)
        System.out.println(fun(i));
    }
}

     
  • 코드 작성(점차적)
    • static int fun2(int n){
        int a[] = new int[20] ;
        a[1] = 1 ;
        a[2] = 1 ;
        for(int i=3 ; i<=n ;i++){
            a[i] = a[i-1] + a[i-2] ;
        }
        return a[n] ;
    }

     
  • 실행 결과:
    • 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

    알고리즘 예제 2


     
  • 귀속계산을 사용하여 1+2+...+100;

    •  
  • 분석: 귀속 관계는 f(n)=f(n-1)+n이고 귀속 수출은 f(1)=1이다.

    •  
  • 코드 작성(귀속): 
    • public class Sum {

    static int fun(int n){
        if( n == 1){
            return 1 ;
        }else{
            return fun(n-1) + n ;
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(fun(100));
    }
}

     
  • 코드 작성(점차적)
    • static int fun2(int n){
        int a[] = new int [200] ;
        a[1] = 1 ;
        for(int i=2 ; i<=n ; i++){
            a[i] = a[i-1] + i ;
        }
        return a[n] ;
    }

     
  • 실행 결과:
    • 5050

    알고리즘 예제 3


     
  • 계단 오르기 문제: n계단이 있다고 가정하면 매번 1단계 또는 2단계를 올라갈 수 있다면 n층까지 올라가는 몇 가지 방안이 있습니까?

    •  
  • 문제 분석:
  • 1 단계를 가설할 때 하나의 방안만 f(1)=1;
  • 2 단계에는 두 가지 방안이 있다(즉 한 번에 한 단계와 한 번에 두 단계) f(2)=2;
  • 3 단계 시 3가지 f(3)=3;
  • 4 단계에는 5가지 f(5)=5가 있다.
  • 귀속법칙 f(n)=f(n-1)+f(n-2) 발견;
  • 귀속수출은 f(1)=1, f(2)=2이다.

    •  
  • 코드 작성(귀속): 
    • public class Ladder {

    static int fun(int n){
        if(n == 1){
            return 1 ;
        }else if(n == 2){
            return 2 ;
        }else{
            return fun(n-1) + fun(n-2) ;
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(fun(5));
    }
}

     
  • 코드 작성(점진): 
    • static int fun2(int n){
        int a[] = new int [200] ;
        a[1] = 1 ;
        a[2] = 2 ;
        for(int i=3 ; i<=n ;i++){
            a[i] = a[i-1] + a[i-2] ;
        }
        return a[n] ;
    }

     
  • 실행 결과:
    • 8
    상술한 예에서 알 수 있듯이 귀환의 중점은 귀환 관계와 귀환 수출을 찾는 것이다.
    요약 정보:
    1. 미루는 것은 이미 알고 있는 조건에서부터 시작한다.
    2. 추이는 반드시 명확한 통용 공식이 있어야 한다.
    3. 추이는 반드시 유한 회 연산이어야 한다.
    반복 요약:
    1. 귀속: 미지의 것을 이미 알고 있는 것으로 미루고 여기서 귀환한다.
    2. 기본 사상: 복잡한 조작을 약간의 중복된 간단한 조작으로 분해한다.
     
    추이와 귀속에 관한 글은 다음과 같다.
    1. https://blog.csdn.net/a1046765624/article/details/66530637
    2.---------------------------------저자: 잎사귀 청일 출처: CSDN 원문:https://blog.csdn.net/u013634252/article/details/80551060판권 성명: 본고는 블로거의 오리지널 문장입니다. 옮겨 싣기 위해 블로거 링크를 첨부하세요!
    알고리즘 도론 학습 노트 (3) 초고
    귀속 사례

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage