汉诺塔问题 | 半卷书

汉诺塔问题

百科故事：

题外话之印度教：印度教是随着印度封建社会形成,种姓制度发生新变化而出现的.
印度教不是某位教主创立的思想体系,而是在长期社会发展过程中形成的,它是广泛吸收婆罗门教、佛教和耆那教教义
以及民间信仰、风俗习惯、哲学思想等的综合产物.也代指印度文化圈内所产生的宗教,是世界主要宗教之一,是印度的国教.

题外话之大梵天：梵天,是指印度教的创造之神.梵天亦称造书天,婆罗贺摩天,净天,华人地区俗称四面佛.
与毗湿奴,湿婆并称三主神.坐骑孔雀(或天鹅).

汉诺塔问题源于一个印度传说:大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.
大梵天命令婆罗门把罗盘从下面开始按照大小顺序重新摆放在另一根柱子上.
并规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘.

递归解决汉诺塔问题

大梵天和它的信徒说,你们把64片黄金圆盘都移过去有惊喜.

我想说这是个狠人…

f(n)=2^n-1,n=64时
假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下：
18446744073709551615秒
这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年…sruprise

这和向国王要米粒的家伙一样机智…

public class Hanoi {

    public static void main(String[] args) {
        int n=6;
        hanoi(n, 'a', 'b', 'c');
    }
    /**
     * 无论几个黄金圆盘，都看作是上边的和最后一个
     * @param n 个数黄金圆盘
     * @param from 源金刚石柱
     * @param mid 中间金刚石柱
     * @param target 目标金刚石柱
     */
    public static void hanoi(int n ,char from ,char mid,char target) {
        if(n==1) {
            //System.err.println("第一个黄金圆盘从"+from+"移到"+target);
        }else {
            //把上边的从源 移到 中间
            hanoi(n-1, from, target, mid);
            //System.err.println("把第"+n+"个黄金圆盘从"+from+"移到"+target);
            //把上边的从中间 移到 目标
            hanoi(n-1, mid, from, target);
        }
    }
}