「prolog勉強プロジェクトオイラー321~330」の編集履歴(バックアップ)一覧に戻る

prolog勉強プロジェクトオイラー321~330 - (2014/01/07 (火) 02:06:41) のソース

プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ。


*Problem 321 「カウンタの交換」 †
チェッカーの駒を入れ替えるパズルを題材にとった数学の問題。
問題の詳細はリンク先参照のこと。
http://odz.sakura.ne.jp/projecteuler/index.php?Problem%20321

***解放 只今考え中。
30分ほど紙の上で色々試行錯誤した結果。
最小入れ替え回数はたぶん青のチェッカーの枚数をn枚として。
n^2+2nで最小入れ替え回数が与えられこれが三角数なので適当な自然数mをとって。
n^2+2n=m*(m+1)/2
を満たす自然数n、mの組となる。
整理すると
7/4=2(n+1)^2-(m+1/2)^2
という2次曲線上の整数解の組を小さいものから求めよという問題となる。
パズルに見せかけて実態は難しい数学の問題だということです。

----
Yahoo知恵袋のtiansunjianglinさんというかたは
この問題を効率的に解くということを目的にするなら
8(n+1)^2-7=(2m+1)^2
と変形して、ある整数に1を足して2乗し、8倍してから7を引く。
これが平方数なら、Trueということで条件に合う整数を見つければいいと思います。
と返答を頂きました。

論外な意見でして、私の乏しい数学知識によればこの問題ディオファントス方程式を解く必要があるはずです。
条件を満たすnはどんどん間隔が大きくなりますので小さいほうから試すと相当長時間計算しないと答えが出てきません、nの数列の増加率から考えて数日は計算する必要があるかもしれないので論外です。
補足
tiansunjianglinさんからディオファントス方程式の生成方法を教えてもらう。
この分野について教育を受けたことがないので読解に苦労しているが何とかなりそう。
----