研究帖28-4

BB君「博士、見ましたか！彼女の高飛車な態度を！」

ナイス博士「まったくだ！最近ちょっと腕を上げたからって、調子に乗りすぎだ！この間なんか 研究帖に、私がボケてきた、なんて書いてるんだぞ！」

BB君「ええっ！そんな事を書いたんですか？」

ナイス博士「そうなんだよ！BB君、彼女をこのままほっといたら、ますます冗長するぞ！！」

BB君「そうですね。ここらで僕たちのすごさを見せ付けないとだめですね！」

ナイス博士「そうだな。やろう！」

BB君「しかし、彼女のプログラムは、かなり高性能ですよ！」

ナイス博士「うん。」

BB君「配列の要素が50以上でも、全然問題ないようですよ！」

ナイス博士「うん。」

BB君「しかも、100ミリ秒もかからないようですよ！」

ナイス博士「うん。」

BB君「ねえっ！博士！」

ナイス博士「ちょっと待ちたまえ！考えてるんだから。....うーーん、 ちょっと気になる事が有るんだ。」

BB君「何ですか？」

ナイス博士「彼女は、不要なループを途中で抜けるために条件分岐したら、かえって 1ミリ秒遅くなったって言ったんだ。」

BB君「そうですか。それは変ですね。」

ナイス博士「うん。」

BB君「うーーん、......まてよ？」

ナイス博士「えっ、何か思いついたかい？」

BB君「博士がエクセルVBAでやった時、わずか16要素の配列で、シートが１枚いっぱいに なったって言ってましたよね。」

ナイス博士「うん。」

BB君「と言うことは、配列の要素数よりはるかに多くの組み合わせをチェックしている事に なりますね。」

ナイス博士「そうだな...。」

BB君「だから、１回ごとに条件分岐するだけでも膨大な回数になって時間がかかるし、 その結果多少早くループを抜けられても、場合によっては遅くなってしまうんじゃないですか？」

ナイス博士「ああ、なるほど！そう言えば、BB君のコードは、１回ごとの計算内容が多いな。」

BB君「ええ、何とかならないかなあ。...」

ナイス博士「そうだ！計算回数を減らせばいいんだから、いっそのこと、配列の インデックスの組み合わせを、使えそうな分だけ出してから計算したらどうだい？..前に、そういう プログラムを作った事があるんだ。」

BB君「へえ、どうするんですか？」

ナイス博士「こうだよ。」

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

1.与えられた配列をソートする。

2.小さい方から足していって与えられた合計を越えたら、その時の要素数-1が 最大要素数となる。

2.大きい方から足していって与えられた合計を越えたら、その時の要素数-1が 最小大要素数となる。

3.研究帖21で作った、インデックスの組み合わせを全て出すプログラムで、最小要素数 から最大要素数までの数の、インデックスの組み合わせを全部出し、ArrayListに記録する。

4.ArrayListから１つずつ呼び出し、その組み合わせで与えられた配列の要素を組み合わせ、 その合計値が与えられた合計と一致したら、ArrayListのそこの項目を要素の組み合わせに書き換える。

5.一致しなかったらその要素を削除する。

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

BB君「なるほどねえっ！」

ナイス博士「うん。だが、まだ問題が有るぞ。」

BB君「何ですか？」

ナイス博士「研究帖21のコードも、再帰を使ってるから、スタック不足になるんじゃないか？」

BB君「ああ、そうか。じゃ、再帰を使わないでバックトラック法をやるしかないな。」

ナイス博士「うん。でも、出来るのかな。」

BB君「そうですねえ。....でも、研究帖16の8クイーン問題でやってるじゃないですか。」

ナイス博士「ああ、そうだったな。」

BB君「まあ、考えてみます。博士も、ディップスイッチ法を改良してみてください。」

ナイス博士「うん。やって見るよ。」

そして１時間が過ぎた。.....

BB君「博士！出来ましたよ！」

ナイス博士「そうか、私も出来た所だ。」

BB君「じゃあ、早速見せて下さい。」

ナイス博士「うん。これだ！」

【ディップスイッチ方式その２】

アプレットを開く。

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

1.与えられた配列、int[] ii と同じ長さの配列、int[] dswitchを作る。

2.それぞれの要素に、２のインデックスの累乗の数値を入れる。

3.dswitchの要素数と同じビットの２進数を０から最大値までカウントする。

3.カウントごとにそれぞれのdipswitchの要素とカウントとのandをビット演算する。

4.iiの要素のうち、演算の結果0にならなかったdswitchの要素と同じインデックスの要素を 合計して、与えられた合計と一致すれば、それらの要素をArrayListに出力する。

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

BB君「なるほどね、だいぶ単純になったですね。」

ナイス博士「うん。余計なクラスはやめたから、早くなったと思うんだ。君のは？」

BB君「これです！」

【再帰を使わないバックトラック方式】

アプレットを開く。

BB君「じゃ、早速この前の配列で試して見ましょう！」

ナイス博士「うん、確か、

{1,1,1,2,2,2,3,4,5,6,7,8,9,10,11,12,13,14,15} で、合計値28だったな。

クリック！..........................................？？？」

BB君「あれ？？？..........................................」

ナイス博士「.....................................141ミリ秒か、う---ん。まだ遅いな。」

BB君「ええ、そうですねえ。」

ナイス博士「でも、君のプログラムがあるじゃないか！早速試してみよう！」

BB君「ええ、とりあえず、要素11個でやってみます。クリック！.....」

ナイス博士「.........................................出来た！」

BB君「15ミリ秒ですね。」

ナイス博士「うん、答えも合ってるぞ。よし！もっと要素を増やしてみよう！」

BB君「はい！！19個でクリック..................................................」

ナイス博士「.........................................................................」

BB君「...............................................................................」

ナイス博士「.........................................................................」

BB君「...............................................................................」

ナイス博士「.........................................................................」

BB君「...............................................................まだかな？......」

ナイス博士「......................................................だめだこりゃ！！」

BB君「いやあ、遅いな！」

ナイス博士「まっ、まずいぞ！！」

BB君「こんなプログラムをそよ風さんに見せたら、もっと調子に乗って、僕たちを さんざん馬鹿にしますよ！」

ナイス博士「そんな事になったら大変だ！とにかく、どんな手段でもいいから、彼女のより 0.1ミリ秒でも早く出来るプログラムを作るんだ！」

BB君「うーーん、どうしたらいいか........クルルルッ..クルルルッ.....あっ！ 電話だ！..はい、もしもし....何！....わかった！すぐ行くぞ！！」

ナイス博士「おいおい！いったい何だ？？」

BB君「博士、ブラック博士について、重要な情報がはいったそうです！すぐに行って見ます。」

ナイス博士「ええっ！...じゃあ、プログラムは？」

BB君「ちょっとそれどころではなくなりました。国家的最重要事項なので。」

ナイス博士「ええっ、しょうがないなあ。....」

BB君「博士！極秘行動なので裏口から出ます！」

ナイス博士「そうか、じゃあ、こっちの出口から出なさい。」

BB君「....すいません、ドアが開かないんですけど。」

ナイス博士「そうじゃないよ。何をやってるんだ。押すんじゃなくて引くんだよ！」

BB君「ああ、そうか。じゃ、また来ます。」

ナイス博士「......まったく、こんな大事な時に行ってしまうんだから、彼も頼りに ならないな。ドアの開け方さえ分らないんだから。..押してもだめなら引いて見ろって言うじゃ ないか........................ん？....押しても..だめなら...引いて.................... ...........................ああっ！！そうだ！！！」

続く。

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

研究課題に戻る。

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