プログラマ専用SNS ミクプラ


https://dixq.net/forum/

コードの間違いを指摘して下さい

https://dixq.net/forum/viewtopic.php?f=3&t=15556

ページ 1 ／ 1

コードの間違いを指摘して下さい

Posted: 2014年8月18日(月) 17:02
by mkt
AOJの問題　http://judge.u-aizu.ac.jp/onlinejudge/d ... d=ITP1_6_D　に関してなのですが、以下のコードでプログラムを提出したのですが、Wrong Answer となってしまいました。コードのどこが間違っているかを教えてください。どうかよろしくお願いします。

コード: 

#include <stdio.h>
  
int main(void)
{
    int n,m,i,j,k,vector_a[100][100],l,o,vector_b[100],vector_c[100];
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++) {
        for(j=0;j<m;j++) {
            scanf("%d ",&k);
            vector_a[i][j] = k;
        }
    }
    for(l=0;l<m;l++) {
        scanf("%d",&o);
        vector_b[l] = o;
    }
    for(i=0;i<n;i++) {
        for(j=0;j<m;j++) {
            vector_c[i] += vector_a[i][j] * vector_b[j];
        }
    printf("%d\n",vector_c[i]);
    }
    return 0;
}

Re: コードの間違いを指摘して下さい

Posted: 2014年8月18日(月) 17:09
by みけCAT
vector_cが初期化されていません。

Re: コードの間違いを指摘して下さい

Posted: 2014年8月18日(月) 17:56
by mkt
vector_cを初期化すると、通りました。みけCAT様、ありがとうございました。

疑問に思ったのですが、何故、vector_aとvector_bは初期化する必要がないのに、vector_cは初期化をする必要があるのでしょうか？
理由を教えて下さい。どうかよろしくお願いします。

Re: コードの間違いを指摘して下さい

Posted: 2014年8月18日(月) 18:28
by みけCAT
mkt さんが書きました:疑問に思ったのですが、何故、vector_aとvector_bは初期化する必要がないのに、vector_cは初期化をする必要があるのでしょうか？
理由を教えて下さい。どうかよろしくお願いします。
vector_aとvector_bは以前の値に関係なく入力データで上書きされるので、初期化する必要がありません。
vector_cはそのようなことが無いため、初期化をする必要があります。

Re: コードの間違いを指摘して下さい

Posted: 2014年8月18日(月) 19:07
by mkt
理由が分かりました。ありがとうございました。

すみません、重ねて質問なのですが、自分の環境だと、vector_cを初期化しなくても、問題なく動きます。自分の使っている環境（mmgames 学習用c言語開発環境）では、初期化をしなくでも宣言をするだけで、配列のすべての要素に０を代入しているのかと思い、調べてみるとそうではありませんでした。何故、自分の環境では、vector_cを初期化しなくても問題なく動いたのでしょうか？理由を教えて下さい。よろしくお願いします。

Re: コードの間違いを指摘して下さい

Posted: 2014年8月18日(月) 19:22
by みけCAT
mkt さんが書きました:何故、自分の環境では、vector_cを初期化しなくても問題なく動いたのでしょうか？理由を教えて下さい。よろしくお願いします。
たまたまかもしれませんが、自分の環境でもEasyIDECを用いて

コード: 

2 2
1 2
3 4
5
6
というテストケースで1回実行すると、正しい出力が得られたので、
もしかしたら自動的に初期化に相当する処理が出力されたのかもしれません。
読み解いてみようと思うので、とりあえずOllyDbgで逆アセンブルした結果を貼っておきます。

【編集】無駄に長いのでspoilに入れました
► スポイラーを表示
【編集】テストケースに誤りがあったので修正

Re: コードの間違いを指摘して下さい

Posted: 2014年8月18日(月) 19:49
by みけCAT
さらに、最後のforループとreturn 0;の部分だけ抜き出し、整形すると、以下のようになりました。

コード: 

; [EBP-4]       n
; [EBP-8]       m
; [EBP-0C]      i
; [EBP-10]      j
; [EBP-9C54]    vector_a
; [EBP-9DEC]    vector_b
; [EBP-9F7C]    vector_c
; [EBP-9F80]    作業用領域

    ; i = 0
    MOV EAX,0
    MOV DWORD PTR SS:[EBP-0C],EAX
OUTER_LOOP_CHECK:

    ; i >= n ならループを抜ける
    MOV EAX,DWORD PTR SS:[EBP-0C]
    MOV ECX,DWORD PTR SS:[EBP-4]
    CMP EAX,ECX
    JGE OUTER_LOOP_END
    JMP OUTER_LOOP_BEGIN
OUTER_LOOP_NEXT:

    ; i = i + 1
    MOV EAX,DWORD PTR SS:[EBP-0C]
    MOV ECX,EAX
    ADD EAX,1
    MOV DWORD PTR SS:[EBP-0C],EAX
    JMP SHORT OUTER_LOOP_CHECK
OUTER_LOOP_BEGIN:

    ; j = 0
    MOV EAX,0
    MOV DWORD PTR SS:[EBP-10],EAX
INNER_LOOP_CHECK:

    ; j >= m ならループを抜ける
    MOV EAX,DWORD PTR SS:[EBP-10]
    MOV ECX,DWORD PTR SS:[EBP-8]
    CMP EAX,ECX
    JGE INNER_LOOP_END
    JMP INNER_LOOP_BEGIN
INNER_LOOP_NEXT:

    ; j = j + 1
    MOV EAX,DWORD PTR SS:[EBP-10]
    MOV ECX,EAX
    ADD EAX,1
    MOV DWORD PTR SS:[EBP-10],EAX
    JMP SHORT INNER_LOOP_CHECK
INNER_LOOP_BEGIN:

    ; ECX = &vector_c[i]
    MOV EAX,DWORD PTR SS:[EBP-0C]
    SHL EAX,2
    LEA ECX,[EBP-9F7C]
    ADD ECX,EAX

    ; EDX = &vector_a[i][j]
    MOV EAX,DWORD PTR SS:[EBP-0C]
    MOV EDX,190
    IMUL EAX,EDX
    LEA EDX,[EBP-9C54]
    ADD EDX,EAX
    MOV EAX,DWORD PTR SS:[EBP-10]
    SHL EAX,2
    ADD EDX,EAX

    ; tmp = ECX
    ; ECX = &vector_b[j]
    MOV EAX,DWORD PTR SS:[EBP-10]
    SHL EAX,2
    MOV DWORD PTR SS:[EBP-9F80],ECX
    LEA ECX,[EBP-9DEC]
    ADD ECX,EAX

    ; EAX = (*EDX) * (*ECX)
    ; すなわち EAX = vector_a[i][j] * vector_b[j]
    MOV EAX,DWORD PTR DS:[EDX]
    MOV EDX,DWORD PTR DS:[ECX]
    IMUL EAX,EDX

    ; ECX = *tmp
    ; すなわち ECX = &vector_c[i]
    MOV ECX,DWORD PTR SS:[EBP-9F80]
    MOV ECX,DWORD PTR DS:[ECX]

    ; *tmp = ECX + EAX
    ; すなわち vector_c[i] = vector_c[i] + vector_a[i][j] * vector_b[j]
    ADD ECX,EAX
    MOV EAX,DWORD PTR SS:[EBP-9F80]
    MOV DWORD PTR DS:[EAX],ECX

    JMP SHORT INNER_LOOP_NEXT
INNER_LOOP_END:

    ; ECX = &vector_c[i]
    MOV EAX,DWORD PTR SS:[EBP-0C]
    SHL EAX,2
    LEA ECX,[EBP-9F7C]
    ADD ECX,EAX

    MOV EAX,DWORD PTR DS:[ECX]
    PUSH EAX
    MOV EAX,OFFSET 0040200D                  ; ASCII "%d"
    PUSH EAX
    CALL <JMP.&msvcrt.printf>                ; Jump to msvcrt.printf
    ADD ESP,8
    JMP OUTER_LOOP_NEXT
OUTER_LOOP_END:
    MOV EAX,0
    JMP LEAVE_POINT
LEAVE_POINT:
    LEAVE
    RETN
【編集】mとnが逆だったので修正

Re: コードの間違いを指摘して下さい

Posted: 2014年8月18日(月) 19:58
by YuO
mkt さんが書きました:すみません、重ねて質問なのですが、自分の環境だと、vector_cを初期化しなくても、問題なく動きます。自分の使っている環境（mmgames 学習用c言語開発環境）では、初期化をしなくでも宣言をするだけで、配列のすべての要素に０を代入しているのかと思い、調べてみるとそうではありませんでした。何故、自分の環境では、vector_cを初期化しなくても問題なく動いたのでしょうか？理由を教えて下さい。よろしくお願いします。
初期化していない自動変数の値は不定であるとされているから。
refs) ISO/IEC 9899:1999 6.7.8 Initialization ¶10
ISO/IEC 9899:1999 さんが書きました:If an object that has automatic storage duration is not initialized explicitly, its value is indeterminate.
不定なので，0でも1でも-1でもよく，処理系は特定の値に設定する必要すらありません。
大抵の環境では自動変数はスタックに取られるので，以前のスタックの値がそのまま残っている可能性が高いでしょう。
そして，main呼び出し時のスタックは使っていないので0で埋まっている可能性もあり，それが今回はたまたま使われただけだと思います。

ちなみに，処理系によっては特定の値に設定する場合もありますが，それに依存したコードを書くのは止めた方がよいでしょう。
オフトピック
例えば，Visual C++のコンパイラは/RTCsコンパイラオプションをつけてコンパイルすると，未初期化変数を0xCCというバイトで埋めます。

Re: コードの間違いを指摘して下さい

Posted: 2014年8月18日(月) 20:28
by みけCAT
前半部分も解読してみましたが、vector_cの初期化に相当するコードはなさそうでした。
ただし、「おまじない」から呼び出されている部分で、OllyDbgの表示がおかしいようなので、ここの解析を行ってみます。

コード: 

; [EBP-4]       n
; [EBP-8]       m
; [EBP-0C]      i
; [EBP-10]      j
; [EBP-14]      k
; [EBP-9C54]    vector_a
; [EBP-9C58]    l
; [EBP-9C5C]    o
; [EBP-9DEC]    vector_b
; [EBP-9F7C]    vector_c
; [EBP-9F80]    作業用領域

    ; おまじない
    MOV EAX,9F80
    CALL 00401280

    ; scanf("%d %d",&n,&m)
    LEA EAX,[EBP-8]
    PUSH EAX
    LEA EAX,[EBP-4]
    PUSH EAX
    MOV EAX,OFFSET 00402000                  ; ASCII "%d %d"
    PUSH EAX
    CALL <JMP.&msvcrt.scanf>                 ; Jump to msvcrt.scanf
    ADD ESP,0C

    ; i = 0
    MOV EAX,0
    MOV DWORD PTR SS:[EBP-0C],EAX
FIST_LOOP_CHECK:

    ; i >= n ならループを抜ける
    MOV EAX,DWORD PTR SS:[EBP-0C]
    MOV ECX,DWORD PTR SS:[EBP-4]
    CMP EAX,ECX
    JGE FIRST_LOOP_END
    JMP FIRST_LOOP_BEGIN
FISRT_LOOP_NEXT:

    ; i = i + 1
    MOV EAX,DWORD PTR SS:[EBP-0C]
    MOV ECX,EAX
    ADD EAX,1
    MOV DWORD PTR SS:[EBP-0C],EAX
    JMP SHORT FIST_LOOP_CHECK
FIRST_LOOP_BEGIN:

    ; j = 0
    MOV EAX,0
    MOV DWORD PTR SS:[EBP-10],EAX
FISRT_INNER_LOOP_CHECK:

    ; j >= m ならループを抜ける
    MOV EAX,DWORD PTR SS:[EBP-10]
    MOV ECX,DWORD PTR SS:[EBP-8]
    CMP EAX,ECX
    JGE FIRST_INNER_LOOP_END
    JMP FIRST_INNER_LOOP_BEGIN
FIRST_INNER_LOOP_NEXT:

    ; j = j + 1
    MOV EAX,DWORD PTR SS:[EBP-10]
    MOV ECX,EAX
    ADD EAX,1
    MOV DWORD PTR SS:[EBP-10],EAX
    JMP SHORT FISRT_INNER_LOOP_CHECK
FIRST_INNER_LOOP_BEGIN;

    ; scanf("%d",&k)
    LEA EAX,[EBP-14]
    PUSH EAX
    MOV EAX,OFFSET 00402006                  ; ASCII "%d "
    PUSH EAX
    CALL <JMP.&msvcrt.scanf>                 ; Jump to msvcrt.scanf
    ADD ESP,8

    ; ECX = &vector_b[i][j]
    MOV EAX,DWORD PTR SS:[EBP-0C]
    MOV ECX,190
    IMUL EAX,ECX
    LEA ECX,[EBP-9C54]
    ADD ECX,EAX
    MOV EAX,DWORD PTR SS:[EBP-10]
    SHL EAX,2
    ADD ECX,EAX

    ; *ECX = k
    MOV EAX,DWORD PTR SS:[EBP-14]
    MOV DWORD PTR DS:[ECX],EAX

    JMP SHORT FIRST_INNER_LOOP_NEXT
FIRST_INNER_LOOP_END:
    JMP SHORT FISRT_LOOP_NEXT
FIRST_LOOP_END:

    ; l = 0
    MOV EAX,0
    MOV DWORD PTR SS:[EBP-9C58],EAX
SECOND_LOOP_CHECK:

    ; l >= m ならループを抜ける
    MOV EAX,DWORD PTR SS:[EBP-9C58]
    MOV ECX,DWORD PTR SS:[EBP-8]
    CMP EAX,ECX
    JGE SECOND_LOOP_END
    JMP SECOND_LOOP_BEGIN
SECOND_LOOP_NEXT:

    ; l = l + 1
    MOV EAX,DWORD PTR SS:[EBP-9C58]
    MOV ECX,EAX
    ADD EAX,1
    MOV DWORD PTR SS:[EBP-9C58],EAX
    JMP SHORT SECOND_LOOP_CHECK
SECOND_LOOP_BEGIN:

    ; scanf("%d",&o)
    LEA EAX,[EBP-9C5C]
    PUSH EAX
    MOV EAX,OFFSET 0040200A                  ; ASCII "%d"
    PUSH EAX
    CALL <JMP.&msvcrt.scanf>                 ; Jump to msvcrt.scanf
    ADD ESP,8

    ; ECX = &vector_b[l]
    MOV EAX,DWORD PTR SS:[EBP-9C58]
    SHL EAX,2
    LEA ECX,[EBP-9DEC]
    ADD ECX,EAX

    ; *ECX = o
    MOV EAX,DWORD PTR SS:[EBP-9C5C]
    MOV DWORD PTR DS:[ECX],EAX
    JMP SHORT SECOND_LOOP_NEXT
SECOND_LOOP_END:

Re: コードの間違いを指摘して下さい

Posted: 2014年8月18日(月) 20:43
by みけCAT
「おまじない」の部分はスタック上にローカル変数用の領域を確保するルーチンを呼び出しており、
初期化に相当するコードは無さそうでした。

コード: 

   0:	87 2c 24             	xchg   %ebp,(%esp)
   3:	55                   	push   %ebp
   4:	8d 6c 24 04          	lea    0x4(%esp),%ebp
   8:	51                   	push   %ecx
   9:	89 e9                	mov    %ebp,%ecx
   b:	81 e9 00 10 00 00    	sub    $0x1000,%ecx
  11:	85 01                	test   %eax,(%ecx)
  13:	2d 00 10 00 00       	sub    $0x1000,%eax
  18:	3d 00 10 00 00       	cmp    $0x1000,%eax
  1d:	7d ec                	jge    0xb
  1f:	29 c1                	sub    %eax,%ecx
  21:	89 e0                	mov    %esp,%eax
  23:	85 01                	test   %eax,(%ecx)
  25:	89 cc                	mov    %ecx,%esp
  27:	8b 08                	mov    (%eax),%ecx
  29:	8b 40 04             	mov    0x4(%eax),%eax
  2c:	50                   	push   %eax
  2d:	c3                   	ret

Re: コードの間違いを指摘して下さい

Posted: 2014年8月18日(月) 21:00
by mkt
みけCAT様
vector_cは自動では初期化されていないということがよく分かりました。繰り返し、質問に答えていただきありがとうございました。

YuO様
自分の環境ではvector_cを初期化しなくても、プログラムが問題なく動いた理由がよく分かりました。ありがとうございました。
All times are UTC+09:00
ページ 1 ／ 1
Powered by phpBB® Forum Software © phpBB Limited
https://www.phpbb.com/