【javaデータ構造とアルゴリズム学習】ハノータ
ハノタは再帰的な分治思想が言わざるを得ない経典のケースだ.
ハノタ(河内塔とも呼ばれる)問題はインドの古い伝説に由来する知的玩具だ.大梵天が世界を創造した時、ダイヤモンドの柱を3本作り、1本の柱の上に64枚の黄金円盤を下から上へ大きさ順に積み上げた.大梵天はボロモンに円盤を下から大きさ順に別の柱に並べ直すように命令した.また、小円盤では円盤を拡大することができず、3本の柱の間で一度に1つの円盤しか移動できないことが規定されている.その後、この伝説はハンノタゲームに発展し、遊び方は以下の通りである.ロッドA,B,Cが3本あります.Aロッドに皿がいくつかあります.皿を1枚動かすたびに、小さいのは大きな上に重ねるしかありません.
3.全ての皿をAロッドからCロッドに全て移す
私たちはどのようにハンノタというプログラムを実現しますか?
主な思想:再帰分治の思想
(1).Aのn-1皿をBに移動
(2).Aの上のn番目の皿をCに移動します
(3).Bのn-1皿をCに移動
次はハンノタワーのコード実装です.
ハノタ(河内塔とも呼ばれる)問題はインドの古い伝説に由来する知的玩具だ.大梵天が世界を創造した時、ダイヤモンドの柱を3本作り、1本の柱の上に64枚の黄金円盤を下から上へ大きさ順に積み上げた.大梵天はボロモンに円盤を下から大きさ順に別の柱に並べ直すように命令した.また、小円盤では円盤を拡大することができず、3本の柱の間で一度に1つの円盤しか移動できないことが規定されている.その後、この伝説はハンノタゲームに発展し、遊び方は以下の通りである.ロッドA,B,Cが3本あります.Aロッドに皿がいくつかあります.皿を1枚動かすたびに、小さいのは大きな上に重ねるしかありません.
3.全ての皿をAロッドからCロッドに全て移す
私たちはどのようにハンノタというプログラムを実現しますか?
主な思想:再帰分治の思想
(1).Aのn-1皿をBに移動
(2).Aの上のn番目の皿をCに移動します
(3).Bのn-1皿をCに移動
次はハンノタワーのコード実装です.
public class Hanno {
public void move(int n, String A, String B, String C){
if (n == 1){
System.out.println(A +"-->"+C); //
}else {
move(n-1,A,C,B); // n-1 A B
System.out.println(A + "-->" + C); // n A C
move(n-1,B,A,C); // n-1 B C
}
}
public static void main(String[] args) {
Hanno hanno = new Hanno();
hanno.move(3,"A","B","C");
}
}