行列の積のプログラム

n次正方行列X=(xij),Y=(yij)の積XYの(i,j)成分はΣ(k=1,n)xikykjで定義する。これをmin{k∈1,2,…n}(xik+ykj)と変更したとき行列の積を計算するプログラムの作成をしたいです。

※minXは、Xの中の最小値を意味する。

十進BASICで解きたいのですが、以下のプログラムで間違いがあったら指摘してただけないでしょうか？よろしくお願いします。

INPUT N
DIM X(n,n)
DIM Y(n,n)
DIM Z(n,n)
INPUT X(n,n)
INPUT Y(n,n)
FOR i = 1 TO n
　FOR j = 1 TO n
　　LET Z(i,j) = X(i,1) * Y(1,j)
　　　FOR k = 2 TO n
　　　　IF Z(i,j) > X(i,k) * Y(k,j) THEN LET Z(i,j) = X(i,k) * Y(k,j)
　　NEXT k
　NEXT j
NEXT i
INPUT Z(n,n)
END

No.1 回答者： fronteye 回答日時： 2008/03/16 10:02

minXの定義がいまいちわからないので、プログラムの内容ではなく文法へのアドバイスをします。

十進BASICでは、配列へ数値を入力するのはMAT INPUT文を使います。
n=2ならば、5,4,9,3のように配列の要素分の数値をカンマで区切って入力します。
最後のINPUT Z(n,n)は出力だと思います。
MAT PRINT文を使います。

INPUT N
DIM X(n,n)
DIM Y(n,n)
DIM Z(n,n)
MAT INPUT X
MAT INPUT Y
FOR i = 1 TO n
FOR j = 1 TO n
LET Z(i,j) = X(i,1) * Y(1,j)
FOR k = 2 TO n
IF Z(i,j) > X(i,k) * Y(k,j) THEN LET Z(i,j) = X(i,k) * Y(k,j)
NEXT k
NEXT j
NEXT i
MAT PRINT Z
END

No.2 ベストアンサー 回答者： cametan_42 回答日時： 2008/03/16 17:28

これ前やったなあ。

僕の場合はScheme(Lispの一方言)で書いたんですけど、恐らくBASICで書く以上、「殺人的な長さ」になると思います。
まあ、僕はBASICは良く知らんので、入出力関係ですと、ANo.1さんの方を参照して欲しいんですが、一応ロジックで気づいた事を挙げていきます。

9行目:
LET Z(i,j) = X(i,1) * Y(1,j)

そもそもここが違います。
題意では、

min{k∈1,2,…n}(xik+ykj)

でないとならないので、そもそも掛け算を用いません。
また、配列Zのi行j番目にいきなり計算結果を代入するのも間違っています。

題意的には、例えば4行4列の計算結果、Z_{1,1}に当たる数値の候補は

Z_{1,1}=min{x_{1,1}＋y_{1,1},x_{1,2}＋y_{2,1},x_{3,1}＋y_{1,3},x_{1,4}＋y_{4,1}}

の4つあって、この4つの中から「最小の値」をZ_{1,1}として返さないといけません。つまり、この作業をn行n列の行列Zに対して「全て」やらないとならないのです。

もうちょっと具体的に見てみましょうか?
例えば4行4列の行列Xが、十進BASICの記法を真似ると、

MAT X = 1,0,2,0,0,1,0,2,2,0,1,0,0,2,0,1

で、同様に4行4列の行列Yが、

MAT Y = 16,3,2,3,5,10,11,8,9,6,7,12,4,15,14,1

だった場合、出力結果の行列Zは

MAT Z = 4,4,3,1,6,3,2,3,4,5,4,1,5,3,2,2

でないとなりません。
何故なら先ほどの定義により、例えばZ_{1,1}は

Z_{1,1}＝min{1+16, 0+5 , 2+9 , 0+4}

となり(MAT Yの要素を4つづつに分けて、その先頭要素が計算に使われていることに注意!)「その中の最小値」の4がZ_{1,1}の計算結果として出力されます。
どのXの要素とどのYの要素が計算に使われるのか、は普通の「行列の積」に従ってるんですけど、この問題の場合、根本的にn行n列同士の計算を行うと、各要素に対してなおかつ「n個の要素から」最小値を返す、ってのが題意です。
従って、例示したプログラムにはその計算過程が組み込まれていないように見受けられます。
根本的なロジックを見直した方が良いでしょうね。

この回答へのお礼

詳しい解説ありがとうございます。
とても勉強になりました！

お礼日時：2008/03/17 22:01

No.3 回答者： fronteye 回答日時： 2008/03/16 20:23

No.1です。

No.2さんの回答でmin{k∈1,2,…n}(xik+ykj)の意味がわかりました。

それならば簡単なことです。
FOR～NEXT内の乗算(*)を加算(+)に変えるだけです。

No.2さんの提示した例を入力しましたが、正しい結果が出力されましたよ。

この回答へのお礼

回答ありがとうございます、補足までしていただき本当に感謝です。
もっとプログラミングの勉強頑張りたいと思います。

お礼日時：2008/03/17 22:05