方々で色々な方が解かれていますが。
問題 1 : 油売り算
斗桶 (a) に油が 1 斗 (10 升) ある。これを等分したい。7 升枡 (b) と 3 升枡 (c) しかない。この 2 つの枡だけで、5 升ずつ等分する方法を記述せよ。
この問題を解くにあたり、(a) に入っている油の容量を第 1 引数、(b) の容量を第 2 引数、(c) の容量を第 3 引数とするプログラムとせよ。
もちろん、(a), (b), (c) に条件を付けなければ解けない場合もあるが、その場合には条件としてどのようなものがふさわしいかを余力があれば考えよ。
http://karetta.jp/article/blog/ll-spirit/033840
パッと見、ambや探索木を利用した解法ばかりの様だったので、別のアルゴリズムを考えてみることにしました。
プログラムは未だ書いて無いですが、その内書きます。
先ず、此の問題について整理してみると、三升桝と七升桝を使って、十斗桶から油を引いたり足したりしながら等分しろと云う事になります*1。
詰まる所、10に3や7を何回か足したり引いたりしながら5を作れば良い事になります。更に云えば、3や7の倍数(正とは限りません)を足して(-5)を作れと云う問題に成るのです。
よって、
3x+7y=-5
という式が出来上がります。このx, y を見たす整数を見付けられれば良い訳です。
さて、もう一つ式が有れば*2連立方程式となり解が一組に定まりますが、この場合一つきりなので解は無数に存在します。しかし、式を変形して行くことで、一般解を求める事は出来ます。
3x+7y=-5
3x=-5-7y
x=(-5-7y)/3あとは、-5-7y が 3 で割り切れる様に y を決めてやれば良いのですが、それも面倒なのでx, yを新しい変数 t で表し、t=..., -1, 0, 1... と代入すればx, yが定まる様にします。
-5-7y≡0(mod 3)
7y≡-5(mod 3)
y≡1(mod 3)
∴ y = 1+3t
x = (-5-7y)/3
= {-5-7( 1 + 3t)} / 3
= (-12 -21t)/3
∴ x = -4-7t今、 t = 0 とすれば、 x = -4, y = 1 と成り、従って三升桝で4回掻き出し、七升桝で一回戻せば良いことが分かります。確かに、3*(-4)+7*1=-5 ですし、例題の解答とも一致します。
今解いた様な方程式を、一次不定方程式と呼び*3、未知数がx, y のみの場合以下の様な式で表されます。
px+qy=r
この方程式に整数解が存在する為には、一般に r が p, qの最大公約数で割り切れなくては成らないことが分かります。
最大公約数を d とすると、 p, q は当然 dp', dq' と云った形で表され、px + qy はdの倍数に成ります。よって、右辺のrもdで割り切れなくては成りません。
これが、此の問題に対する私の回答です。……あとは、Haskellを使って実際に書くのみですな……時間がorz
