- 追加された行はこの色です。
- 削除された行はこの色です。
NetaTaneMenu >>>> ビリヤードのパズル >>>>
*整数の分割のアルゴリズム
ビリヤードのパズルを力技で解くプログラムを作る為には,
所謂,整数の分割と言うことを実現しなければなりません。
例えば,元々のビリヤードの玉を5個使って1から21まで・・・という場合では,
21=1+2+3+4+11=1+2+3+5+10=1+2+3+6+9=1+2+4+5+9=1+2+3+7+8=1+2+4+6+8
という具合に(これで全部かなあ?)合計が21になる5つの玉の組合せをまず
候補に上げなければなりません。
これは21と言う自然数を5つの異なる自然数の和で表現すると言うことになります。
どういうアルゴリズムで作れば無駄なく作れるでしょうか。
ちなみに,上の例では,
+まず,1+2+3+4として,残りの11を加えてこれをトップバッターにする。
+次に,11を一つ減らして,4を一つ増やして見る。全体の和は変わらない。
+これを繰り返すのだが,例えば,3+6のような形が出てくれば,4+5と変えることができる。
+ぶつぶつ
と言う具合に適当に並べています。
そこで,
でもこんな書き方(アルゴリズム)では,数が大きくなると大変そうだ。
異なる自然数の和と言うのも面倒だし,
21=1+2+3+4+11=1+2+3+5+10=1+2+3+6+9=1+2+4+5+9=1+2+3+7+8=1+2+4+6+8
の代わりに
6=0+0+0+0+6=0+0+0+1+5=0+0+0+2+4=0+0+1+1+4=0+0+0+3+3=0+0+1+2+3
を考えれば少々楽じゃないかなあと考えました。これは図にすると,
■
■ ■
■ ■ ■ ■
■ ■ ■ ■ ■■
■ ■ ■■ ■ ■■
_____■ ____■■ ____■■ ___■■■ ____■■
のようなヤング図形のようなものになりますね。
でもヤング図形ではないので少し調べると,
フェラーズ図形と言うようです。
そこで,このような和を作るプログラムを組んだのですが…。
残念。時間切れです。急な仕事が舞い込んできました。
ではこの続きはまた。
----
そうそう。いろんな方法を考えて見てください。
一緒に上手い構成法?アルゴリズムを探してください。
ではでは。
肝心なものを忘れていました。rubyという言語で組んだプログラムです。
置きました。