人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

線形代数、もしくは数論に関する質問です。
ポイントを付けての再投稿で失礼します。

【問題】
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年かかるといわれても困ってしまいますので、
だいたい何日とか何年とか、ざっくりとしたお答えを
いただければと思います。

1441151454
●拡大する

●質問者: チョコ
●カテゴリ:学習・教育 科学・統計資料
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

質問者から

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


1 ● ita
●300ポイント ベストアンサー

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);
 }}}}
}

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

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ