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. まず,1+2+3+4として,残りの11を加えてこれをトップバッターにする。
  2. 次に,11を一つ減らして,4を一つ増やして見る。全体の和は変わらない。
  3. これを繰り返すのだが,例えば,3+6のような形が出てくれば,4+5と変えることができる。
  4. ぶつぶつ と言う具合に適当に並べています。

でもこんな書き方(アルゴリズム)では,数が大きくなると大変そうだ。 異なる自然数の和と言うのも面倒だし,

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という言語で組んだプログラムです。 置きました。


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2005-01-28 (金) 16:42:22 (6105d)