UVa 254 – 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.

It is well known and rather easy to prove that the minimum number of moves needed to complete the puzzle with n disks is tex2html_wrap_inline44 . 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 tex2html_wrap_inline46 ; for even moves, make the only possible move not involving disk 1.







  1. 把上面n-1个盘子移动到临时柱子,2^(n-1)
  2. 把最下面的第n个盘子移动到目标位置,2^(n-1)+1步即1<<n步
  3. 把n-1个盘子从临时柱子移动到目标柱子。2^n步


因为m超出了long long,所以可以用java的BigInteger,然后用BigInteger.testBit(i)判断第i二进制位情况。


import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    int[] cnt = new int[4];
    BigInteger m;

    void solve(int i, int from, int to) {
        if(i < 0) return;
        int tmp = 6 - from - to;
        if(m.testBit(i)) {
            cnt[from] -= i; cnt[tmp] += i;
            --cnt[from]; ++cnt[to];
            solve(i-1, tmp, to);
        } else {
            solve(i-1, from, tmp);

    void run() {
        Scanner cin = new Scanner(System.in);
        while(true) {
            int n = cin.nextInt();
            m = cin.nextBigInteger();
            if(n == 0 && m.equals(BigInteger.ZERO))
            cnt[1] = n; cnt[2] = cnt[3] = 0;
            if(n % 2 == 0) solve(n-1, 1, 3);
            else solve(n-1, 1, 2);
            System.out.println(cnt[1] + " " + cnt[2] + " " + cnt[3]);

    public static void main(String[] args) {
        new Main().run();