研究帖19


作者へのメッセージ
研究課題 ブラック博士のハノイの塔

研究課題 ブラック博士のハノイの塔

 

 

そよ風さん「博士!、博士!ちょっと聞いて下さいよ!」

ナイス博士「やあ、そよ風さん、どうしたんだい?」

そよ風さん「ちょっと聞いて下さい!オーナーから酷い事を聞いたんです。!」

ナイス博士「ほう、なんだね?」

そよ風さん「このあいだ私達が作った女王様の部屋を決めるプログラムなんですけど、まるで だめだって言った人がいるんです!」

ナイス博士「なっ何!だっだれだ!そんな事をいうのは!」

そよ風さん「知らない人です。オーナーの所に突然訪ねて来たセールスマンで、ブラック伴二郎 博士と名乗ったそうです!」

ナイス博士「何!怪しい名前だな!何ていう会社だ!」

そよ風さん「ブラックプログラム研究所だそうです!」

ナイス博士ブラックプログラム研究所だって!!

 

 

 

ナイス博士「何か、うちの名前に似ているな。」

そよ風さん「ええ、その人が外国から帰ってきて、最近作ったそうです。」

ナイス博士「で、いったいどこがだめだって言うんだ!」

そよ風さん「それが、8クイーン問題は、再帰を使って解くのが当り前だそうなんです。私たち は使っていないから、再帰も使えない、とんでもない馬鹿プログラマーだ!なんて言ったそうです!」

ナイス博士「何だって!再帰を使ってないからって、そんな無茶な言い方をするなんて、とんで もない奴だ!」

そよ風さん「そうですよ!でも、その博士は、その場で私たちのプログラムを見て、すぐ もっと短いプログラムに書き換えたそうです。しかも、その時のパソコンの操作が、まるでピアニストの ように素早く、美しかったそうで、オーナーはすっかり信じこまされて、そのうち大きな仕事を頼むんだ! なんて言っているんです!」

ナイス博士「うーーん、これはおかしい!きっとだまされているんだ!」

そよ風さん「ええ、何とかしないと!」

ナイス博士「そうだな、どうしたらいい?」

そよ風さん「その人は、オーナーに対して、本当に良いプログラマーなら、この問題が解ける はずだ、と言って、奇妙な物を置いていったそうです。」

ナイス博士「何!それはどんな物だい?」

そよ風さん「何でも、平たい板に棒が3本立っていて、そのうち一本に、穴があいて大きさが 違う円盤が、下から大きい順に5枚刺さっているんです。」

ナイス博士「何!それはきっと!」

そよ風さん「それは?」

ナイス博士ハノイの塔だ!!

そよ風さんハノイの塔??

 

 

そよ風さん「何ですか?ハノイの塔って?」

ナイス博士「一本の棒の円盤を、他の棒に全部入れ替えるゲームなんだ。」

そよ風さん「それだけですか?簡単じゃないですか。」

ナイス博士「いや、ルールがあって、」

*******************************************************************************************

1.一度に1枚しか動かせない。

2.棒以外の所に円盤を置けない。

3.小さい円盤に大きい円盤を乗せてはいけない。

*******************************************************************************************

ナイス博士「これを守るんだ。」

そよ風さん「ああ、そうですか。どうやって解くんですか?」

ナイス博士「そうだなあ、まず最初の2枚を、1番目の棒から3番目に動かすには、どうする?」

そよ風さん「そうですね、2枚目を下にするんだから、1枚目を2番目の棒にいれて、2枚目を 3番に入れて、また2番目の棒の1枚目を3番に動かします。簡単ですね!」

ナイス博士「そうだな。じゃ、上から3枚を、1番目から3番目に動かすには?」

そよ風さん「うーーん、ちょっとややこしいですね。」

ナイス博士「うん。でも、仮に最初の、1番目から3番目に2枚動かすプログラムを void move2Disc(1番目,3番目)とすれば、まずmove2Disc(1番目,2番目)をやって、3枚目を3本目の棒に 入れて、またmove2Disc(2番目,3番目)をやれば良いんだ。」

ナイス博士「なるほどね。じゃ、4枚動かすのは?」

ナイス博士「さっきの方法を仮にmove3Disc(1,3)とすれば、まずmove3Disc(1,2)を やって........」

そよ風さん「ちょっ、ちょっと待って下さい!それじゃ、1枚ごとにプログラムを 作るんですか?」

ナイス博士「いや、どのプログラムも引数以外同じに出来れば、再帰で何回でも呼び出して 使えるんはずなんだ。」

そよ風さん「ああ、そうですか。で、どんなコードを書けばいいですか?」

ナイス博士「うーーん、どうしたら良いかなあ、こんな時にBB君がいてくれたら........」

そよ風さん「博士、何言ってるんですか!あんな、ブラックプログラム研究所なんて所に、 勝手な事を言われてだまってられないですよ!何とかこのプログラムを作って、私たちの実力を見せ付けて やりましょうよ!」

ナイス博士「よし、やろうじゃないか!」

 

 

 

ナイス博士「うーーん、」

そよ風さん「うーーーーん、」

ナイス博士「どうかね、少しは出来たかね?」

そよ風さん「いや、まだです。どうしたら良いですか?」

ナイス博士「そうだな、まず棒と円盤のクラスが必要だな。たとえば、」

 

****************************************************************

class Peg{
    int[] disks;
    int top;
    
    Peg(int capasity){
        disks=new int[capasity];
        top=-1;
    }
    
    void setDisks(){
        for(int i=0;i<disks.length;i++){
            disks[i]=disks.length-i;
        }
        top=disks.length-1;
    }
}

*****************************************************************

ナイス博士「こんな感じだな。」

そよ風さん「なるほど、棒に刺さっている円盤を配列にしてるんですね。topは何の変数ですか?」

ナイス博士「一番上の円盤のインデックスだ。だから最初は円盤が無いから-1で、円盤を 入れたら1足して0にするんだ。このクラスで棒のインスタンスを3つ作って、そのうち1つに void setDisksで円盤をセットするんだ。」

そよ風さん「そうか。じゃ、円盤を移動する時、出す方の棒のtopを1つ減らして、入れる方を たすんですね。たとえば」

 

****************************************************************

Peg p1=new Peg(5);
Peg p2=new Peg(5);
Peg p3=new Peg(5);

p1.setDisks();
p2.disks[top++]=p1.disks[top];
p1.disks[top]=0;
p1.top--;

*****************************************************************

そよ風さん「こんな感じですか?」

ナイス博士「うーーん、あまり良くないな。せっかくjavaでやるんだから、もっとオブジェクト 指向的に分りやすく出来るよ。たとえば」

 

****************************************************************

int getDisk(){
        int temp=disks[top];
        disks[top]=0;
        top--;
        return temp;
    }
    
    void setDisk(int disksize){
        top++;
        disks[top]=disksize;
    }

*****************************************************************

ナイス博士「こう言うのを作っておけば、p2.setDisk(p1.getDisk())と書けば、これだけで 出来るだろう?」

そよ風さん「ああ、なるほどね、いかにも1番目の棒から円盤を取って2番目にセットする、 と言う感じで出来ちゃいますね。」

ナイス博士「よし、出来たぞ!これでどうだ!!」

 

  アプレット

Peg.javaのコード Game.javaのコード AppletStart.javaのコード

 簡単なクラス図

 

 

そよ風さん「すごい!さっそくオーナーに見せに行きます!」

 

続く。

 

」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」

*参考

 

ハノイの塔に関して詳しい説明を見つけました。

http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94

(ナイスプログラム)

作者へのメッセージ

 

研究課題に戻る。

 見学者への注意事項に戻る。