質問: ( 12, 20, 25, 32), ( 20, 25, 32, 37), ( 12, 25, 32, 37), ( 12, 20, 32, 37), ( 12, 20, 25, 37) で、ほかに挙がっていた解として (1, 3, 9, 27)とか(1, 3, 13, 21)なんかがあるらしい、 というところまではわかったのですが、 網羅的に解を求める方法がわかりません。 お教えいただきたくお願いします。 P.S. 補足で計算時間について触れましたが、 要するに実現可能な時間かどうかが知りたかったので 追加しました。 100年かかるといわれても困ってしまいますので、 だいたい何日とか何年とか、ざっくりとしたお答えを いただければと思います。
回答: 10分ほどでCのコード書いて走らせたら0.1秒以内で終わりました。 入れ替えの重複を除いてX1<=X2<~X3<=X4 とすると計算量は 40^3/24 * 3^4程度です。アルゴリズムは特に難しいことはしていません。 約7000通りの解があります。 ``` #include #include int target[5]={12,20,25,32,27}; int main(int argc, char **argv) { int x1,x2,x3,x4; for(x1=1;x1<=40;x1++) { for(x2=x1;x2<=40;x2++) { for(x3=x2;x3<=40;x3++) { for(x4=x3;x4<=40;x4++) { int flag[5]={0,0,0,0,0}; int a1,a2,a3,a4; for(a1=-1;a1<=1;a1++){ for(a2=-1;a2<=1;a2++){ for(a3=-1;a3<=1;a3++){ for(a4=-1;a4<=1;a4++){ int sum=x1*a1+x2*a2+x3*a3+x4*a4; int t; for(t=0;t<5;t++)if(sum==target[t])flag[t]=1; }}}} int sum=0; int t; for(t=0;t<5;t++)sum+=flag[t]; if(sum==5)printf("%d %d %d %d\n",x1,x2,x3,x4); }}}} } ```