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つの異なる自然数の和で表現すると言うことになります。 どういうアルゴリズムで作れば無駄なく作れるでしょうか。 ちなみに,上の例では,
でもこんな書き方(アルゴリズム)では,数が大きくなると大変そうだ。 異なる自然数の和と言うのも面倒だし, 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という言語で組んだプログラムです。 置きました。 |