데이터 구조 - 중요 한 귀속 알고리즘

2467 단어 데이터 구조
데이터 구조 - 재 귀 와 분할
재 귀 알고리즘: 컴퓨터 과학 에서 문 제 를 같은 하위 문제 로 반복 적 으로 분해 하여 문 제 를 해결 하 는 방법 을 말 합 니 다. 함수 가 자신 을 호출 하거나 함수 가 일련의 다른 함 수 를 호출 했 는데 그 중의 한 함 수 는 마지막 에 첫 번 째 함 수 를 다시 호출 했 습 니 다.
분 치 사상: 하나의 규 모 를 N 으로 하 는 문 제 를 k 개의 규모 가 작은 서브 문제 로 나 눌 수 있다. 이런 문 제 는 서로 독립 되 고 원래 의 문제 와 같 으 며 이런 문 제 를 재 귀적 으로 해결 한 다음 에 각 문제 의 해 를 합 쳐 원래 의 문 제 를 해결 할 수 있다.
재 귀 응용 - n 단계 곱 하기 문제 풀이
int factorial(int n){
    if(n==0)
        return 1;
    else
        return n*factorial(n-1);
}

재 귀적 응용 - 한 노 타 문제 풀이
알고리즘 사상:
  • 원통 A 의 맨 위 에 있 는 n - 1 개의 접 시 를 보조 기둥 B
  • 로 이동한다.
  • 원통 A 의 n 번 째 접 시 를 목표 기둥 C 로 이동
  • 보조 기둥 B 에 있 는 n - 1 개의 접 시 를 대상 기둥 C
  • 로 이동한다.
    본 사례 에서 한 노 타 문 제 를 해결 하고 사고 와 코드 는 왕 치 와 교수 데이터 구조 수업 의 총 결 에서 나온다.
    void move(int count,int start,int finish,int temp){
        if(count==1){
            cout<<"move disk "<<count<<" from "<" to "<else{
            move(count-1,start,temp,finish);
            cout<<"move disk "<<count<<" from "<" to "<count-1,temp,finish,start);
        }
    }

    재 귀적 으로 해결 할 수 있 는 문 제 는 크게 다음 과 같다.
  • 데이터 의 정 의 는 귀속 에 따라 정 의 된 것 이다.예 를 들 어 Fibonacci 함수
  • 문제 해법 은 재 귀 알고리즘 에 따라 이 루어 진다.예 를 들 어 하노이 문제
  • 데이터 의 구조 형식 은 재 귀 에 따라 정의 된다.예 를 들 어 이 진 트 리, 광의 표 등
  • 좋은 웹페이지 즐겨찾기