한 노 타 문제 재 귀 알고리즘 분석

가다http://www.360doc.com/content/12/0727/11/219024_226737868.shtml）
재 귀 는 어떤 유형의 나선형 while 순환 을 실현 했다.while 순환 은 순환 체 가 실 행 될 때마다 어떤 진전 을 이 루어 순환 종료 조건 에 점점 가 까 워 져 야 한다.
재 귀 함수 도 마찬가지 입 니 다. 재 귀 호출 할 때마다 특정한 제한 조건 에 점점 가 까 워 져 야 합 니 다.재 귀 함수 가 이 제한 조건 에 부합 할 때, 그것 은 자신 을 호출 하지 않 습 니 다.
귀속 알고리즘 의 특징
재 귀 알고리즘 은 자신 을 직접 또는 간접 적 으로 호출 하 는 알고리즘 이다.컴퓨터 작성 프로그램 에서 재 귀 알고리즘 은 큰 문 제 를 해결 하 는 데 매우 효과 적 이 며 알고리즘 에 대한 설명 이 간결 하고 이해 하기 쉽다.
귀속 알고리즘 이 문 제 를 해결 하 는 특징:
(1) 재 귀 는 과정 이나 함수 에서 자신 을 호출 하 는 것 이다.
(2) 재 귀 전략 을 사용 할 때 반드시 명확 한 재 귀 종료 조건 이 있어 야 하 며 재 귀 출구 라 고 부른다.
(3) 재 귀 알고리즘 은 문 제 를 푸 는 것 이 간결 해 보이 지만 재 귀 알고리즘 은 문 제 를 푸 는 운행 효율 이 비교적 낮다.그래서 일반적으로 귀속 알고리즘 으로 프로그램 을 설계 하 는 것 을 제창 하지 않 는 다.
(4) 재 귀적 호출 과정 에서 시스템 은 각 층 의 반환 점, 국 지적 양 등 을 위해 스 택 을 열 어 저장 했다.재 귀 횟수 가 너무 많 으 면 스 택 이 넘 치기 쉽다.그래서 일반적으로 귀속 알고리즘 으로 프로그램 을 설계 하 는 것 을 제창 하지 않 는 다.
재 귀 알고리즘 요구
재 귀 알고리즘 에 나타 난 '중복' 은 보통 세 가지 요구 가 있다.
첫째, 매번 호출 할 때마다 규모 가 축소 된다.
둘째, 인접 한 두 번 의 반복 사이 에 밀접 한 관 계 를 가진다. 첫 번 째 는 다음 을 위해 준비 해 야 한다 (보통 앞의 출력 은 다음 의 입력 으로 한다).
셋째, 문제 의 규모 가 매우 큰 시간 에 반드시 직접 해답 을 제시 하고 재 귀적 호출 을 하지 않 아야 하기 때문에 매번 재 귀적 호출 은 조건 이 있다 (규모 가 직접 해답 의 크기 에 이 르 지 못 하 는 것 을 조건 으로). 무조건 재 귀적 호출 은 순환 이 되 어 정상적으로 끝나 지 못 할 것 이다.한 절 에 기둥 이 세 개 있 고 첫 번 째 는 64 개의 접시 가 있 으 며 위 에서 아래로 접시 가 점점 커진다.절 안의 늙 은 스님 에 게 이 64 개의 접 시 를 모두 세 번 째 기둥 으로 옮 겨 달라 고 요구 하 다.이동 할 때 는 작은 접시 만 큰 접 시 를 누 를 수 있다.그리고 매번 하나만 움 직 일 수 있어 요.
1. 이때 늙 은 스님 (뒤에서 우리 가 그 를 첫 번 째 스님 이 라 고 부른다) 은 매우 어렵다 고 생각 했다. 그래서 그 는 한 사람 이 앞의 63 개의 접 시 를 두 번 째 기둥 으로 먼저 옮 길 수 있다 면 나 는 마지막 접 시 를 세 번 째 기둥 으로 직접 옮 기 고 그 사람 에 게 아까 의 63 개의 접 시 를 두 번 째 기둥 에서 세 번 째 기둥 으로 옮 기 면 나의 임 무 를 완성 할 수 있 을 것 이 라 고 생각 했다.간단 하 다그래서 그 는 그 보다 젊 은 스님 을 찾 아 명령 했다.

      ①     63           

      ②        64             

      ③    63            

  2、         ，     ，             ：         62             ，                   ，          62                   ，        ，  。             （          ），  ：

      ①    62           

      ②        63             

      ③    62           

3. 세 번 째 스님 은 임 무 를 맡 고 61 번 째 접 시 를 옮 기 는 임 무 를 조롱박 으로 네 번 째 스님 에 게 바 가 지 를 건 네 주 었 습 니 다. 등등 64 번 째 스님 에 게 임 무 를 맡 길 때 까지 미 루 었 습 니 다.
4. 이 임 무 를 맡 기 고 각자 맡 은 일 을 완성 할 때 가 되 었 습 니 다.리 턴 완료:
64 번 째 스님 은 첫 번 째 접 시 를 옮 겨 놓 고 63 번 째 스님 은 자신 이 나 눠 준 두 번 째 접 시 를 옮 겼 다.64 번 째 스님 은 첫 번 째 접 시 를 두 번 째 접시 로 옮 겼 다.여기까지 64 번 째 스님 의 임 무 를 완수 하고 63 번 째 스님 은 62 번 째 스님 이 맡 긴 임 무 를 수행 하 는 첫걸음 을 내 디 뎠 다.
위 에서 보 듯 이 64 번 째 스님 의 임 무 를 완수 해 야 63 번 째 스님 의 임 무 를 완수 할 수 있 고, 2 번 째 스님 - 64 번 째 스님 의 임 무 를 완수 해 야 첫 번 째 스님 의 임 무 를 완수 할 수 있다.이것 은 전형 적 인 귀속 문제 다.
/**************************************************************/
/*
지금 우 리 는 세 개의 접시 로 분석 하고 있다.
첫 번 째 스님 명령:
① 두 번 째 스님 은 먼저 첫 번 째 기둥 앞의 두 접 시 를 두 번 째 기둥 으로 옮 겨 라.(세 번 째 기둥 을 빌려)
② 첫 번 째 스님 은 첫 번 째 기둥 의 마지막 접 시 를 세 번 째 기둥 으로 옮 깁 니 다.
③ 두 번 째 스님 은 앞의 두 접 시 를 두 번 째 기둥 에서 세 번 째 기둥 으로 옮 겨 라.
두 번 째 단 계 는 쉽게 이 루어 진 다 는 것 이 분명 하 다.
그 중 첫 번 째 단 계 는 두 번 째 스님 에 게 접시 가 두 개 있 었 고 그 는 명령 했다.
① 세 번 째 스님 은 첫 번 째 기둥 의 첫 번 째 접 시 를 세 번 째 기둥 으로 이동한다.(두 번 째 기둥 을 빌려)
② 두 번 째 스님 은 제 가 첫 번 째 기둥 두 번 째 접 시 를 두 번 째 기둥 으로 옮 깁 니 다.
③ 세 번 째 스님 은 첫 번 째 접 시 를 세 번 째 기둥 에서 두 번 째 기둥 으로 이동한다.
마찬가지 로 두 번 째 단 계 는 쉽게 이 루어 지지 만 세 번 째 스님 은 접 시 를 한 개 만 옮 겨 야 하기 때문에 임 무 를 맡 길 필요 가 없다.
(주의: 이것 이 재 귀 를 중단 하 는 조건 이 고 경계 값 이 라 고도 합 니 다)
세 번 째 단 계 는 두 번 째 스님 에 게 접시 가 두 개 있 는 지, 명령 으로 나 눌 수 있다.
① 세 번 째 스님 은 두 번 째 기둥 위의 첫 번 째 접 시 를 첫 번 째 기둥 으로 이동한다.
② 두 번 째 스님 은 두 번 째 접 시 를 두 번 째 기둥 에서 세 번 째 기둥 으로 옮 깁 니 다.
③ 세 번 째 스님 은 첫 번 째 기둥 의 접 시 를 세 번 째 기둥 으로 옮 겨 라.
분석 을 조합 하면 1 → 3 1 → 2 3 → 2 세 번 째 기둥 을 빌려 두 번 째 기둥 으로 이동 하 는 것 이다.
1 → 3 이기 적 인 사람 이 자신 에 게 남 긴 일 | 2 → 1 2 → 3 1 → 3 첫 번 째 기둥 을 빌려 세 번 째 기둥 으로 이동 하 는 데 총 7 걸음 이 필요 하 다.

      4   ，           1   3   3   ，

        7 ， 14 ，    1    1 ，

     4          7+1+7=15 ，

     ，5     15+1+15=31 ，6     31+1+31=64 ……

         ，  n     （2 n  ）-1 。

위의 전체적인 종합 분석 을 통 해 알 수 있 듯 이 n 개의 접 시 를 1 개 (상당히 첫 번 째 기둥) 에서 3 개 (상당히 세 번 째 기둥) 로 옮 겼 다.
(1) 1 개의 접시 (n - 1) 를 3 개의 접 시 를 빌려 2 개의 접시 로 옮긴다.
(2) 1 개 위의 n 번 째 접 시 를 3 개 이동한다.
(3) 2 개의 접시 (n - 1) 를 1 개의 접시 에 빌려 3 개의 접 시 를 이동한다.

      hanoi（n,a,b,c）   1 n     2    3 。



        :   

     (1)    hanoi(n-1,1,3,2)

     (3)    hanoi(n-1,2,1,3)

      C      ，  ：

첫 번 째 접 시 를 A 자리 에서 C 자리 로 옮 겨 주세요.
두 번 째 접 시 를 A 자리 에서 B 자리 로 옮 겨 주세요.
첫 번 째 접 시 를 C 자리 에서 B 자리 로 옮 겨 주세요.
세 번 째 접 시 를 A 자리 에서 C 자리 로 옮 겨 주세요.
첫 번 째 접 시 를 B 자리 에서 A 자리 로 옮 겨 주세요.
두 번 째 접 시 를 B 자리 에서 C 자리 로 옮 겨 주세요.
첫 번 째 접 시 를 A 자리 에서 C 자리 로 옮 겨 주세요.

/************************************************************************/

#include 
#include 
using namespace std;

//  int n:   n   
int move(int n,char a, char b){
    printf("==>==>:       %d       %c     %c 

",n,a,b);
    return 0;
}

//  int n：      n   
int hanoi(int n,char a,char b,char c){
    cout<<"******************int hanoi(int n,char a,char b,char c) begin!!!"<if (n == 1){
       cout<<"      n="<"，   "<"좌석, 바로 옮 길 수 있 습 니 다." "좌석" < else {
cout < < "남 은 접시 수 n =" <, 접시 가 있 습 니 다 "<"좌석, 도움 이 필요 합 니 다" "좌석, 이사" "좌석" < if (n = 1) {
cout<"11111=>: ";
move (1,a,c);
}else{
hanoi (n - 1, a, c, b); / / 위 해설 에 따 르 면 n 개의 접 시 를 이동 하려 면 (2 의 n 차방) - 1 단계 가 필요 합 니 다. 여 기 는 n - 1 개의 접 시 를 이동 하려 면 (2 의 n 차방) - 2 단계 가 필요 합 니 다. 즉, 이곳 의 1 차 재 귀 는 n - 1 층 재 귀 순환 을 해 야 호출 을 끝 낼 수 있 습 니 다. n - 1 개의 접 시 를 a 자리 에서 c 자 리 를 빌려 최종 적 으로 b 자리 에 올 렸 습 니 다.
move (n, a, c); / / 마지막 접시 인 n 번 째 접 시 를 a 자리 에서 c 자리 에 올 려 놓 았 습 니 다. 이로써 1 차 호출 을 완 료 했 습 니 다. 그 결 과 는 마지막 접 시 를 임 무 를 완 료 했 고 나머지 접 시 는 b 자리 에 놓 여 있 습 니 다. 다음 단 계 는 남 은 n - 1 접시 에 대해 새로운 재 귀적 호출 을 하 는 것 입 니 다.
hanoi (n - 1, b, a, c); / / 새로운 재 귀적 호출 시작
};
if (n == 1) {
cout < < < 대응 --- --- 남 은 접시 수 n = > <, 접시 가 있 습 니 다 <"좌석, 바로 옮 길 수 있 습 니 다." "좌석" < else {
cout < < < 대응 --- --- 남 은 접시 수 n = > <, 접시 가 있 습 니 다 <"좌석, 도움 이 필요 합 니 다" < "좌석, 이사" < "좌석" < cout < < < int hanoi (int n, char a, char b, char c) end end end end end end end end end @ @ @! @ @ @ "< return 0;
}
int main(){
freopen("hanoi.in","r",stdin);
freopen("hanoiOutPut.txt","w",stdout);
int num;
scanf("%d",&num);
cout < < 시작 > < A ',' B ',' C ');
cout < "종료" < return 0;
}

시작 하 다
******************int hanoi(int n,char a,char b,char c) begin!!!
남 은 접시 수 n = 3, 접 시 는 A 자리 에 있 습 니 다. B 자 리 를 빌려 C 자리 로 옮 겨 야 합 니 다.
******************int hanoi(int n,char a,char b,char c) begin!!!
남 은 접시 수 n = 2, 접 시 는 A 자리 에 있 습 니 다. C 자 리 를 빌려 B 자리 로 옮 겨 야 합 니 다.
******************int hanoi(int n,char a,char b,char c) begin!!!
남 은 접시 수 n = 1, 접 시 는 A 자리 에 있 고 C 자리 로 바로 옮 길 수 있 습 니 다.
11111 = >: = = > = >: 첫 번 째 접 시 를 A 자리 에서 C 자리 로 옮 깁 니 다.
대응 - - - 남 은 접시 수 n = 1, 접 시 는 A 자리 에 있 고 C 자리 로 바로 옮 길 수 있 습 니 다.
int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@
두 번 째 접 시 를 A 자리 에서 B 자리 로 옮 깁 니 다.
******************int hanoi(int n,char a,char b,char c) begin!!!
남 은 접시 수 n = 1, 접 시 는 C 자리 에 있 고 B 자리 로 바로 옮 길 수 있 습 니 다.
11111 = >: = = > = >: 첫 번 째 접 시 를 C 자리 에서 B 자리 로 옮 깁 니 다.
대응 - - - 남 은 접시 수 n = 1, 접 시 는 C 자리 에 있 고 B 자리 로 바로 옮 길 수 있 습 니 다.
int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@
대응 - - - 남 은 접시 수 n = 2, 접 시 는 A 자리 에 있 습 니 다. C 자 리 를 빌려 B 자리 로 옮 겨 야 합 니 다.
int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@
세 번 째 접 시 를 A 자리 에서 C 자리 로 옮 깁 니 다.
******************int hanoi(int n,char a,char b,char c) begin!!!
남 은 접시 수 n = 2, 접 시 는 B 자리 에 있 습 니 다. A 자 리 를 빌려 C 자리 로 옮 겨 야 합 니 다.
******************int hanoi(int n,char a,char b,char c) begin!!!
남 은 접시 수 n = 1, 접 시 는 B 자리 에 있 고 A 자리 로 바로 옮 길 수 있 습 니 다.
11111 = >: = = > = >: 첫 번 째 접 시 를 B 자리 에서 A 자리 로 옮 깁 니 다.
대응 - - - 남 은 접시 수 n = 1, 접 시 는 B 자리 에 있 고 A 자리 로 바로 옮 길 수 있 습 니 다.
int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@
두 번 째 접 시 를 B 자리 에서 C 자리 로 옮 깁 니 다.
******************int hanoi(int n,char a,char b,char c) begin!!!
남 은 접시 수 n = 1, 접 시 는 A 자리 에 있 고 C 자리 로 바로 옮 길 수 있 습 니 다.
11111 = >: = = > = >: 첫 번 째 접 시 를 A 자리 에서 C 자리 로 옮 깁 니 다.
대응 - - - 남 은 접시 수 n = 1, 접 시 는 A 자리 에 있 고 C 자리 로 바로 옮 길 수 있 습 니 다.
int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@
대응 - - - 남 은 접시 수 n = 2, 접 시 는 B 자리 에 있 습 니 다. A 자 리 를 빌려 C 자리 로 옮 겨 야 합 니 다.
int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@
대응 - - - 남 은 접시 수 n = 3, 접 시 는 A 자리 에 있 습 니 다. B 자 리 를 빌려 C 자리 로 옮 겨 야 합 니 다.
int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@
끝나다