研究帖28-1

そよ風さん「博士、今日は。」

ナイス博士「やあ、そよ風さんか。どうだい研究の調子は？」

そよ風さん「ええ、実は難しい問題を頼まれたんです。」

ナイス博士「へえ、どんな事？」

そよ風さん「親戚のおじさんが材木商をやってるんですが、最近 毎月のように大量の注文が来るんです。」

ナイス博士「ほう、それは良かったな、大儲けじゃないか！」

そよ風さん「それが、困った事に、注文の長さがまちまちで、うまく切らないと、材料が足りなく なったり、無駄が多すぎて全然儲からなかったりするんです。で、うまい切り方を計算するプログラムを 作ってくれと頼まれたんです。」

ナイス博士「そうか、どんなプログラムが作りたいんだい？」

そよ風さん「はい、こんな感じです。」

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

1.原材料となる木材の長さを入力する。

2.切り取る木材の長さを全て入力する。

3.切りしろの長さも入力する。

4.最も少ない原材料で、全ての木材を切り出す長さの組み合わせを表示する。

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

ナイス博士「なあんだ、これなら棒の切り取り問題が使えるぞ！」

そよ風さん「そうですか！棒の切り取り問題ですね！さっそく "何でも入門書"で調べて見ます！！！」

ナイス博士「あっ、ちょっ、ちょっと待ちたまえ！おいっ！.......ああ、行っちゃったか。」

そよ風さん「博士！棒の切り取り問題なんて、"何でも入門書"に載ってませんよ！」

ナイス博士「そりゃそうだよ。私が勝手に付けた名前なんだ。」

そよ風さん「何だ！早く言って下さいよ！」

ナイス博士「いや、言おうと思ったらさっさと出てっちゃったから言えなかったんだ！」

BB君「あれっ、二人でいったい何を言い争ってるんですか？」

ナイス博士「実は、こういう訳なんだ。」

BB君「なあんだ、それならナップザック問題の解き方で出来るよ！」

そよ風さん「へえ、ナップザック問題ね！よし、さっそく！！....」

ナイス博士「いや、だから、ちょっと待ちなさい！！」

そよ風さん「ちょっと！何で引き止めるんですか？」

ナイス博士「だから、棒の切り取り問題の解き方は、もう分ってるんだよ！！」

そよ風さん「なんだ！早く言って下さいよ！！」

ナイス博士「いや、だから、.......ぶつぶつ...ぶつぶつ....」

ナイス博士「以前、エクセルVBAでやって見たことがあるんだ。こんな感じだ。」

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

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

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

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

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

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

そよ風さん「割と単純ですね。これでうまく行くんですか？」

ナイス博士「まあまあうまく行ったが、完全じゃないんだ。無駄が出る事があるんだ。」

そよ風さん「そうですか。どうしてかな？」

ナイス博士「これは、長い棒から先に切り出せば、少なくなった残りからだんだん短い棒を 切り出すので、残りを少なくしやすいだろうと、考えたんだが、人間が自分でやる時は、もっとうまく やるだろう？」

そよ風さん「そうですか。うーーん、....まあ、わざと短い棒を組み合わせて、ぴったりの 長さにしたりしますよね？」

ナイス博士「そのとおりだよ。実際テストして見ると、余りが0になるはずの組み合わせで 余りが出る事が有ったんだ。」

そよ風さん「そうですか。で、どうしたんですか？」

ナイス博士「そこで、まず原材料とぴったりの長さになる木材の組み合わせを出してから、 残りの木材を最初のプログラムで計算すれば良いと思ったんだが、その時、ふと、配列の数字の全部の 組み合わせを出すには、どうしたら良いかと考えたんだ。」

そよ風さん「そうですか。」

BB君「で、どうしたんですか？」

ナイス博士「インターネットで調べると、方法が書いて有ったんだが、それが正しいと 証明する方法がわからなかったんだ。」

そよ風さん「そうですか。博士は数学が苦手ですからね。」

ナイス博士「うん。そこで、数学を使わなくても正しいと証明できるような方法がないかと 思ったんだが、ちょうどその時、初級シスアドの勉強をしていて、ディップスイッチの問題が出て いたんだ。」

そよ風さん、BB君「ディップスイッチ！！」

そよ風さん「ディップスイッチって何ですか？」

ナイス博士「パソコンや家電製品のマイコン基盤の部品で、小さなスイッチが並んで ついていて、たとえば４つついていれば、４ビットの二進数が表現できるんだ。」

そよ風さん「へえーー」

BB君「で、どんな問題だったんですか？」

ナイス博士「確か、４ビットのディップスイッチでは、入り切りの組み合わせは何通りあるか、 と言うような問題だったかな。何通りだと思う？」

そよ風さん「４ビットと言う位ですから、２の4乗で、16通りですか？」

ナイス博士「そうだね。で、この場合、それ以外のスイッチの組み合わせは有り得ない事と、 16のうちで同じスイッチの組み合わせは2回出て来ない事は、別に数学で証明しなくてもはっきり しているだろう？」

BB君「そうですね！スイッチの入り切りは二進数の１と０の組み合わせと同じだから、０から 16までで同じ数字は2回出て来ないし、16以上の組み合わせは絶対表現出来ませんからね。」

そよ風さん「そうね！それが出来たら数字とは言えませんね！」

ナイス博士「うん。だから、数字の配列を、要素数と同じビットのディップスイッチのように 考えて、入り切りすれば、全ての組み合わせが重複なしで出て来ると思ったんだ。まとめると、」

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

1.組み合わせる数字を全て配列に入れる。

2.配列の要素数と同じビット数の2進数を、0から最大値までカウントする。

3.各カウントで、1になったビットのインデックスの要素だけを書き出す。

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

そよ風さん「へえーー、なるほど！いいアイデアですね！」

BB君「で、それからどうしたんですか？」

ナイス博士「それが、まだ問題が有ったんだ。」

そよ風さん「何ですか？」

ナイス博士「エクセルVBAでやったんだが、配列の要素が16あると、一行に1つの組み合わせで シートが一枚いっぱいになってしまうんだ。17だと、その2倍だ！　18だと、さらに倍だ！！！」

そよ風さん「そりゃあすごいわ！」

BB君「でも、原材料の長さとぴったりの組み合わせだけ出せば、だいぶ減るんじゃ ないんですか？」

ナイス博士「そうだろうな。でも、計算に時間がかかりそうだし、方法さえわかったら ちょっと興味が薄れて、初級シスアドの勉強もやっていたんで、そこまででやめてしまったんだ。」

そよ風さん、BB君「なるほどねえーー」

ナイス博士「そういうわけで、今回再度、javaで挑戦だ！！」

そよ風さん、BB君「そうですね！やりましょう！！」

続く。

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

ディップスイッチについて詳しい説明が見つかりました。

（ナイスプログラム）

ディップスイッチについて

研究課題に戻る。

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