• ベストアンサー

線形探索（番兵法）のプログラムについて。

線形探索（番兵法）のプログラムについて考えています。 メイン関数からsearch関数に値を渡してそこで探索させるのですが、 int search(int a[], int n, int key) { int i = 0; a[n] = key; while (1) { if (a[i] == key) break; i++; } return (i == n ? -1 : i); } のwhileを使ったやり方からfor文を使ったやり方に変更したいと思っています。 色々な方法でプログラムを考えてみたいので。 そうすると、なんかうまくいきません。 for文だとどのように考えたらいいのでしょうか？

質問者が選んだベストアンサー

  • ベストアンサー
  • hofuhofu
  • ベストアンサー率70% (336/476)
回答No.4

番兵法の意義からすると冗長な表現を省いた#2の方法もそう悪くはないと思いますが、ソースの見やすさを考えると、私ならwhileを使って、 while(a[i]!=key) i++; とします。 これは、 for(;a[i]!=key;i++); と同義ですが、whileのほうが直感的に理解しやすいかと思います(慣れれば大して変わらないですが)。 多分動作速度もあまり変わらないでしょう。 #2ぐらいの変則的な使い方ならどうということは無いですが、中にはアルゴリズムを理解するのに「解読」が必要なほど難解な表現が使われることがあります(C/C++プログラマに多いような)。 そうしたほうがソースが短くて済んだり、動作が速かったりするのですが、あまり多用するとわけのわからない代物になります。 ここの#6さんの回答とかは面白いです。 http://oshiete1.goo.ne.jp/kotaeru.php3?q=653025 初歩のforの使い方(規定回数ループさせるだけ)で番兵法は多分無理だと思います。 どうしてもループの継続条件と検索のためのif文で計2回の比較が入りますから、逐次検索と変わらなくなってしまいます。 多分ここでつまづかれていたんでしょうけど。

その他の回答 (3)

  • tatsu99
  • ベストアンサー率52% (391/751)
回答No.3

No1です。 >for(i=0;;i++)の終了条件は書かなくてもいいのでしょうか？ >こういう書き方をはじめてみました。 かまいません。No2のかたも言ってますが、 for(;;)とwhile(1)は同じ動作です。 forに関する説明文を注意深く読んでみて下さい。 話は変わりますが、今回の解の方法としては、 for(i=0;i<n;i++){ if (a[i]==key) return i; } return -1; が最も素直な解でしょう。

  • hofuhofu
  • ベストアンサー率70% (336/476)
回答No.2

もっと簡略化して for(i=0;a[i]!=key;i++); 最後のセミコロンを忘れずに。 ちなみに、 while (1) はそのまま、 for(;;) と置き換えても、同じ動作をします。 継続条件を書かないのは、無限ループさせたいときによく使われる手法です。 http://www.kusa.ac.jp/~kajiura/c/kurikaeshi/newpage21.htm#無限ループ

  • tatsu99
  • ベストアンサー率52% (391/751)
回答No.1

for (i=0;;i++){ if (a[i]==key) break; } でどうですか？

usui323
質問者

お礼

回答ありがとうございます。 for(i=0;;i++)の終了条件は書かなくてもいいのでしょうか？ こういう書き方をはじめてみました。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • 線形探索について

    C言語の線形探索の課題なんですが ５つの整数を入力して その入力した値からみつけたい値を探索する課題なのですが #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を線形探索 ---*/ int search(const int a[], int n, int key) { int i = 0; while (1) { if (i == n) return (-1); /* 探索失敗 */ if (a[i] == key) return (i); /* 探索成功 */ i++; } } int main(void) { int i, ky, idx; int x[4]; int nx = sizeof(x) / sizeof(x[0]); printf("%d個の整数を入力してください。\n", nx); for (i = 0; i < nx; i++) { printf("x[%d]：", i); scanf("%d", &x[i]); } printf("探す値："); scanf("%d", &ky); idx = search(x, nx, ky); /* 配列xから値がkyである要素を線形探索 */ if (idx == -1) puts("探索に失敗しました。"); else printf("%dは%d番目にあります。\n", ky, idx + 1); return (0); } ここまではわかるのですが、 x[0]=99 x[1]=99 x[2]=88 x[3]=99 x[4]=22 と入力したときに 99は 1番目に見つかりました ２番目に見つかりました ４番目に見つかりました と出力したいのですがうまくいきません 線形探索で同じ数値を探索するにはどうすればよいのですか？

  • 線形探索と二分探索

    線形探索と二分探索のプログラムを作成中です。 自力(本やwebに落ちているサンプルを参考にして)でここまで作りましたが正直自信がありません。どうかお願いします。 #include <stdio.h> #define ARRAYI1_MAX sizeof(array1) #define ARRAYI2_MAX sizeof(array2) //int binary_search(int*,int,int); //二分探索関数のプロトタイプ宣言 int liner_search(int*,int,int); //線形探索関数のプロトタイプ宣言 void main(void) { int array1[]={2,3,5,8,12,20,32,52}; int array2[]={22,34,65,66,12,33,43,5,1}; int result,key; printf("探す文字を入力して下さい。\n"); sacnf("%d",&key); result=liner_search(array1,ARRAYI1_MAX,key); if(result<0){ printf("見つかりませんでした\n");} else{ printf("%d番目に見つかりました\n",result);} } //線形探索 int liner_search(int*array,int num_array,int key) { int i=0; for(i=0;i<result;i++) } /*二分探索 int binary_search(int*array,int num_array,int key) { }*/

  • このプログラムの説明合っていますか?

    /* 線形探索（for文で実現）*/ #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を線形探索 ---*/ int search(const int a[], int n, int key)　　　 { int i;　　　　　　　　　　　　/*iを宣言*/ for (i = 0; i < n; i++)　　　　　/*iの値を設定し宣言*/ if (a[i] == key)　　　　　　　/*iにkeyで入力*/ return (i); /* 探索成功 */ return (-1); /* 探索失敗 */ } int main(void)　　　　　　　　　　/*main関数*/ { int i, ky, idx;/*i,ky,idxを宣言*/ int x[7];　/*ｘは配列で７つの数字を入れられる*/ int nx = sizeof(x) / sizeof(x[0]);/*配列を宣言*/ printf("%d個の整数を入力してください。\n", nx); for (i = 0; i < nx; i++) { printf("x[%d]：", i); scanf("%d", &x[i]); }printf("探す値："); scanf("%d", &ky); idx = search(x, nx, ky); /* 配列xから値がkyである要素を線形探索 */ if (idx == -1) puts("探索に失敗しました。"); else printf("%dは%d番目にあります。\n", ky, idx + 1); return (0);　　　　　　/*0の数字で戻る*/ } 1行ずつ理解したいのですが分からない個所多いんです。 分からないの文は説明が書いてないので教えてください。

  • このプログラムどこがおかしいですか？

    コンパイルはできますが実行できません… どこがおかしいか分かる人教えてください。 このプログラムはファイルから名前　数学の点数、英語の点数を読み込んで文字データに入れた後構造体に入れて探し出す値の項目（キー）を入力して（何番目にあるか）探し出すというプログラムです。 #include <stdio.h> #include <string.h> #define NUMBER 10 //構造体を宣言する struct student { //名前、身長、体重を構造体オブジェクトのメンバに格納する関数の定義 char name[10]; char math[4]; char eng[4]; }; /*--- 要素数nの配列aからkeyと一致する要素を線形探索（番兵法） ---*/ int search(struct student *b, int n, char key) { int i=0; b[i].name[0]=key; // 番兵を追加 while (1) { if (b[i].name[0] == key) break; /* 見つけた */ i++; } return (i == n ? -1 : i); } int main(void) { FILE *fpin; struct student a[NUMBER]; int i=0, idx,ret; char buffer[20],ky; int nx=sizeof(buffer) / sizeof(buffer[0]); fpin=fopen("input2.txt","r"); //テキストファイルを読み取りモードで開く while(fgets(&buffer[0],sizeof(buffer),fpin) !=NULL ) { if(i>=100) break;//読み込む人数が100人を超えてる時の処理 ret=sscanf(&buffer[0],"%s %s %s",&a[i].name,&a[i].math,&a[i].eng); //データ文字列を3分割 if(ret!=3) //3に分割できなかったときの処理 { puts("代入された入力項目の個数が3でありません"); goto END; } printf("%s %s %s\n",&a[i].name,&a[i].math,&a[i].eng); i++; } printf("探す値："); scanf("%s", &ky); idx = search(a, nx - 1, ky); /* 配列xから値がkyである要素を線形探索 */ if (idx == -1) puts("探索に失敗しました。"); else printf("%dは%d番目にあります。\n", ky, idx + 1); END: fclose(fpin); return 0; }

  • 線形探索のエラーがでて困っています

    線形探索を用いて表を作るプログラムを作ったのですが、データの数が１００００ならば作動するのですが、それ以上になってしまうとセグメントエラーが起こります。なぜだが教えていただけないでしょうか？ #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 1000000 #define M 10 typedef int Key; typedef struct item{ Key key; }Item; struct table { int n; Item item[N]; }; typedef struct table *Table; Item *lookup_item(Table table ,Key key){ int i=0; while(1){ if(i==table->n) return (0); if(table->item[i].key==key) return &(table->item[i]); i++; } return 0; } int add_item(Table table, Item item){ int i; int n=table->n; if(lookup_item(table ,item.key)!=0) return (0); else { table->item[n].key=item.key; table->n++; return (1); } } Table new_table(){ Table table; table = (Table)malloc(sizeof(table)); return table; } int remove_item(Table table, Key key){ int i=0; int n=table->n; if(lookup_item(table,key)!=0) { while(1){ if(table->item[i].key==key){ table->item[i].key=table->item[n-1].key; table->n--; return 1; } i++; } } else return (0); } Key keys[N]; int main() { Table table; Item item; clock_t t1, t2; char buff[128]; int i, j, n; /* ファイルからキーを読み込み keys[] に格納する。*/ for (n=0; n<N && fgets(buff, 128, stdin)!=NULL; n++) { keys[n] = atoi(buff); } /* 表を用意する。*/ table = new_table(); /* 追加項目数と全項目の追加に必要な時間(秒単位)を印字する。*/ t1 = clock(); for (i=j=0; i<n; i++) { item.key = keys[i]; j += add_item(table, item); } t2 = clock(); printf("%d %.3f\n", j, (double)(t2-t1)/CLOCKS_PER_SEC); /* 探索成功数と全項目の探索に必要な時間(秒単位)を印字する。*/ t1 = clock(); for (i=j=0; i<n; i++) { if (lookup_item(table, keys[i])!=NULL) j++; } t2 = clock(); printf("%d %.3f\n", j, (double)(t2-t1)/CLOCKS_PER_SEC); /* 削除項目数と全項目の削除に必要な時間(秒単位)を印字する。*/ t1 = clock(); for (i=j=0; i<n; i++) { j += remove_item(table, keys[i]); } t2 = clock(); printf("%d %.3f\n", j, (double)(t2-t1)/CLOCKS_PER_SEC); return 0; } よろしくお願いします。

  • 線形探索法のプログラムについて

    配列Aに格納されている数字を検索するプログラムより、 Aのプログラムでは配列Aに格納されている数字を検索(scanf("%d" , j)で入力)した にもかかわらず、「該当するデータがありませんでした」と表示されてしまいます。 Bのプログラムでは、配列Bに格納されている数字を検索(scanf("%d" , j)で入力)すると 「該当するデータがありました」と表示されます。 Aのプログラムで、------でかこってある部分に問題があると思われ、 いろいろと試してみましたが、未だにその理由をつかむことができません。 その理由を知りたく、書き込みを致しました。 ご教授の程宜しくお願い致します。 A. main(){ int i , j; int k = 0; int A[5] = {4 , 1 , 3 , 4 , 5}; printf("検索する数値を入力してください > "); scanf("%d" , j); --------------------------------------------------------------- for(i=0 ; i<5 ; i++){ if(A[i] == j){ printf("該当するデータはあります"); k++; } } --------------------------------------------------------------- if(k <= 0){ printf("該当するデータがありませんでした\n"); } return; } B #include<stdio.h> main(){ int i , j , k; int A[5] = {4 , 1 , 3 , 4 , 5}; printf("検索する数値を入力してください > "); scanf("%d" , j); for(i=0 ; i<5 ; i++){ if(A[i] == j){ k++; } } if(k>0){ printf("該当するデータはありました"); }else{ printf("該当するデータはありませんでした"); } return; }

  • C言語の二分探索法について質問です。

    C言語の２分探索法について質問です。 以下のようなプログラムを作りたいのですが，途中でよく分からなくなってしまいました。添削お願いします。 入力された整数を配列に順次格納する(必ず昇順になるように入力)。0が入力された時に整数の入力を終了し， 次に入力された数字を二分探索によって配列から探索し，その配列の添字番号を出力するプログラムを作成せよ。 実行例 (例1) (例2) 9 ←入力 1 ←入力 7 ←入力 42 ←入力 69 ←入力 99 ←入力 31 ←入力 13 ←入力 93 ←入力 0 ←入力 59 ←入力 5 ←入力 17 ←入力 not found ←出力 0 ←入力 7 ←入力 2 ←出力 プログラム #include <stdio.h> #include <stdlib.h> #define ARRAY_SIZE 10 int swap(int a, int b) { int c; c = a; a = b; b = a; } int main(void) { int array[] ; int low = 0; int high = n - 1; int mid; int key; int i, j, n; int data; struct node *p; puts("整数を入力して下さい。"); for(i = 0; i < ARRAY_SIZE && scanf("%d", array + i) == 1; ++i){ if(array[i] == 0) break; for(j = i; j > 0 && array[j-1] > array[j]; j--) swap(array[j-1], array[j]); } n = i; puts( "探索する値を入力して下さい" ); scanf( "%d", &key ); while( low <= high ) / { mid = (low + high) / 2; if( array[mid] == key ) { return ; } else if( array[mid] < key ) { low = mid + 1; } else { high = mid - 1; } } puts( "not found" ); return 0; }

  • 作っているプログラムが分かりません・・・

    プログラムが… 以下のプログラムを作っているのですが、よく分かりません・・・ A監督が 77,B走塁コーチは 78 です.さて,77 と 78の素因数の和は等しくなっています. つまり,77=7×11,78=2×3×13,7+11=18,2+3+13=18 となっています. このように,素因数の和が互いに等しいという条件を満たすような, 差が 1 の自然数の組を 20000 以下でできるだけ多く探索しましょう. ここで,20000 以下には 26 組しかないことがわかっています. #include<stdio.h> #difine MAX 20000 int main(){ int sum[MAX+1]; int i,j,n; for(i = 2;i <= MAX;i++){ j = 2; while(j*j <= i){ if(i % j == 0){ _________________; break; } else j++; } if(j*j > i) ___________________; } n = 0; for(i = 2;i < MAX;i++) if(sum[i] == sum[i+1]){ n++; printf("%3d (%d,%d)\n",n,i,i+1); } return 0; } 補足 分からないのはプログラムの書き方で _________________；の部分だけでも答えていただけるとありがたいです。

  • ２分探索法　『成功・不成功探索一回の実行時間を求める』

    Ｃ言語の授業で課題が出たのですが、自分が思っているような値が出なくて困っています。よろしければヒントだけでも頂ければなと思います。 ----------課題---------- 整列されているＮ個のデータに対して、その中にｖがあるかどうかを判断する２分探索プログラムを実行する Ｎの値を10^6、5×10^6、10^7、5×10^7、10^8 と変化させたとき、成功探索、不成功探索一回の実行時間をそれぞれ求めよ。 このとき、Ｎと実行時間の関係はどのようになっているか（１００字程度で） 　　Ｎ　　成功探索　　不成功探索 　10^6　　＊＊＊秒　　　＊＊＊秒 5×10^6 　＊＊＊秒　　　＊＊＊秒 　10^7　　＊＊＊秒　　　＊＊＊秒 5×10^7 　＊＊＊秒　　　＊＊＊秒 　10^8　　＊＊＊秒　　　＊＊＊秒 ---------------------------------------- ～↑を元に作成したプログラム（成功探索の場合）～ #include <stdio.h> #include <stdlib.h> #include <time.h> #define T 1000000 #define N 100000000 int a[N]; int main(void) { clock_t t1,t2; int t; int i; int l, r, k, v, m; for (i = 0; i < N; i++) a[i] = i; t1=clock(); for (t = 0; t < T; t++) { v = rand() % N; l=0; r=N-1; k=-1; while (r >= l) { m = (l+r)/2; if (v == a[m]) { k=m; break; } if (v < a[m]) r = m-1; else l = m+1; } } t2=clock(); printf("cpu time=%10.6f[micro sec]\n",(double)(t2-t1)*1000000/(CLOCKS_PER_SEC*T)); return 0; } ↑a[i]すべてに０～Ｎ－１を代入し、ｖにランダムに０～Ｎ－１の値を代入する。２分探索法で、ｖ＝a[i]となったら終了する。 実行時間は、↑の操作を10^6回行い、その平均を実行時間をする…単位：マイクロ秒 として、コンパイルして動いたんですが実行時間の値にずれがありどの値が一番適切か分からなくて困っています。 ↑のプログラムをそれぞれのＮで実行したところ Ｎ＝ 　10^6で実行・・・1.016 0.891 0.969 1.155 1.14 [micro sec] 5×10^6で実行・・・1.422 1.500 1.563 1.250 1.406 1.297 　10^7で実行・・・1.750 1.360 1.37 1.407 1.672 1.531 5×10^7で実行・・・1.859 1.797 1.812 1.800 　10^8で実行・・・2.062 2.140 2.320 2.500 このような結果になりました。 これで正しいのでしょうか？もう少しずれの幅が小さいと決められそうなのですが…そもそもプログラムが間違ってるんでしょうか？ でも、Ｎが大きくなるにつれて実行時間が増えてるのでこちらはまだいいんですが・・・問題は不成功探索の方です。 次に 不成功探索では↑のプログラムの 乱数ｖのところを変化させて v=rand() % N；という箇所を ｖ＝Ｎ;としました。 a[i]には０～Ｎ－１が入っているので、ｖ＝Ｎとすれば必ず不成功になるはずですよね？ こうして実行してみると Ｎ＝ 10^6、5×10^6、10^7、5×10^7、10^8と値を変化させても 0.719 0.54 0.625 0.534 [micro sec] に近い値ばかり出てしまい、正しい値とは到底思えません。 不成功探索は成功探索より時間がかかるはずですよね？なのになぜこのようになってしまったのでしょうか？ 後、Ｎと実行時間の関係とは、最終的に得られた結果を元にして「実行時間はlog2Nに比例している」と言えばいいんでしょうか？ こういうものってどのように回答したらいいのかヒントだけでももらえると非常に有難いです。 長々とスイマセン。 少し気づいたことなど些細なことでも全然かまわないので、どうかよろしくお願いします。

  • C言語　探索に関して

    C言語探索プログラムについて質問です。 #include <stdio.h> #define MAXSIZE 100 void swapData(int *x, int *y){ int tmp; tmp = *x; *x = *y; *y = tmp; } void simpleSort(int data[], int first, int last) { int i, j; for(i = first; i < last; i++){ for(j = i+1; j <= last; j++){ if(data[i] > data[j]) { swapData(&data[i], &data[j]); } } } } int ArrayBinarySearch(int data[], int n, int x) { int left = 0, right = n - 1, center; while(left <= right){ center = (left + right)/2; if(data[center]=x){ return center; }else if(x > data[center]){ left = center + 1; }else if(x < data[center]){ right = center - 1; } } return -1; } int main(int argc, char *argv[]) { int data[MAXSIZE]; int i, x; FILE *fp; scanf("%d", &x); fp = fopen(argv[1], "r"); for(i = 0; i < MAXSIZE; i++) { if (fscanf(fp,"%d", &data[i]) == EOF) break; } simpleSort(data, 0, i-1); printf("%d", ArrayBinarySearch(data, i, x )); return 0; } 数値が書かれたファイルを読み込んでソートした後に二分探索を行うプログラムをつくったのですが、うまく動きません。 どこがおかしいか教えてください。 お願いいたします。 ちなみに関数ArrayBinarySearchは目的の値が見つかれば配列中でのインデックスを、見つからない場合は-1を返す関数にしているつもりです。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する