다 주 한 노 타 문제 탐구

머리말
한 노 타 알고리즘 은 알고리즘 디자인 과목 의 가장 대표 적 인 연구 문제 로 본 고 는 다 주 한 노 타 최 적 화 된 알고리즘 을 어떻게 디자인 하 는 지 에 대한 연구 에 주목한다.가장 간단 한 한 노 타 는 세 개의 기둥 (A, B, C) 이기 때문에 다 주 한 노 타의 기둥 개 수 는 M ≥ 3 이다.다음은 삼 주 한 노 타 에서 우리 가 관심 을 가 져 야 할 문제 에 대해 천천히 들 어가 보 자.
1. 삼 주 한 노 타
삼 주 한 노 타 는 전형 적 인 한 노 타 문제 로 알고리즘 디자인 에서 재 귀 알고리즘 의 전형 적 인 문제 이다.그 알고리즘 은 다음 과 같다. 일단 A 를... 기둥 위의 n - 1 한 접시 가 C 를 통과 하 다 기둥 을 B 로 이동 기둥 위 [T (n - 1) 보], 그리고 A 를... 기둥 에 남 은 접시 하 나 를 C 로 옮기다 기둥 위 [1 단계], 마지막 으로 B 를... 기둥 위의 모든 접시 가 A 를 통과 한다. 기둥 을 C 로 이동 기둥 위 [T (n - 1) 보].알고리즘 을 쉽게 얻 을 수 있 는 재 귀 방정식 은 T (n) = 2 * T (n - 1) + 1 이 므 로 걸음 수 는 T (n) = 2 ^ n - 1 이 라 고 계산 하기 어렵 지 않다.삼 주 한 노 타의 알고리즘 정확성 에 대해 서 는 이견 이 없다. 우 리 는 삼 주 한 노 타의 디자인 에서 다 주 한 노 타의 디자인 방법 을 제시 하 는 것 이 필요 하 다.
2. 사주 한 노 타
사주 한 노 타 는 기둥 이 하나 더 생 긴 것 만큼 간단 한 것 이 아니 므 로 우 리 는 먼저 정상 적 인 사고 에서 출발 하여 이동 보 수 를 어떻게 최소 화 하 는 지 탐구 해 보 자.
우선 세 기둥 한 노 타 는 다른 기둥 을 빌려 n - 1 개의 접 시 를 보관 하고 n 개의 접 시 를 목적 위치 로 옮 겨 야 한다 고 생각 할 것 이다.자 연 스 럽 게 사주 한 노 타 는 기둥 이 하나 더 생 겼 기 때문에 이동 하기에 더욱 편리 하 다. 우 리 는 접시 n - 2 를 하나 더 남 겨 서 다른 기둥 에 자 리 를 빌려 목적 위치 로 직접 이동 하지 못 하 게 할 수 있다.이렇게 하면 우 리 는 알고리즘 의 기본 절 차 를 얻 을 수 있다.
（1）       A 에서 C, D 의 도움 을 받 아 n - 2 개의 접시 가 B 위로 이동한다.
（2）       n - 2 를 C 로 이동 합 니 다.
（3）       n - 1 을 D 위로 이동 합 니 다.
（4）       n - 2 를 D 위로 이동 합 니 다.
（5）       B 에서 A, C 장 을 빌리다 n - 2 개의 접시 가 D 위로 이동한다.
또 이렇게 디자인 하 는 것 은 정상 적 인 사고 원칙 에 부합된다.기둥 의 개수 가 증가 함 에 따라 우 리 는 이동 할 때마다 접시 가 가능 한 한 접 히 지 않 기 를 바란다. 즉, n - 2 개의 접 시 를 보관 하 는 기둥 을 빌려 야 하 는 것 을 제외 하고.그러면 남 은 두 개의 기둥 은 두 개의 접 시 를 접 지 않 고 바로 목적 위치 로 이동 할 수 있 도록 허용 해 야 이동 이 편리 하고 절차 도 적 을 것 이다.사실 이 정말 그렇습니까?우 리 는 구체 적 으로 산법 을 분석 해 보 자.
상기 디자인 된 알고리즘 절차 에 따라 우 리 는 재 귀 방정식 을 얻 었 다. F (n) = 2 * F (n - 2) + 3.따라서 이동 보 수 는 F (n) = 4 * 2 ^ (n / 2) - 3: n 이 홀수 입 니 다.F (n) = 6 * 2 ^ (n / 2 - 1) - 3: n 은 짝수 이다.아래 에 6 개의 접시 의 이동 걸음 수 를 보 여 줍 니 다:
n      1     2     3     4     5     6
F(n)  1     3     5     9     13    21
       여기까지 우 리 는 우리 가 디자인 한 알고리즘 이 전형 적 인 한 노 타 알고리즘 과 거의 똑 같 고 심지어 이렇게 대칭 적 으로 조 화 를 이 루 었 다 는 것 을 알 게 되 었 다.이 를 바탕 으로 우 리 는 M (M ≥ 3) 개의 기둥 의 상황 까지 확대 하여 우리 가 원 하 는 최 적 화 를 얻 을 수 있다. 기둥 번호 가 1, 2, 3 이 라 고 가정 하면 M 알고리즘 주제 구조 절 차 는 다음 과 같 아야 한다.
（1）       1 기둥 에서 3... M 기둥 을 빌려 n - (M - 2) 개의 접 시 를 2 기둥 으로 이동한다.
（2）       M - 2 개 를 3... M - 1 기둥 을 통 해 M 기둥 으로 간단하게 이동 합 니 다 [2 * (M - 2) - 1 단계].
（3）       2 기둥 에서 1, 3... M - 1 기둥 을 빌려 n - (M - 2) 개의 접 시 를 M 기둥 으로 이동한다.
구체 적 인 절 차 는 네 기둥 과 유사 하여 더 이상 구체 적 인 분석 을 하지 않 는 다.이렇게 해서 우 리 는 우리 가 직접 구축 한 알고리즘 모델 이 이렇게 완벽 한 것 을 보고 우 리 는 심지어 차 마 그것 을 파괴 할 수 없다.그러나 나 는 유감스럽게도 이런 알고리즘 이 정확 하지만 가장 좋 은 것 은 아니 라 고 자신 에 게 말 했다!!예 를 들 어 6 개의 접시, 4 개의 기둥 이 있 는 한 노 타 에 대해 우리 생각 대로 2 개의 접 시 를 남 겨 두 고 이동 하 는 것 이다.지금 만약 에 우리 가 3 개의 접 시 를 보류한다 면 위의 3 개의 접 시 는 4 개의 한 노 타 규칙 에 따라 B 로 이동 하고 걸음 수 는 5 (이미 계산 되 었 으 며 검증 가능) 이 어야 한다. 나머지 3 개의 접 시 는 3 개의 한 노 타 규칙 에 따라 D 로 이동 하고 걸음 수 는 2 ^ 3 - 1 = 7 걸음 이 어야 한다. 그리고 B 위의 3 개의 접시 가 D 로 이동 하 는 것 은 5 걸음 이 고 총 걸음 수 는 5 + 7 + 5 = 17 걸음 ＜ 21 걸음 이다!이제 우 리 는 우리 의 생각 이 너무 순진 하 다 고 확신 할 수 있다.접시 가 최대한 겹 치지 않도록 걸음 수 를 최소 화 하 겠 다 고 생각 했 지만 절대 장담 할 수 는 없 었 다.아마도 접시 가 비교적 적은 상황 에서 가능 할 것 이다. 그러나 접시 가 증가 할 때, 그 남 은 것 은 단지 한 접시 의 기둥 만 이용 할 수 있다.이렇게 하면 매번 이동 걸음 수 를 늘 렸 지만 다른 측면 에서 재 귀 수량 을 줄 였 기 때문에 우 리 는 이 안에서 균형 점 을 찾 아야 한다.
위의 예 에서 우 리 는 재 귀 프로그램 에서 남 은 접시 의 개 수 는 반드시 M - 2 가 아니 라 M - 1 일 수도 있다 는 시사 점 을 얻 었 다. 우 리 는 남 은 접시 가 M - r 라 고 가정 하면 r 는 도대체 얼마나 받 아야 적당 할 까?사실은 1941 년 에 J. S. Frame 이라는 사람 이 에서 사주 한 노 타 문 제 를 해결 하 는 알고리즘 을 제 시 했 는데 이것 은 사람들 이 잘 아 는 Frame 알고리즘 이다.
(1) 4 주 한 노 타 알고리즘 으로 A 기둥 윗부분 의 n - r 개의 접 시 를 C 기둥 과 D 기둥 을 통 해 B 기둥 위로 옮 깁 니 다 [F (n - r) 걸음].
(2) 3 주 한 노 타 클래식 알고리즘 으로 A 기둥 에 남 은 r 개의 접 시 를 C 기둥 을 통 해 D 기둥 으로 옮 깁 니 다 [2 ^ r - 1 단계].
(3) 4 주 한 노 타 알고리즘 으로 B 기둥 에 있 는 n - r 개의 접 시 를 A 기둥 과 C 기둥 을 통 해 D 기둥 위로 옮 깁 니 다 [F (n - r) 보].
(4) 위의 규칙 에 따라 모든 r (1 ≤ r ≤ n) 상황 에서 걸음 수 f (n) 를 구하 고 최소 로 최종 적 으로 풀 어야 한다.
따라서 Frame 알고리즘 의 귀속 방정식 은 다음 과 같다.
F(n)=min(2*F(n-r)+2^r-1)，（1≤r≤n）。
이 방정식 을 통 해 우 리 는 모든 4 주 한 노 타의 절차 개 수 를 얻 을 수 있 고 [1] 도 증명 할 수 있다. 4 주 한 노 타 에 대해 r = (sqrt (8 * n + 1) - 1) / 2 시 f (n) 가 최소 치 F (n) = (n - (r ^ 2 - r + 2) / 2) * 2 ^ r + 1 을 얻 을 수 있다.그래서 알고리즘 의 복잡 도 는 F (n) = O (sqrt (2 * n) * 2 ^ sqrt (2 * n) 이다.이 방정식 에서 도 알 수 있 듯 이 n < 6 시 에 우 리 는 우리 가 처음에 구상 한 구조 와 같다 는 것 을 검증 할 수 있 지만 n 이 다시 증가 할 때 원래 생각 했 던 것 처럼 그렇지 않다.
3. 다 주 한 노 타
사주 한 노 타의 Frame 알고리즘 을 바탕 으로 우 리 는 다 주 (M 주) 한 노 타 워 의 상황 을 설명 할 수 있 습 니 다. 우 리 는 M 주 한 노 타 알고리즘 이 라 고 부 릅 니 다.
(1) M 기둥 한 노 타 알고리즘 으로 1 기둥 위의 n - r 개의 접 시 를 3... M 기둥 을 통 해 2 기둥 위로 옮 깁 니 다 [M (n - r) 보].
(2) M - 1 기둥 한 노 타 알고리즘 으로 1 기둥 에 남 은 r 개의 접 시 를 3... M - 1 기둥 을 통 해 M 기둥 으로 옮 깁 니 다 [< M - 1 > (r) 보].
(3) M 기둥 한 노 타 알고리즘 으로 2 기둥 에 있 는 n - r 개의 접 시 를 1 기둥 과 3... M 기둥 을 통 해 M 기둥 위로 옮 깁 니 다 [M (n - r) 걸음].
(4) 위의 규칙 에 따라 모든 r (1 ≤ r ≤ n) 상황 에서 걸음 수 m (n) 을 구하 고 최소 로 최종 적 으로 M (n) 을 풀 수 있다.
4 주 한 노 타의 재 귀 방정식 과 결과 공시 에서 알 수 있 듯 이 기둥 의 수량 이 증가 함 에 따라 알고리즘 의 복잡 정도 도 계속 증가 하고 있다.M 주 한 노 타 문 제 를 해결 하려 면 M - 1 주 한 노 타 워 의 알고리즘 을 사용 해 야 하기 때문에 알고리즘 이 문 제 를 해결 하려 면 재 귀 해 야 하 는 것 을 제외 하고 알고리즘 의 절차 자체 도 재 귀 해 야 한다. 이런 재 귀 구 조 는 현재 접촉 하고 있 는 재 귀 알고리즘 보다 훨씬 복잡 하 다.관심 이 있 으 면 이런 알고리즘 을 디자인 해 볼 수 있 습 니 다. 알고리즘 과 관련 된 매개 변 수 는 접시 의 개수 n, 기둥 의 개수 m, 알고리즘 의 번호 num, 파라미터 r 등 정보 가 있어 야 합 니 다.서로 다른 기둥 의 상황 에 따라 순환 과 재 귀 를 통 해 가장 적합 한 r 값 을 찾 아야 하기 때문에 이런 알고리즘 은 복잡 도가 상당히 높 을 것 이다.그러나 우 리 는 단지 가장 좋 은 알고리즘 을 얻 는 방법 을 탐구 하기 위해 서 일 뿐 이 므 로 구체 적 으로 실현 하 는 것 은 더 이상 군말 하지 않 는 다.
총결산
이상 의 토론 을 통 해 우 리 는 일반적인 사고 인 접 시 를 접 지 않 고 다 주 한 노 타의 최 적 화 를 찾 아 보 았 으 나 결 과 는 성공 하지 못 했다. 접 시 는 오랫동안 기둥 이 충분히 이용 되 지 않 았 을 수도 있다.그 후에 앞 사람 이 제기 한 Frame 알고리즘 을 통 해 다 주 한 노 타 알고리즘 을 파생 시 켰 고 다 주 한 노 타 알고리즘 의 이중 포 함 된 재 귀 구조 인 알고리즘 문제 의 재 귀 와 알고리즘 자체 의 재 귀 실현 을 대체적으로 묘사 했다.이런 보기 드 문 재 귀 프로그램 구 조 는 우리 에 게 알고리즘 디자인 에 있어 새로운 시 야 를 넓 혀 주 었 고 머지않아 더 좋 은 알고리즘 디자인 방법 을 찾 아 다 주 한 노 타 문 제 를 해결 할 수 있 기 를 바란다.
문제 풀이:

#include <cstdio>
#include <cmath>
int work(int n)
{
    if(n==1) return 1;
    int ans=0;
    int r=(int)( sqrt(8*n+1)-1)/2;
    ans+= pow(2.0,(double)r)-1;
    ans+= 2*work(n-r);
    return ans;
}
int main()
{
    int n;
    while (scanf("%d",&n)==1)
        printf("%d
",work(n));
    return 0;
}

설명:
1941 년 에 J. S. Frame 이라는 사람 이 에서 사주 한 노 타 문 제 를 해결 하 는 알고리즘 을 제 시 했 는데 이것 은 사람들 이 잘 아 는 Frame 알고리즘 이다.
(1) 4 주 한 노 타 알고리즘 으로 A 기둥 윗부분 의 n - r 개의 접 시 를 C 기둥 과 D 기둥 을 통 해 B 기둥 위로 옮 깁 니 다 [F (n - r) 걸음].
(2) 3 주 한 노 타 클래식 알고리즘 으로 A 기둥 에 남 은 r 개의 접 시 를 C 기둥 을 통 해 D 기둥 으로 옮 깁 니 다 [2 ^ r - 1 단계].
(3) 4 주 한 노 타 알고리즘 으로 B 기둥 에 있 는 n - r 개의 접 시 를 A 기둥 과 C 기둥 을 통 해 D 기둥 위로 옮 깁 니 다 [F (n - r) 보].
(4) 위의 규칙 에 따라 모든 r (1 ≤ r ≤ n) 상황 에서 걸음 수 f (n) 를 구하 고 최소 로 최종 적 으로 풀 어야 한다.
따라서 Frame 알고리즘 의 귀속 방정식 은 다음 과 같다.
F(n)=min(2*F(n-r)+2^r-1)，（1≤r≤n）。
이 방정식 을 통 해 우 리 는 모든 4 주 한 노 타의 절차 개 수 를 얻 을 수 있 고 [1] 도 증명 할 수 있다. 4 주 한 노 타 에 대해 r = (sqrt (8 * n + 1) - 1) / 2 시 f (n) 가 최소 치 F (n) = (n - (r ^ 2 - r + 2) / 2) * 2 ^ r + 1 을 얻 을 수 있다.그래서 알고리즘 의 복잡 도 는 F (n) = O (sqrt (2 * n) * 2 ^ sqrt (2 * n))
1. 양 해 서 천 북경대학 컴퓨터 과학 과 기술 과, 북경 북경대학 학보 자연과 학 판) 제4 0 회 말 아, 제 1 기간 년 1 월.
2. 북경대학 학보 (자연과 학 판), 제4 2 권, 제1기, 2006 년 1 월