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

質問

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

メイン関数から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文だとどのように考えたらいいのでしょうか？

回答No.4

hofuhofu · ベストアンサー

番兵法の意義からすると冗長な表現を省いた#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回の比較が入りますから、逐次検索と変わらなくなってしまいます。
多分ここでつまづかれていたんでしょうけど。

回答No.3

tatsu99

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

回答No.2

hofuhofu

もっと簡略化して
for(i=0;a[i]!=key;i++);
最後のセミコロンを忘れずに。

ちなみに、
while (1)
はそのまま、
for(;;)
と置き換えても、同じ動作をします。
継続条件を書かないのは、無限ループさせたいときによく使われる手法です。
http://www.kusa.ac.jp/~kajiura/c/kurikaeshi/newpage21.htm#無限ループ

回答No.1

tatsu99

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

お礼

回答ありがとうございます。

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