Towers of Hanoi

In 1883, Edouard Lucas invented, or perhaps reinvented, one of the most popular puzzles of all times - the Tower of Hanoi, as he called it - which is still used today in many computer science textbooks to demonstrate how to write a recursive algorithm or program. First of all, we will make a list of the rules of the puzzle:

• There are three pegs: A, B and C.
• There are n disks. The number n is constant while working the puzzle.
• All disks are different in size.
• The disks are initially stacked on peg A so that they increase in size from the top to the bottom.
• The goal of the puzzle is to transfer the entire tower from the A peg to one of the others pegs.
• One disk at a time can be moved from the top of a stack either to an empty peg or to a peg with a larger disk than itself on the top of its stack.

A good way to get a feeling for the puzzle is to write a program which will show a copy of the puzzle on the screen and let you simulate moving the disks around. The next step could be to write a program for solving the puzzle in a efficient way. You don't have to do neither, but only know the actual situation after a given number of moves by using a determinate algorithm.

The Algorithm

It is well known and rather easy to prove that the minimum number of moves needed to complete the puzzle with n disks is . A simple algorithm which allows us to reach this optimum is as follows: for odd moves, take the smallest disk (number 1) from the peg where it lies to the next one in the circular sequence ; for even moves, make the only possible move not involving disk 1.

Input

The input file will consist of a series of lines. Each line will contain two integers n, m: n, lying within the range [0,100], will denote the number of disks and m, belonging to [0, ], will be the number of the last move. The file will end at a line formed by two zeros.

Output

The output will consist again of a series of lines, one for each line of the input. Each of them will be formed by three integers indicating the number of disks in the pegs A, B and C respectively, when using the algorithm described above.

Sample Input

3 5
64 2
8 45
0 0

Sample Output

1 1 1
62 1 1
4 2 2

---

大數轉二進制去做。
你可以先看懂第一個非大數版本，再改成題目所需要的大數版本

#include <stdio.h>
int peg[3];
int n, m, flag;
void h(int n, int A, int B, int C) {
    if(flag)    return;
    if(m == 0) {
        printf("%d %d %d\n", peg[0], peg[2], peg[1]);
        flag = 1;
    }
    if(n > 0) {
        if(m > (1<<(n-1))-1) {
            m -= (1<<(n-1))-1;
            peg[A] -= n-1;
            peg[B] += n-1;
        } else
            h(n-1, A, C, B);
        m--;
        peg[A]--, peg[C]++;
        if(m > (1<<(n-1))-1) {
            m -= (1<<(n-1))-1;
            peg[B] -= n-1;
            peg[C] += n-1;
        } else
            h(n-1, B, A, C);
    }
}
int main() {
    while(scanf("%d %d", &n, &m) == 2) {
        if(n == 0)  break;
        flag = 0;
        peg[0] = n, peg[1] = peg[2] = 0;
        h(n, 0, 1, 2);
    }
    return 0;
}

---

#include <stdio.h>
#include <string.h>
int peg[3], on, flag;
char m[100], bin[100];
int highbit;
void int2bin(int n) {
    memset(bin, 0, sizeof(bin));
    int i, j, tmp;
    int ml = strlen(m);
    for(i = 0; m[i]; i++)
        m[i] -= '0';
    for(i = 0; i < n; i++) {
        tmp = 0;
        for(j = 0; j < ml; j++) {
            tmp = tmp*10 + m[j];
            m[j] = tmp/2;
            tmp %= 2;
        }
        bin[i] = tmp;
    }
    highbit = n-1;
    while(highbit >= 0 && bin[highbit] == 0)
        highbit--;
}
void calc() {
    static int i;
    for(i = 0; i < on; i++) {
        if(bin[i] >= 2) {
            bin[i+1] += bin[i]/2;
            bin[i] %= 2;
        }
        while(bin[i] < 0)
            bin[i] += 2, bin[i+1]--;
    }
    highbit = on-1;
    while(highbit >= 0 && bin[highbit] == 0)
        highbit--;
}
void h(int n, int A, int B, int C) {
    if(flag)    return;
    if(highbit == -1) {
        if(on&1)
            printf("%d %d %d\n", peg[0], peg[2], peg[1]);
        else
            printf("%d %d %d\n", peg[0], peg[1], peg[2]);
        flag = 1;
    }
    if(n > 0) {
        if(highbit >= n-1 && n) {
            bin[n-1] = 0, bin[0]++;
            calc();
            peg[A] -= n-1, peg[B] += n-1;
        } else
            h(n-1, A, C, B);
        bin[0]--;
        calc();
        peg[A]--, peg[C]++;
        if(highbit >= n-1 && n) {
            bin[n-1] = 0, bin[0]++;
            calc();
            peg[B] -= n-1, peg[C] += n-1;
        } else
            h(n-1, B, A, C);
    }
}
int main() {
    while(scanf("%d %s", &on, m) == 2) {
        if(on == 0 && m[0] == '0')  break;
        peg[0] = on, peg[1] = peg[2] = flag = 0;
        int2bin(on);
        h(on, 0, 1, 2);
    }
    return 0;
}