C++を咥えて個別アルゴリズムをつつく0−線形探索法。まめな方法だね♪2008-08-18 Mon 20:01
この記事は「
アルゴリズムの方法論をつつく2−線形探索。仕方がない、逐一調べよう。」
との連動企画ピヨ。詳しい説明はそちらを見てね。
そして、ボクの実装例を見る前に自分で実装を試みよう。
お待たせ♪それじゃつつくピヨ♪
どう?見てのとおり不器用なアルゴリズムだね。ソートしていないとデータが探しずらい事がよく分かるピヨね。みんな、整理整頓はマメにしておこう♪じゃ、バイ♪バイ♪ |
この記事のコメント探索時のループでは条件として「index < MAX」となってますので、見つからなかった時の条件として「index == ( MAX - 1 )」では具合悪いかと。。。その後の条件も不要かと思います。
2008-08-19 Tue 13:40 | URL | DD. #GMs.CvUw[ 内容変更]
コメント有難うございます。
その判定につきましては、「見つからなかった」のか「最後までいっただけ」なのかを判定するために必要となります。 この例ですと4を検索した場合Indexは9になりますが、見つからなかった時もIndexは9(MAX−1)となります。これを区別するための判定が【線形探索法】では必要とされていますのでそう実装しました。 この問題は次に紹介する「番犬」の手法を使えば解決します。こういった欠点のあるアルゴリズムを紹介する事により、アルゴリズムの進歩を味わってもらいたい考えている次第です。
2008-08-19 Tue 15:04 | URL | インドリ #-[ 内容変更]
検索対象が見つからなかった場合、
「index < MAX」の条件では、 indexがMAXと同じかそれより大きい場合になるかと思いますので、「index == ( MAX - 1 )」ではなく、「index == MAX」にはならないのでしょうか?
2008-08-21 Thu 15:31 | URL | DD. #GMs.CvUw[ 内容変更]
それには理由が2つあります。
まず一つ目に、C++は0から数えるから、配列のインデックスは最大値が9となりますので、10ではうまくいきません。 二つ目に、ループの index < MAX は10になった瞬間に終わりますのでやはりindex == MAXだとうまくいきません。 疑問に思ったことがあったら、これからもバンバンコメント書いてね。本当に間違っている事がよくありますので助かります。
2008-08-21 Thu 16:11 | URL | インドリ #-[ 内容変更]
おいらだったら、見つかった時点で break ではなく
return index; とします。 これなら、ループを抜けた==見つからなかった が確実に成立しますので。 もちろん、比較を何度もしないというメリットもありますが、 それ以上にだれが見てもすぐわかるというメリットもありますのでw とっちゃん さんの手段はベストなんだけど、ひとつ問題があるピヨ。それは・・・番兵法の利点が説明できないことですw
だって、番兵とび越えちゃうものw 名前を付けて頂ければ、このブログで紹介するピヨ。 こんな感じで・・・・ 「○●アルゴリズム」作者とっちゃん 殿
2008-08-21 Thu 18:18 | URL | インドリ #-[ 内容変更]
あ、番兵がいるのかw
それは考えてなかったわぁw<まじめに記事読め! いえ、この記事には番兵がいなくて、次の記事で番兵法を紹介しているので、それは仕方がないです。
2008-08-21 Thu 18:48 | URL | インドリ #-[ 内容変更]
すいません。よくわかってないので教えて下さい。
>二つ目に、ループの index < MAX は10になった瞬間に終わりますのでやはりindex == >MAXだとうまくいきません。 例えば検索文字として"10"を入力した場合、配列内から見つからなかったので、 indexが10の時点でループが終るかと思います。 なので、次のif文の「index == ( MAX - 1 )」は成立せず、 return値として-1は返らず、エラーと見なされなくなるのではないでしょうか? >見つからなかった時もIndexは9(MAX−1)となります。 がよくわかりませんでした。
2008-09-07 Sun 23:32 | URL | DD. #GMs.CvUw[ 内容変更]
ステップ実行してみてください。
そうすればわかると思います。
2008-09-08 Mon 12:19 | URL | インドリ #-[ 内容変更]
|
コメントの投稿 |
||
|
|
||
| 管理者だけに閲覧 | ||
|
|
||
この記事のトラックバック |
|
| 無差別に技術をついばむ鳥 |
|