研究帖28-5

そよ風さん「うーーん、うまく行かないわ。」

ナイス博士「どうだ！そよ風さん、研究の調子は？」

そよ風さん「あらっ、博士、博士の方は、出来たんですか？」

ナイス博士「出来たぞ！これを見てくれ。」

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

【加算方式】

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

2.一番小さい要素と、その次の要素を足す。void getElement(int total,int index)

3.与えられた長さに一致したら出力し、その次の要素で同じ処理をする。

4.短かったら、その差を引数にして、再帰で同じ処理を行う。getElement(total-ii[index],index-1)

5.与えられた長さを越えたら、戻る。

6.次に小さい要素で続ける。getElement(total,index-1)

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

そよ風さん「へえっ、どれどれ.....あれっ？.....これって、私のコードを改造して 作ったんじゃないですか？」

ナイス博士「そうだ！君は元の数値から要素を引いていって最後に0になる組み合わせを出すが、 私は0から足して行って元の数値に一致する組み合わせを出すんだ。」

そよ風さん「なあんだ、私のコードとほとんど同じじゃないですか。」

ナイス博士「そうじゃない！加算方式なら、ループを最後まで行かなくても合計値を超えたら 抜けられるから、スピードアップしているはずだ！」

そよ風さん「へえ、そうですか。ＢＢ君の方法や、ディップスイッチ法は、どうだったんですか？」

ナイス博士「いや、改良したが、そよ風さんの方法のほうがはるかに早かったんだ。 大したもんだ。腕を上げたな、そよ風さん。」

そよ風さん「えっ、いやあ、それほどでも..フフッ...。」

そよ風さん「じゃ、これを私のプログラムと比べて見ましょう。ダブルクリック！！ ................両方とも同じ時間ですよ。」

ナイス博士「えっ、同じか。おかしいな。もう一回やってみてくれ。」

そよ風さん「ええ、いいですよ。ダブルクリック！！ ................同じですね。」

ナイス博士「そうか。うまく行くと思ったんだがな。うーーーん、.....じゃ、戻って研究続行だ！」

そよ風さん「ちょっ、ちょっと待って下さい！」

ナイス博士「えっ、どうしたんだい？」

そよ風さん「実は、難しい問題が有るんです。」

ナイス博士「難しい問題だって！」

そよ風さん「ぴったりの組み合わせはたくさん出来ますが、全部はいらないんです。」

ナイス博士「ああっ、そりゃそうだ。」

そよ風さん「で、全部の木材が一番うまく切り取れる組み合わせをどうやって選ぶかが、 問題です。」

ナイス博士「そうか。..考えられる方法はいろいろ有るんじゃないか？たとえば.....」

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

【考えられる色々な方法】

1.バックトラック方式でぴったりの組み合わせを全部チェックして一番良い組み合わせを選ぶ。

2.前にエクセルで使った方法で組み合わせを作ってから余分な余りを修正する。

3.大きい要素から１つずつぴったりの組み合わせを探し、見つからなかった場合に前に使った 方法で組み合わせを選ぶ。

4.前に使った方法で余分な余りが出たら、余りの１番大きな数字を使ったぴったりの組み合わせを 作り、残った数字を前に作った方法で再度処理する。

5.そよ風さんの減算方式を使ってぴったりの組み合わせが出来るたびに、使った数字を配列から 削除し、最後に余った分を前に使った方法で処理する。

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

ナイス博士「うん、とにかく、バックトラック法はスタック不足になりそうだな。」

そよ風さん「そうですね。...ところで、前にエクセルで使った方法は、どんなプログラムですか？」

ナイス博士「じゃ、javaでやって見よう。」

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

【棒の切り取り問題解決プログラム】

1.原材料の木材に番号を付ける。

2.切り出す木材のうち一番長い物に、それ以上長い原材料のうち、一番短い棒の番号を付ける。

3.番号をつけたら原材料からその分の長さを引く。

4.全部の木材に番号がつくまで繰り返す。

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

そよ風さん「うまく行っているようですけど、どういう時にうまく行かないんですか？」

ナイス博士「たとえば{5,2,2,3,3,3}で、合計9になる組み合わせを出す場合だ。」

そよ風さん「{5,2,2}と{3,3,3}にはならないんですか？」

ナイス博士「うん。大きい方から組み合わせるから{5,3}、{3,3,2}で、 最後に{2}が余るんだ。」

そよ風さん「ああ、そうか。棒が2本でいいのに、3本必要になりますね。」

ナイス博士「うん。だから、この場合{5,2,2}を先に作れば、後はうまく行くと思うんだ。」

そよ風さん「じゃ、とにかく、【考えられる色々な方法】のどれかで、やって見ます！」

ナイス博士「うん、頑張ってくれ！」

続く。

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

研究課題に戻る。

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