다 주 한 노 타 문제 에 대한 분석 - 알고리즘 및 공식 유도

한 노 타 문제
한 노 타 (Tower of Hanoi) 는 수학 게임 이다. 세 개의 기둥 이 있 는데 그 중에서 한 개의 기둥 은 바닥 에서 위로 크기 가 점점 작은 여러 개의 원반 을 연결 하고 다음 과 같은 규칙 을 따른다. 1. 한 번 에 한 개의 원반 만 이동 할 수 있다.2. 큰 원반 은 작은 원반 위 에 놓 으 면 안 됩 니 다.최소한 몇 걸음 을 움 직 여야 모든 원반 을 다른 기둥 으로 옮 길 수 있 습 니까?
해답: N N N 개의 원반 을 이동 하 는 데 필요 한 최소 걸음 수 를 F (N) F (N) F (N) 로 설정 합 니 다.세 개의 기둥 을 각각 A, B, C 라 고 명명 하고 N N N 개의 원반 을 A 기둥 에서 C 기둥 으로 옮 기 려 면 다음 과 같은 절차 로 분해 해 야 한다. 1. N - 1 N - 1 N - 1 N - 1 개의 원반 을 A 기둥 에서 B 기둥 으로 옮 기 려 면 F (N - 1) F (N - 1) F (N - 1) 걸음 이 필요 하 다.2. 남 은 최대 원반 을 A 기둥 에서 C 기둥 으로 옮 기 려 면 한 걸음 이 필요 합 니 다.3. N - 1 N - 1 N - 1 원반 을 B 기둥 에서 C 기둥 으로 옮 기 려 면 F (N - 1) F (N - 1) F (N - 1) 걸음 이 필요 하 다.최소 이동 보 수 를 얻 는 추이 공식 F (N) = 2F (N − 1) + 1F (N) = 2F (N - 1) + 1F (N) = 2F (N − 1) + 1.이지 F (1) = 1 F (1) = 1 F (1) = 1, 통항 공식 F (N) = 2 N − 1 F (N) = 2 ^ N - 1 F (N) = 2 N − 1.
홍보: 네 개 이상 의 기둥 이 있다 면 필요 한 최소 이동 보 수 는 얼마 입 니까?
Frame - Stewart 알고리즘
이 알고리즘 은 점차 적 인 사상 을 채택 하여 다 주 한 노 타 문 제 를 풀 었 다.M M M 개의 기둥, N N N 개의 원반 을 설정 하 는 데 필요 한 최소 이동 보 수 는 F M (N) F 이다.M (N) FM (N), 이동 절 차 를 다음 과 같이 분해 합 니 다. 1. r r 개의 원반 을 다른 기둥 으로 옮 기 려 면 F M (r) F 가 필요 합 니 다.M (r) FM (r) 걸음;2. 남 은 N - r N - r 개의 원반 을 목표 기둥 으로 옮 기 려 면 F - M - 1 (N - r) F 가 필요 하 다.{M - 1} (N - r) FM - 1 (N - r) 걸음;3 、 r r 개의 원반 을 목표 기둥 으로 옮 기 려 면 F M (r) F 가 필요 합 니 다.M (r) FM (r) 걸음.전달 공식 F M (N) = min ⁡ 1 ≤ r < N {2 F M (r) + F M − 1 (N − r)} F 획득M(N)=\min\limits_{1 \ \ le r < N} \ \ {2F M (r) + F {M - 1} (N - r) \ \} FM (N) = 1 ≤ r < Nmin {2FM (r) + FM − 1 (N - r)} 코드:

#include 
#include 
#include 
using namespace std;

// the least number of movements for n disks, m pegs
map<pair<int, int>, double> mapLeastMoves;
double LeastMoves(const int n, const int m) {
    if (n < 0 || m < 3)
        return -1;
    if (n == 1)
        return 1;
    const auto index = make_pair(n, m);
    if (mapLeastMoves.count(index) > 0)
        return mapLeastMoves[index];
    double least_moves;
    if (m == 3) {
        least_moves = pow(2., n) - 1;
    } else {
        least_moves = 2 * LeastMoves(n - 1, m) + LeastMoves(1, m - 1);
        for (int r = n - 2; r > 0; --r) {
            double moves = 2 * LeastMoves(r, m) + LeastMoves(n - r, m - 1);
            if (moves < least_moves)
                least_moves = moves;
            else // a little optimization
                break;
        }
    }
    mapLeastMoves[index] = least_moves;
    return least_moves;
}

void main() {
    int M = 7, N = 10;
    cout << "M\\N";
    for (int n = 1; n <= N; ++n)
        cout << "\tN = " << n;
    cout << endl;
    for (int m = 3; m <= M; ++m) {
        cout << "M = " << m;
        for (int n = 1; n <= N; ++n)
            cout << "\t" << LeastMoves(n, m);
        cout << endl;
    }
    system("pause");
}

출력:

M\N     N = 1   N = 2   N = 3   N = 4   N = 5   N = 6   N = 7   N = 8   N = 9   N = 10
M = 3   1       3       7       15      31      63      127     255     511     1023
M = 4   1       3       5       9       13      17      25      33      41      49
M = 5   1       3       5       7       11      15      19      23      27      31
M = 6   1       3       5       7       9       13      17      21      25      29
M = 7   1       3       5       7       9       11      15      19      23      27

다 주 상황 하의 통항 공식
F M − 1 (N − r) F{M - 1} (N - r) FM - 1 (N - r) 계속 전개, F M (N) FM (N) FM (N) 의 유도 공식 은 다음 과 같이 F M (N) = min ⁡ r M, r M − 1,..., r 3 {2 [F M (r M) + F M − 1 (r M − 1) + + F 3 (r 3))] + 1}, s. t. {0 ≤ r m < N, \8704 m * * * * * [3, M] ∑ m = 3 M r m + 1 = 3 M r m m + 1 = N F M (N) = \ min \ \ \ \ \ lims {r M, {M - {M, {M - 1}, \ dot m [3, M] △ △ 3, M △ 3 M M + 1 = 3 M M M M + 1 = N M M M M M + 1 = N N F M (s, r 3} \ \ {2 [F M (r M) + F {M - 1} (r {M - 1}) + \ dots + F 3 (r 3)] + 1 \}\ \ \ \ \ \ \ \ \ \ \ \ quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ sum {m = 3} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ∑ m = 3M rm + 1 = N 용Δ \Delta ΔN N 에 일시 F M (N) F M (N) FM (N) 의 증 가 를 나타 내 고 설정 합 니 다.Δ F M ( N ) = F M ( N ) − F M ( N − 1 ) \Delta F_M(N)=F_M(N)-F_M(N-1) ΔFM (N) = FM (N) - FM (N - 1)Δ F M ( 1 ) = 1 Δ F M ( N + 1 ) = 2 min ⁡ m ∈ [ 3 , M ] { Δ F m ( r m + 1 ) } Δ F M ( N + 1 ) ≥ Δ F M ( N ) \begin{cases} \Delta F_M(1)=1\\ \Delta F_M(N+1)=2\min\limits_{m\in[3,M]}\{\Delta F_m(r_m+1)\}\\ \Delta F_M(N+1)\ge\Delta F_M(N) \end{cases} ⎩⎪⎪⎨⎪⎪⎧​ΔFM​(1)=1ΔFM​(N+1)=2m∈[3,M]min​{ΔFm​(rm​+1)}ΔFM​(N+1)≥ΔFM (N) 만약 r m + 1 = 1, 8707 ° m * 8712 ° [3, M] r m + 1 = 1, \ \ exists m \ \ in [3, M] rm + 1 = 1, 8707 ° m * 8712 ° [3, M] 이면Δ F M ( N + 1 ) = 2 Δ F m ( 1 ) = 2 \Delta F_M(N+1)=2\Delta F_m(1)=2 ΔFM​(N+1)=2ΔFm (1) = 2. 이때 ∑ m = 3M r m < ∑ m = 3M 1 = M − 2 & ThickSpace; ⟹ & ThickSpace; N < M − 1 \ \ \ sum {m = 3} ^ M {r m} < \ sum {m = 3} ^ M {1} = M - 2 \ \ implies N < M - 1 ∑ m = 3M rm < ∑ m = 3M 1 = M − 2 ⟹ N < M − 1, N + 1 N + 1 N + 1 N + 1 을 N N N 으로 교체 한 것 을 알 수 있다.Δ F M ( N ) = 2 ,  if  1 < N ≤ M − 1 \Delta F_M(N)=2, \text{ if }1 1, * 8704 ° m * 8712 ° [3, M] r m + 1 > 1, \ forall m \ in [3, M] rm + 1 > 1, * 8704 ° m * 8712 ° [3, M], 그리고 r m + 1 ≤ m - 1, * 8707 ° m * 8712 ° [3, M] r m + 1 \ le m - 1, \ \ exists m \ in [3, M] rm + 1 ≤ m − 1, * 8707 ° m * 8712 ° [3, M], 그러면Δ F M ( N + 1 ) = 2 Δ F m ( r m + 1 ) = 4 \Delta F_M(N+1)=2\Delta F_m(r_m+1)=4 ΔFM​(N+1)=2Δ(rm + 1) = 4. 이때 ∑ m = 3 M r m < ∑ m = 3 M (m − 1) = 1 2 M (M − 1) − 1 & ThickSpace; ⟹ & ThickSpace; N < 1 2 M (M − 1) \ \ sum {m = 3} ^ M {r m} < \ sum {m = 3} (\ \ sum {m = 3} ^ M (m - 1) = \ \ \ \ frac {1} {2} M (M - 1) - 1) - 1 \ \ \ 암 암 암 암 (N < \ \ \ \ \ frac {1}} M (M - 1) {2} M (M - 1) {2} M (M - 1) < < < < < < < < < < 램 m m m = 3MM = 3M(m m = 3M (m - 1) = 21M (M - 1) - 1 ⟹ N & lt; 21M (M - 1), N + 1 N + 1 N + 1 N + 1Δ F M ( N ) = 4 ,  if  M − 1 < N ≤ 1 2 M ( M − 1 ) \Delta F_M(N)=4, \text{ if }M-1 m − 1, ∀ m − 1, [3, M] r m + 1 > m - 1, \ \ \ forall m \ \ \ in [3, M] rm + 1 > m − 1, [3, M], r m + 1 ≤ 1 2 M (M − 1), \ \ forall m \ \ \ \ \ \ \ in [3, M] r m + 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ frac {1} M (M - 1), \ \ \ \ 존재m \ in [3, M − 1 2 M (M − 1), \ \ \ m (M − 1 2 M (M − 1), [3, M] r m + 1 ≤ 21 M (M − 1), 8707 ° m * 8712 ° [3, M], 칙Δ F M ( N + 1 ) = 2 Δ F m ( r m + 1 ) = 8 \Delta F_M(N+1)=2\Delta F_m(r_m+1)=8 ΔFM​(N+1)=2Δ(rm + 1) = 8. 이때 ∑ m = 3 M r m < ∑ m = 3 M 1 2m (m + 1) = 6 (M + 1) M (M + 1) M (M − 1) − 1 & ThickSpace; ⟹ & ThickSpace; N < 1 6 (M + 1) M (M − 1) \ \ \ sum {m = 3} ^ M {r m} < \ sum {m = 3} < \ sum {m = 3} ^ M \ \ \ \ \ \ \ frac {1} {2} m (m - 1) {2} m (m - 1) = \ \ \ \ \ frac {1} (M + 1) {6} (M + 1) {M + 1) M (M + 1) M (M + 1) M (M - 1) - 1) \ implies N < \ frac {1} {6} (M + 1) M (M - 1) ∑ m = 3M rm < ∑ m = 3M 21m (m - 1) = 61 (M + 1) M (M - 1)− 1 ⟹ N < 61 (M + 1) M (M - 1), N + 1 N + 1 N + 1 N + 1 을 N N N N 으로 교체, 알 수 있다.Δ F M ( N ) = 8 ,  if  1 2 M ( M − 1 ) < N ≤ 1 6 ( M + 1 ) M ( M − 1 ) \Delta F_M(N)=8, \text{ if }\frac{1}{2}M(M-1)