한 노 타 문제

한 노 타 문제 (하노이)
한 노 타 문 제 는 재 귀 문제 의 본보기 가 되 어 왔 다.이 동시에 이 문 제 는 시간의 발전 에 따라 새로운 것 을 만들어 내 고 인류의 아 이 큐 를 시험 하고 있다.여기 서 약간의 총 결 을 하 였 으 나 필 자 는 재능 이 부족 하여 학문 이 얕다.부족 하면 지적 해 주 십시오.
가장 기본 적 인 문제
제목 설명:
한 노 타 는 번호 가 1 부터 n 까지 크기 가 다른 원반 과 세 개의 기둥 a, b, c 로 구성 되 어 있다.처음에 이 n 개의 원반 은 큰 것 에서 작은 것 까지 차례대로 a 기둥 에 끼 워 넣 었 는데 그림 과 같다.a 기둥 위의 n 개의 원반 을 다음 규칙 에 따라 c 기둥 으로 옮 겨 야 합 니 다.

한 번 에 하나의 원반 만 옮 길 수 있 습 니 다. 그것 은 반드시 어떤 기둥 의 꼭대기 에 있어 야 합 니 다.

원반 은 세 개의 기둥 에 만 보관 할 수 있다.

큰 접시 가 작은 판 을 누 르 는 것 을 언제든지 허락 하지 않 는 다.

이 n 개의 접 시 를 a 기둥 에서 c 기둥 으로 이동 하려 면 적어도 몇 번 이동 해 야 합 니까?
Solution：
직접 재 귀 하면 됩 니 다. 만약 에 처음에 a 번 기둥 에 N 개의 접시 가 있 고 위 에서 아래로 반경 이 차례대로 커진다 고 가정 하면 우 리 는 위의 n - 1 개의 접 시 를 하나의 전체 로 볼 수 있 습 니 다. 그리고 우리 가 지금 해 야 할 일 은 n - 1 개의 접 시 를 a 에서 b 로 이동 한 다음 에 가장 큰 접 시 를 a 에서 c 로 이동 한 다음 에 그 n - 1 개의 접 시 를 b 에서 c 로 이동 하 는 것 입 니 다.
사실 생각 이 깊 어 지면 서 한 노 타 문제 에서 우리 가 실현 하고 자 하 는 것 은 n 개의 접 시 를 한 기둥 에서 다른 기둥 으로 옮 기 는 것 이다. 우 리 는 다른 기둥 을 통 해 실현 을 도와 야 할 뿐이다.
그래서 지금 우리 의 원래 문 제 는 비교적 간단 한 서브 문제 로 바 뀔 수 있다. 즉, 남 은 n - 1 개의 접 시 를 하나의 기둥 에서 다른 기둥 으로 옮 기 면 된다.
이제 우 리 는 접시 가 하나 밖 에 남지 않 을 때 까지 한 없 이 돌아 갈 수 있다. 그러면 답 은 분명히 1 이다.이렇게 하면 우 리 는 조금 만 더 거 슬러 올 라 가면 답 을 얻 을 수 있다.
Code:

#include
void hanoi(int n,char a,char b,char c)
{
    if(n==1)
    {
        printf("%d:%c->%c
",1,a,c);
    }
    else
    {
        hanoi(n-1,a,c,b);//  b        ，  a   (n-1)    c   
        printf("%d:%c->%c
",n,a,c);
        hanoi(n-1,b,a,c);//  c        ，  b   (n-1)    a   
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    hanoi(n,'A','B','C');
    return 0;
}

단순 변형

원래 의 문제 에서 우 리 는 n 개의 접시 로 세 개의 기둥 으로 이동 했다. 위의 코드 는 재 귀적 인 사상 으로 경 로 를 수출 했다.

우리 가 방안 수 를 알 고 싶 을 때 시 계 를 쳐 서 보 는 것 도 좋 습 니 다.
n
프로젝트 수
3
7
4
15
5
31
6
63
…
…
이 럴 때 n 개의 접 시 를 내 놓 을 수 있 는 공식 을 알 수 있 을 것 같다. f (n) = 2 * 8727 ° f (n - 1) + 1 n 의 범 위 는 n ≥ 3 이다. 이것 은 n 개의 접 시 를 한 기둥 에서 다른 기둥 으로 이동 하 는 방안 수 를 표시 하기 때문이다. 그러면 n - 1 개의 접 시 를 a - > b: f (n - 1) 로 먼저 이해 할 수 있다.가장 큰 것 을 a - > c: + 1;n - 1 접 시 를 a - > c: f (n - 1);so the ans is it.

지금 우 리 는 다른 각도 에서 생각해 보 자. 만약 에 우리 가 세 개의 접시, n 개의 기둥 이 있다 고 가정 하면 결 과 는 어떤 변화 가 있 을 까?

Thinking……………………………………………………………………………………………………..
사실 답 은 변 하지 않 았 습 니까? 아니면 f (n) = 2 * 8727 ° f (n - 1) + 1 이것 도 이해 하기 쉽 습 니까?아니 지?P. S. 를 내 려 다 보면 f (n) = 2 ^ n - 1;
사주 한 노 타 문제
먼저 설명 하고 자 하 는 것 은 사주 한 노 타 에 기둥 이 하나 더 생 긴 것 만 간단 한 것 이 아니 라 지금 우 리 는 정상 적 인 사고방식 으로 이 과정 을 어떻게 실현 해 야 할 지 생각해 보 자.
위의 분석 을 통 해 우 리 는 한 기둥 주위 에 두 개의 빈 기둥 [또는 반경 이 큰 접시] 만 있 으 면 그 두 기둥 의 협 조 를 통 해 이동 할 수 있다 는 것 을 확신 할 수 있다.그래서 사주 문제 에 대해 우 리 는 이렇게 해도 무방 하 다.

A 에서 C, D 를 빌려 n - 2 개의 접 시 를 B 위로 이동

n - 1 번 째 접 시 를 C

로 이동

가장 큰 접 시 를 D

로 이동

n - 1 번 째 접 시 를 C 에서 D

로 이동

B 에서 A, C 를 빌려 n - 2 개의 접 시 를 D 위로 이동

그래서 우 리 는 F (n) 를 이동 하 는 방안 수로 설정 하면 'F (n) = 2 * F (n - 2) + 3' 를 얻 을 수 있 습 니 다.
그리고 분류 토론 을 해서 일반적인 공식 을 얻 도록 하 겠 습 니 다.

F(n)=4*2^(n/2)-3; n%2!=0

F(n)=6*2^(n/2-1)-3; n%2==0

문 제 는 여기까지 해결 에 성공 했다 고 말 할 수 있다.
하지만 우 리 는 M 개의 기둥 까지 확장 할 수 있 습 니까?
유사 한 원리 로 같은 조작 을 하 다.우리 가 확신 할 수 있 는 것 은 이 사고방식 이 반드시 정확 하 다 는 것 이다. 그러나 그것 이 가장 좋 은 것 이 아 닐 까?
그렇지 않 으 면 네 기둥 문제 에 대해 우리 의 생각 은 두 접 시 를 보존 하고 이동 하 는 것 이다. 그러면 다섯 개, 여섯 개의 기둥 이 있다 면??
접시 가 늘 어 났 을 때, 남 은 것 은 단지 한 접시 의 기둥 만 이용 할 수 있다.이렇게 하면 한 걸음 한 걸음 이동 하 는 횟수 가 늘 어 났 지만 다른 한편 으로 는 재 귀적 인 수 를 줄 였 다.그래서 이 문 제 는 복잡 해 지기 시작 했다.
문 제 는 재 귀 가 필요 하기 때문에 알고리즘 의 절차 자체 도 재 귀 가 필요 하 다.
1914 년 에 J. S. Frame 이라는 사람 이 이 문 제 를 해결 하 는 방법 을 제 시 했 는데 이름 은 Frame 알고리즘 이다.
여기 서 재 귀 방정식 만 나열 합 니 다.
F(n)=min{2*F(n-r)+2^r-1} (1<=r<=n)
그리고 그 시간 복잡 도 는 O (sqrt (2 * n) * 2 ^ sqrt (2 * n)) 입 니 다.
질문
게임 의 게임 방법 을 바 꾸 면 가장 왼쪽 (오른쪽) 에서 가장 오른쪽 (왼쪽) 으로 직접 이동 하 는 것 을 허락 하지 않 습 니 다. (매번 이동 할 때마다 중간 봉 으로 이동 하거나 중간 에서 이동 합 니 다) 큰 판 을 다음 판 위 에 올 리 는 것 도 허락 하지 않 습 니 다.현재 N 개의 원반 이 있 는데, 적어도 몇 번 은 이동 해 야 이 원반 들 을 가장 왼쪽 에서 가장 오른쪽으로 옮 길 수 있 습 니까?
이상 의 경험 을 가지 고 이 문 제 를 푸 는 것 은 비교적 쉽다.우 리 는 위의 (N - x) 접 시 를 하나의 전체 로 볼 수 있다 는 것 을 이미 알 고 있 으 며, 최소한 의 이동 방안 을 찾 아서 표현 식 을 열거 하면 된다.
이 문제 의 유일한 차이 점 은 바로 양쪽 에서 이동 할 수 없다 는 것 이다. 그러나 곰 곰 이 생각해 보면 이것 은 우리 가 가장 큰 접 시 를 가장 왼쪽 에서 가장 오른쪽으로 이동 할 수 없 도록 제한 할 뿐이다.전체적으로 제한 이 없다. 즉, 우 리 는 한 걸음 한 걸음 전 체 를 옮 길 수 있다 는 것 이다.(생각해 보 니 왜?)
방안 은 다음 과 같다.

n - 1 개의 접 시 를 A 에서 C

로 이동

가장 큰 접 시 를 A 에서 B

로 이동한다.

n - 1 개의 접 시 를 C 에서 A

로 이동

가장 큰 접 시 를 B 에서 C

로 이동한다.

n - 1 개의 접 시 를 A 에서 C

로 이동
마찬가지 로 f (n) 는 n 개의 접 시 를 A 에서 C 로 이동 하 는 최소 걸음 수 를 나타 내 는데 1, 3, 5 는 f (n - 1) 이 고 2, 4 는 모두 1 임 을 알 수 있다.
따라서 f (n) = 3 * f (n - 1) + 2;
But, 우리 도 작은 방법 을 쓸 수 있어...킁 킁.
가장 큰 접 시 를 A 에서 C 로 옮 겨 야 하기 때문에 + 2 는 일정한 것 입 니 다. 그러나 우리 가 f (n - 1) 앞의 계 수 를 확정 하지 않 으 면 x 를 설정 한 다음 에 샘플 을 대 입 할 수 있 습 니 다. x 를 풀 면 공식 을 쉽게 내 놓 을 수 있 습 니 다. (나 는 x 를 먼저 구하 고 검증 하 는 것 이 라 고 말 하지 않 을 것 입 니 다 ^ O ^)
P. S. 물론 이런 전달 식 은 수학 공식 으로 표현 할 수 있 으 며 관심 이 있 으 면 스스로 유도 할 수 있다.
매 포인트 이동 횟수 문의
1, 2, n 으로 n 개의 접 시 를 표시 하고 1 번 접시, 2 번 접시 라 고 합 니 다.번호 가 크 면 접시 가 크다.이동 과정 에서 어떤 원반 은 이동 횟수 가 많 고 어떤 것 은 적 다 는 것 을 발견 했다.접시 의 총수 와 번 호 를 알려 이 접시 의 이동 횟수 를 계산 하 세 요.
이 문 제 는 이전 과 차이 가 많 지 않 습 니 다. 다만 i 번 째 접시 에 대해 서 는 아래 의 접 시 를 고려 할 필요 가 없습니다.
그래서 f (n) = 2 * f (n - 1) 를 얻 을 수 있 습 니 다.
그 중 f (1) = 1;
그리고 정 답 은 f (n - m + 1) 입 니 다.
[못 알 아 보고 물 어보 지도 마. 내 가 무슨 말 을 하 는 지 모 르 겠 어...]