首页 > 专题系列 > Java解POJ > POJ 3601 Tower of Hanoi [解题报告] Java
2013
11-12

POJ 3601 Tower of Hanoi [解题报告] Java

Tower of Hanoi

问题描述 :

The Tower of Hanoi is a puzzle consisting of three pegs 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, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another peg, 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 2n − 1 moves.

To complicate the puzzle a little, we allow multiple disks to be of the same size. Moreover, equisized disks are mutually distinguishable. Their ordering at the beginning should be preserved at the end, though it may be disturbed during the process of solving the puzzle.

Given the number of disks of each size, compute the number of moves that the optimal solution takes.

输入:

The input contains multiple test cases. Each test case consists of two lines. The first line contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 106). The second lines contains n integers a1, a2, …, an (1 ≤ a1, a2, …, an ≤ 105). For each 1 ≤ in, there are ai disks of size i. The input ends where EOF is met.

输出:

For each test case, print the answer modulo m on a separate line.

样例输入:

1 1000
2
5 1000
1 1 1 1 1
5 1000
2 2 2 2 2
5 1000
1 2 1 2 1

样例输出:

3
31
123
41

解题代码:

//* @author popop0p0popo
import java.util.*;
import java.io.*;

public class Main{
	public static int step;
	public static int[] h;
	public static void main(String[] args){
	 Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int n,m;
		while (scanner.hasNext()){
			n=scanner.nextInt();
			m=scanner.nextInt();
			step=0;
			h=new int[n];
			for (int i=0;i< n ;i++ ){
				h[i]=scanner.nextInt();
			}
			step=getStep(h.length-1,m);
			System.out.println(step%m);
		}
	}

	public static int getStep(int moved,int m){
		if (moved==0){
			return 2*h[moved]-1;
		}
		int total=h[0];
		for (int i=1;i< moved ;i++ ){
			total=(total*2+h[i])%m;
		}
		if (h[moved]==1){
			return total*2+1;
		}
		else{
			return 2*total+2*h[moved]+getStep(moved-1,m);
		}
	}
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }