研究帖28-11

 

 

 

 


作者へのメッセージ
研究課題 スタックでプッシュアンドポップ!

研究課題 スタックでプッシュアンドポップ!

 

   

 

そよ風さん「カチャポンカチャポン、ランランラン♪!クルポンクルポン、タリラリラン♪!

         カチャカチャポンポン、ホイホイホイ♪!!」

ナイス博士「おおっ!そよ風さん、今日も調子良さそうだな!!」

そよ風さん「ええ、絶好調です。もうちょっとで完成ですよ!」

ナイス博士「そうか。特別No.1研究員になってからの君は、見違えるように上達したな!」

そよ風さん「そうですか!!ま、この程度の実力はもともとですけどね。」

 

 

 

BB君「博士!博士!見て下さい!ついに、ぴったりの組み合わせを見つけるプログラムが出来ました!!」

ナイス博士「なんだ、BB君か。」

そよ風さん「ちょっと、今さら何言ってるのよ、もうとっくに先に進んでるのよ。」

BB君「まあ、とにかくコードを見てくれ!!」

 

アプレットを開く。

AppletFrame3.javaのコード

TestData.javaのコード

MatchCombination13.javaのコード

 簡単なクラス図

 

 

ナイス博士「おお、すっきりしたコードだな!」

BB君「ええ、スタックを使えば、わざわざ再帰なんか使わなくても、簡単に出来るんです!」

そよ風さん「なっ、何よ!短ければ良いってもんじゃないわ!」

ナイス博士「で、性能はどうなんだい?」

BB君「フッフッフッ、じゃあ、組み合わせ数を5000でやって見ましょう。」

そよ風さん「ええーーっ!!5000!!

ナイス博士「じゃ、ちょっと私は、終わるまでにトイレに...」

BB君クリック!!....博士、出来ましたよ!!」

ナイス博士もう出来たのか!!はっ、早い!」

BB君「じゃ、組み合わせ数を10000でやって見ましょう。」

そよ風さん「ええーーーーーっ!!10000!!

BB君クリック!!.............出来ましたよ!!」

ナイス博士はっ、早い!!!

BB君「どうですか、スタックを使うとこんなに早くなるんです!」

 

     

 

そよ風さん「今さらそんなコードを作っても、私はもう完成間近よ。」

BB君「いや、君のコードには、まだまだ問題があるんだ。」

そよ風さん「なっ、何の事よ!」

BB君「研究帖28-9の、MatchConbination10のコードを、製品の配列が{10,9,6,6,5,4,4,} で、原材料が11で、切りしろ無しでやってみれば分るよ。」

そよ風さん「フッ、何を言ってるのやら...たった7個の配列でいいの?クリック.....」

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

BB君「........博士、今のうちにトイレに行ったらどうですか?..........................」

そよ風さん「なっ、何よ!すぐ終わるわ................................................」

ナイス博士「じゃ、ちょっとトイレに...........戻ったぞ...あれ?まだかい......................」

BB君「無限ループに入ったから、ずっとこのままです........」

そよ風さん「......」

 

     

 

MatchCombination10.javaのコード

ナイス博士「いったいどうしてだ、BB君。」

BB君「最初の10で、{6,5}の組み合わせが出来て、使用済みになってしまうんです。」

そよ風さん「ええっ、そんな筈無いわ!わざわざループにしたのに....」

BB君「いや、デバッグモードで確認したんだ。void getElement(int total,int index) の最後の1行、getElement(total,index-1)が有るから、そのまま次の要素に進んでしまうんだ。」

ナイス博士「じゃあ、この配列では、早い段階で使用済みの要素が出来て、後の方で組み合わせ が出来なくなるから無限ループになるのか...」

BB君「そうです。ステップモードで実行して確認しました。」

ナイス博士「うーーーん、まいったなあ、やっとここまで来たのに...」

BB君「博士、大丈夫です!!余りが有ると処理が遅くなる原因がわかりました!」

ナイス博士、そよ風さん原因が!!

 

 

BB君「僕のコードで、スタックの中身を書き出す所がありますね。」

ナイス博士「うん、

        void getPrint(String s){
                System.out.println(s+"\n");
                for(int i=0;i<st.size();i++){
                    System.out.print(temp[st.get(i)]+",");
               }
               System.out.print("\n"+s);
               //System.exit(0);
            }

    ここだろう?」

BB君「これをアプレットじゃなくアプリケーションのTestFrame.javaで実行すると、 最初にぴったりの組み合わせが見つからず終わった時のスタックの中身が書き出されるんです。」

 

TestFrame.java

 

ナイス博士「ああ、なるほどね。」

BB君「で、ぴったりの配列に適当な余りを入れて動かして見たら、細かい数字が残ったんです。」

ナイス博士「ほう、それで?」

BB君「で、余りが途中に有ると処理が遅くなる原因ですが......」

 

 

 

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

【余りが有ると処理が遅くなる原因】

1.製品の長さの配列が{5,4,3,2,1,1,1,1,1,1,1,1}で、原材料の長さが6だとする。

2.長さの合計が22なので、余り4

3.長い方から順番に処理するので{5,2},{4,1,1},{3,1,1,1}が出来る。

4.{1,1,1,1}が余るが、数字が小さいのでネストが深くなり、終わるまで処理が遅くなる。

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

 

BB君「数字が小さければ小さいほどネストが深くなるので、処理の時間もかかるわけです。」

ナイス博士「そうか。なるほどねえ。」

そよ風さん「じゃあ、どうするのよ?」

BB君「それは..」

そよ風さん「原因がわかったら解決策も分るでしょ!」

BB君「いや、だから、それは....」

ナイス博士「そうだなあ、....まあ、簡単かもしれないな。」

BB君「えっ!どうするんですか?」

ナイス博士「ぴったりの要素が見つからずに配列が終わったら、その時の余りをそのまま余り用 のArrayListに入れるんだ。で、処理が全部終わったら、余った数字を出して同じ処理を繰り返すんだ。」

そよ風さん「それだけでうまく行くんですか?」

ナイス博士「そうだなあ、..まあ、やってみれば分るよ。」

そよ風さん「........」

 

続く。

 

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

 

作者へのメッセージ

 

研究課題に戻る。

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