boj 1343 漢諾塔 遞歸問題 謝謝大牛的解答 我需要多聯系

位址：http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1343

Tower of Hanoi Submit: 115    Accepted:31 Time Limit: 1000MS  Memory Limit: 65535K

Description

The Tower of Hanoi is a puzzle consisting of three pegs(namead 1,2,3) and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg(1), the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another peg(3), obeying the following rules:

Only one disk may be moved at a time.

Each move consists of taking the upper disk from one of the pegs and sliding it onto another peg, on top of the other disks that may already be present on that peg.

No disk may be placed on top of a smaller disk.

For n disks, it is a well-known result that the optimal solution takes 2^n− 1 moves.

Sunny has a YuGong’s spirit, he want to do this day by day by day …... So , he make a tower of hanoi which has n (n<=31) disks , and just wrote down the number of steps he moved before , and this day , he wants to move the ith step to jth step(1<=i<=j<2^n&&j-i<=50) . Now , please tell him each of step he should do .

Input

The first line contains only one integer k , the number of cases.

Each of test case only one line contains three integers n, i , j .

Output

For each test case , first line print “Case d:” , means the dth case.

Next j-i+1 lines print “b->e”, (b,e=1,2,3) , which means move a disk from b peg to e peg .

Sample Input

2

2 1 3

3 1 4

Sample Output

Case 1:

1->2

1->3

2->3

Case 2:

1->3

1->2

3->2

1->3

#include <stdio.h>

// 将N個盤子由Src移動到第Dst根柱子，并輸出其中的第i->j步

void Move(int N, int Src, int Dst, int i, int j)

{

    int Step = (1 << (N - 1)) - 1; // 計算将N-1個盤子移到中間柱子的所需步數

    if (N > 1 && i <= Step)        // 如果這個過程中覆寫到了第i->j步，則遞歸進去，否則沒必要

    {

        Move(N - 1, Src, 6 - Src -Dst, i, j);

    }

    ++Step;

    if (i <= Step && Step <= j)     // 最底下一個盤子移動到目标

    {

        printf("%d->%d/n", Src, Dst);

    }

    // 将N-1個盤子由中間柱子移動到目标柱子

    if (N > 1 && j > Step)          // 如果這個過程中覆寫到了第i->j步，則遞歸進去，否則沒必要

    {

        Move(N - 1, 6 - Src - Dst, Dst, i - Step, j - Step);

    }

}

int main()

{

    int TotalCases;

    scanf("%d", &TotalCases);

    for (int Case = 1; Case <= TotalCases; ++Case)

    {

        int n, i, j;

        scanf("%d %d %d", &n, &i, &j);

        printf("Case %d:/n", Case);

        Move(n, 1, 3, i, j);

    }

    return 0;

}