1441151454 線形代数、もしくは数論に関する質問です。

ポイントを付けての再投稿で失礼します。

【問題】
x_1~x_4は、0 < x_1, x_2, x_3, x_4 ≦ 40を満たす自然数。
a_ij はそれぞれ、-1, 0, 1のどれかの値をとる整数。
このとき図の式を満たすxの組をすべて求めよ。

とりあえずこれを満たすごく簡単な解は
(x_1, x_2, x_3, x_4)
= ( 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年かかるといわれても困ってしまいますので、
だいたい何日とか何年とか、ざっくりとしたお答えを
いただければと思います。

回答の条件
  • 1人10回まで
  • 13歳以上
  • 登録:2015/09/02 08:50:54
  • 終了:2015/09/02 21:51:50
id:bitter_sweet_chocolate

コンピュータの数値計算で力ずくで解くのがよいのかもしれませんが、単純に総当たりで考えると40^4*3^(5*4)で約9000兆個の組合せがあります。コンピュータが最適とおっしゃるときはこれを解くのにどのくらい時間がかかるのか、合わせて教えていただけると非常にありがたいです。

ベストアンサー

id:ita No.1

ita回答回数203ベストアンサー獲得回数472015/09/02 21:18:44

ポイント300pt

10分ほどでCのコード書いて走らせたら0.1秒以内で終わりました。
入れ替えの重複を除いてX1<=X2<~X3<=X4 とすると計算量は
40^3/24 * 3^4程度です。アルゴリズムは特に難しいことはしていません。
約7000通りの解があります。

#include <stdio.h>
#include <stdlib.h>

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);
    }}}}
}
id:bitter_sweet_chocolate

ご回答ありがとうございます。
簡潔で素直で正攻法のコードですね。
まさか秒殺未満とは思いませんでした。考えるより実行してみるべきでした。
7000通りもあるのでは人力ではちょっと無理ですね。
重ねてありがとうございました。

2015/09/02 21:59:43

その他の回答(0件)

id:bitter_sweet_chocolate

質問文を編集しました。詳細はこちら

id:ita No.1

ita回答回数203ベストアンサー獲得回数472015/09/02 21:18:44ここでベストアンサー

ポイント300pt

10分ほどでCのコード書いて走らせたら0.1秒以内で終わりました。
入れ替えの重複を除いてX1<=X2<~X3<=X4 とすると計算量は
40^3/24 * 3^4程度です。アルゴリズムは特に難しいことはしていません。
約7000通りの解があります。

#include <stdio.h>
#include <stdlib.h>

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);
    }}}}
}
id:bitter_sweet_chocolate

ご回答ありがとうございます。
簡潔で素直で正攻法のコードですね。
まさか秒殺未満とは思いませんでした。考えるより実行してみるべきでした。
7000通りもあるのでは人力ではちょっと無理ですね。
重ねてありがとうございました。

2015/09/02 21:59:43

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません