質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.21%

c言語 for の無限ループ回避の理由

受付中

回答 4

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,590
退会済みユーザー

退会済みユーザー

コード同士のどの部分が影響を及ぼすのか理解できず困っています。
こちらの(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp)を問題に対して以下のように解答しました。
コードとしては一方の配列に含まれる値をもう一つの配列から二分探索を行うものなのですが、途中でforの無限ループが発生してしまいます。
以下コードになります。

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

int binary(int a[],int left,int right,int x){
    int middle=(left+right)/2;
    if(x==a[middle]) return 1;

    while(left != right) {
        if(x<a[middle])binary(a, left, middle,x);

        if(x>a[middle])binary(a, middle+1,right,x);
    }
    return -1;
}

int main(){
int i, j,n,m;

scanf("%d",&n);
printf("%d",n);
int s[n];
for(i=0;i<n;i++){
    scanf("%d",&s[i]);
    printf("Ok");
}

scanf("%d",&m);
printf("%d",m);
int t[m];
for(i=0;i<m;i++){
    scanf("%d",&t[i]);
    printf("Ok");
}
printf("読み込み終わり");
int x,ans,count;
count=0;
for (i = 0; i < m;i++) {
    x=t[i];
    ans=binary(s,0,n,x);
    if(ans==1)count++;
    }
printf("%d",count);
    return 1;
}


具体的にはコンパイル時に2つ目のfor scanf

for(i=0;i<m;i++){
    scanf("%d",&t[i]);
    printf("Ok");
}


で無限ループをしました。
そこでコードを触ってみたところ、
「printf("読み込み終わり");」を以下を消した場合だと何故か

for(i=0;i<m;i++){
    scanf("%d",&t[i]);
    printf("Ok");
}


の先程のループがとまり、「printf("読み込み終わり");」に到達したあとプログラムが終了します。
この理由がわかりません。

削除後のコードは以下になります。

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

int binary(int a[],int left,int right,int x){
    int middle=(left+right)/2;
    if(x==a[middle]) return 1;

    while(left != right) {
        if(x<a[middle])binary(a, left, middle,x);

        if(x>a[middle])binary(a, middle+1,right,x);
    }
    return -1;
}

int main(){
int i, j,n,m;

scanf("%d",&n);
printf("%d",n);
int s[n];
for(i=0;i<n;i++){
    scanf("%d",&s[i]);
    printf("Ok");
}

scanf("%d",&m);
printf("%d",m);
int t[m];
for(i=0;i<m;i++){
    scanf("%d",&t[i]);
    printf("Ok");
}
printf("読み込み終わり");
    return 1;
}

その後デバッグツールを使い、変数の確認等を行いましたが、
x>hit を満たしているのにもかかわらず再帰せずreturn -1に到達してしまいます。
x=4,hit=3である以上
if(x >  hit){binary(a, middle+1,right,x);}
で再帰すると思うのですがなぜか再帰しません。(イメージ説明
画像のように13行目で再帰せずに14行目に抜けてしまいます。
これはなぜなのでしょうか?

今現在のコードは以下のようになります。

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

/* 二分探索 xは探したい値 */
int binary(int a[],int left,int right,int x){
    int middle=(left+right)/2;
    if(x==a[middle]) return 1;

    if(left<right){
        int hit=a[middle];
        if(hit > x){binary(a, left, middle, x);}

        if(x >  hit){binary(a, middle+1,right,x);}
      }
    return -1;
}

int main(){
int i,n,m;

scanf("%d",&n);
int s[n];
for(i=0;i<n;i++){
    scanf("%d",&s[i]);

    /* 配列sの作成 */

}

scanf("%d",&m);
int t[m];
for(i=0;i<m;i++){
    scanf("%d",&t[i]);

/* 配列tの作成 */
}

int x,ans,count;
count=0;/* 見つかった回数カウント */
for (i = 0; i < m;i++) {
    x=t[i];
    ans=binary(s,0,n-1,x);
    if(ans==1)count++;
    }
    printf("%d",count);
    return 1;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • pepperleaf

    2019/01/08 22:44

    初回、binary()に入ったところから、ステップ実行した結果でしょうか?
    (1/8 のコードで、、、)
    続いて、ステップ実行続けても同様でしょうか?
    時折、デバッガはウソつくことがあるので注意が必要。(最適化等の問題)

    キャンセル

  • 退会済みユーザー

    退会済みユーザー

    2019/01/09 13:54

    正確に説明するとi=0のときは
    if(left<right)に到達せずにそのままreturnとなります
    i=1のときにそのような現状が起きます

    実行は最初から実行し、ブレークポイントを置いた形です

    キャンセル

  • pepperleaf

    2019/01/09 22:22

    このデバッガ使った事が無いので、見方が分かりませんが、赤●がブレークポイント? で、再帰の判定はどうしてるのでしょうか?
    データが不明なので、正確には分かりませんが、再帰はしていて、
    > if(x==a[middle]) return 1;
    ここで戻ってるって事はありませんか? 上記、書き忘れましたが、ステップ実行の場合、関数内の処理では、ブレークポイントが無いと止まりません。 確認するならば、関数の先頭にブレークポイントが必要です。 (または、ステップインの設定)

    キャンセル

  • pepperleaf

    2019/01/11 22:55

    あ、書き忘れましたが、 binary()関数、main()から、呼ばれ、最初に
    > if(x==a[middle])
    が成立すれば、1 を返しますが、それ以外は全て、-1 となります。なぜなら、binary()を再帰で呼んでいますが、その戻り値は常に無視され、最後の
    > return -1;
    となります。 この辺の理解は間違い無いでしょうか?

    キャンセル

回答 4

+3

こんにちは。

具体的にはコンパイル時に2つ目のfor scanf(中略)で無限ループをしました。

この判断ミスだろうと思います。
printf()の出力はキャッシュされますので、キャッシュをフラッシュする、ある程度出力が貯まる、プログラムが正常終了する等の事象が発生するまで出力されません。なので、無限ループや落ちた時に単純なprintfですとその場所を見誤ることが多いです。
各printfの後ろにfflush(stdout);をおいてみて下さい。printfの後キャッシュを直ぐにフラッシュするので直ぐに出力されるようになります。

ざっと見る限り無限ループを回っているのは binary関数の可能性が高そうです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/01/03 00:34

    皆様の意見にbinary の方にループがあるのと、printfは到達時にすぐ出力されてることを知っておらず、binaryの部分で修正を試みることに致しました。

    キャンセル

  • 2019/01/03 09:56

    あ、気が付かなかったですが、printf()の出力に "\n" が無い。
    ほぼ、確実にキャッシュされますね。(仕様かどうかは知りませんが、、、)
    printf("%d\n", n) とかするだけで、出力されると思います。

    キャンセル

+1

EclipseやVisualStudioを入れると、Cのコードで任意の場所で止めて、変数の内容を確認したり、ワンステップづつ実行させてどういう動作をするか確認できるようになります。
こういうので自分のコードの動作を確認なされてはどうでしょう
あてずっぽでコードを書かなくて済むようになります

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/01/03 00:35

    macの都合上、visual studioが使えずCLionというIDEを使っていたのですがEclipse検討してみます(ワンステップずつ実行できる機能の存在を存じておりませんでした。)

    キャンセル

  • 2019/01/03 00:43

    Cでコードを組む場合、そういうデバッガ無しでコードを組むのは無謀と言っていいと思います
    C言語というのは、コードにエラーがあっても、止まらない、おかしな動作をする、場合によっては正常に動いているような動作をする、というモノなので、推測や当てずっぽでは、初心者が正しいコードを組むのは至難の業となります

    #Pythonなどでは、おかしなコードでは確実に止まってくれます

    キャンセル

  • 2019/01/03 01:59 編集

    (CLionはとてもいいIDEですよ!!ステップ実行もできるはずです!!
    参考→https://pleiades.io/help/clion/debugging-code.html

    キャンセル

  • 2019/01/07 18:58

    alphyaさん

    Clionのデバッグツールを導入し、使わせて頂いています!
    ありがとうございます

    キャンセル

0

詳しく見ておりませんが、現象からして未定義状態になっている可能性があります。これは、C言語の仕様外の状態のことであり、再現性のないバグとして表面化するパターンが多いです。

ループの中でn,m,i,s[i],t[i]の値の経過を見てみるといいと思いますよ。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/01/03 00:24

    とりあえず、バイナリサーチ関数の再帰呼び出しの部分はおかしいですね。whileループと再帰を併用している上に、戻り値伝搬がないです。

    キャンセル

0

    while(left != right) {
        if(x<a[middle])binary(a, left, middle,x);

        if(x>a[middle])binary(a, middle+1,right,x);
    }


この部分で無限ループ発生しませんか?
while ループ内で、left, right が更新されていません。
もしかしたら、

if () return binary();

の間違い?

無限ループ箇所の確認はどのように行ったのでしょう。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/01/03 00:38

    Chironianさんのコメントにもつながるのですが、printfの出力タイミンでループの確認を行っていました(今回だとokや読み込み終わりの出力)
    whileループは他の方のコメントにもありますように今修正を試みています。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.21%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る