修正履歴
  • 2014/1/6 数式の記述ミスや記述のあいまいさを訂正。大体の記述はあってるはずなのでここで仮完成とする。




Problem 142 「完全平方数コレクション」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20142
x + y, x - y, x + z, x - z, y + z, y - zが全て平方数となる整数の組 x > y > z > 0で, 最小の x + y + z を求めよ.



解法

この問題は深さ制限探索で解きます。
まず式を定義しなおします。
  • x+y=S1
  • x-y=S2
  • y+z=S3
  • y-z=S4
  • x+z=S5
  • x-z=S6
と定義します。(S1~S6は当然平方数)
探索を行うに当たってできるだけ早めに、(x,y,z)の組が式の条件を満たすことが判明すれば答えが高速に見つかる希望が持てます。

まず深さ制限探索の上限を決めます。
x>y>zよりx+yが一番大きな数となるのでS1の上限を適当に定めます。(答えが見つからなかったらあとでS1を増加させてコードを再実行します)。


前準備のメモ化

S1の上限をn1^2とするとS1は

S1=(4,9,16,,,,n1^2)の値をとります。
まずS1とS2はx+yとx-yですからxはS1、S2から等距離にあることがわかりこれはS1とS2の平均です。
S1>S2,S1<=n^2となるS1、S2のすべての組み合わせでxのリストを作りこれをxsとします。
x=(S1+S2)/2とxを定義できます(当然xが整数となるものだけです)。

またyはy=s-S2と定義することができx、yの組が作れます。
xに対応するyは複数得られxの各値に対しyのリストが空集合か1個以上のyのリストが作られます。
これをメモ化しておきます。


ここで以下のような操作を考えます。
ys=f(x)をxsの要素xをf(x)に一つ代入する操作と考えます。関数fは上のメモ化で求めたデータを基にxの値から対応するyのリストを返します。

次にysの要素を一つずつ試し要素をyとします。
これでx+y,x-yの二つを満たすx、yの組み合わせが得られました。

ここでf(x)にxでなくyを代入すると
zs=f(y)
とyに対応するzのリストが得られます。
zsの要素はどれもy+z、y-zの両方を満たします。

このzsのリストから要素を取り出しzとします。
この時点でこの(x,y,z)の組は
x+y,x-y,y+z,y-zの4つの条件を満たしていることが判明します。

あとはx+z,x-zが平方数ならこの(x,y,z)の組はすべての条件を満たしているのでx+y+zの値を計算します。
すべての条件を満たす(x,y,z)の組でx+y+zが一番小さくなったものが答えです。

もし答えが見つからなければS1の上限を大きくして再度コードを実行します。

x+y+zが見つかった場合それが最小であるとの確証を得るのも簡単です。
S1の上限n^2を増加させたときS1=n^2で得られるxの最小値x1は
x1=(n^2+1)/2と定義されます。
このx1が見つかっている最小のx+y+zより大きくなればそれ以上S1の上限を増加させてもx1は常にx+y+zの答えより大きくなります。
よってx=(n^2+1)/2が見つかった答えより大きくなればこれ以上は検討する必要がないと判明します。

これは速度はまあまあですがメモリを多量に消費する解法です。
たぶんもっとエレガントな解法はあると思いますのでほかの方の解法も参考にしてください。

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2014年01月06日 16:42