ハノイの塔(ハノイタワー-Hanoi)

1.1.説明ハノイの塔(Towers of Hanoi)はフランス人M.Claus(Lucas)が1883年にタイからフランスに連れて行ったもので、ハノイはベトナム戦争時の北越の首都、現在のホーチミン市である.1883年にフランスの数学者Edouard Lucasがこの物語に言及したことがある.創世記の時、Benaresには3本のダイヤモンド棒(Pag)で支えられていたバルト教塔があり、最初は神が1本目の棒に64個の上から下まで小から大に並ぶ金盤(Disc)を置き、僧侶にすべての金盤を1本目の石棒から3本目の石棒に移すように命令したという.そして、運搬中に大皿が小皿の下にあるという原則を守り、毎日1つの皿だけを運ぶと、皿が全部運ばれると、この塔は破壊され、世界の終わりが来る時である.1.2.解法柱がABCと表記されている場合、AからCに運び、皿が1つしかない場合はそのままCに運び、皿が2つある場合はBを補助柱とする.皿数が2つを超えると、3つ目以下の皿を隠すのは簡単で、毎回2つの皿を処理します.つまり、A->B、A->C、B->Cの3つのステップで、隠された部分は、実はプログラムの再帰処理に入ります.実際、n個の皿があれば、移動完了に必要な回数は2^n-1であるため、盤数が64の場合、必要な回数は264-1=18446744073709551615が5.05390248594782 e+16年、つまり約5000世紀であり、この数字にあまり概念がなければ、毎秒1つの皿を運ぶと仮定すれば、約5850億年程度かかる.
 
C言語コード:

#include <stdio.h>

void hanoi(int n, char A, char B, char C) {
    if(n == 1) {
        printf("Move sheet %d from %c to %c
", n, A, C);
    }
    else {
        hanoi(n-1, A, C, B);
        printf("Move sheet %d from %c to %c
", n, A, C);
        hanoi(n-1, B, A, C);
    }
}

int main() {
    int n;
    printf("     ：");
    scanf("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    return 0;
} 

 
Javaコード:

package test;

public class Hanoi 
{
	/**
	 *  n     a   c  ，                 
	 * @param layers
	 * @param placea
	 * @param placeb
	 * @param placec
	 */
	public static void move(int layers, String placea, String placeb, String placec)
	{
		if (layers == 1)
		{
			System.out.println("Move dish " + layers + " from " + placea + " to " + placec);
		}
		else
		{
			
			Hanoi.move(layers-1,placea,placec,placeb);
			System.out.println("Move dish " + layers + " from " + placea + " to " + placec);
			Hanoi.move(layers-1, placeb, placea, placec);
		}
	}

	public static void main(String[] args) 
	{
		Hanoi.move(3, "a", "b", "c");
	}
}