UVa 254 – Towers of Hanoi [汉诺塔+二进制]

Link

传送门

Problem

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.

Mean

众所周知,汉诺塔从一个柱子上的n个盘子移动到另外一个柱子上,至少需要(2^n)-1步,给定一个算法,能够在这个步数内完成。这个算法是:奇数步把1号盘子往右移动(循环),偶数步把1号盘不在的两个柱子中,小盘移动到大盘上。根据这个算法,给定盘子总个数n和步数m,问你m步后三个柱子上的盘子数。

n最大为100,m最大为(2^n)-1.

Analysis

假设有1,2,3三个柱子。首先可以发现,刚开始都在1号柱子,如果n是偶数,那么(2^n)-1步后会全部移动到3号;如果n是奇数,那么(2^n)-1步后会全部移动到2号。

然后我们可以对m分析他的二进制和移动情况。想要移动n个盘子到目标位置需要:

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

那么,根据二进制步数和走的情况就可以对m进行分析,从高位到地位看是0还是1,然后移动盘子递归处理即可。

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

Code

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))
                return;
            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();
    }
}

欢迎留言