無差別に技術をついばむ鳥

情報処理技術全般を気まぐれに研究するブログです

C++を咥えて個別アルゴリズムをつつく0−線形探索法。まめな方法だね♪

この記事は「 アルゴリズムの方法論をつつく2−線形探索。仕方がない、逐一調べよう。」 との連動企画ピヨ。詳しい説明はそちらを見てね。 そして、ボクの実装例を見る前に自分で実装を試みよう。
お待たせ♪それじゃつつくピヨ♪


#include < iostream >
using namespace std;

//保持するデータの最大数
static const int MAX = 10;

//線形探索法で指定された値を探索する
//なお、戻り値がー1の場合は発見出来なかった事を示す。
class SearchMan {
public:
    static int LinearSearch(int target[MAX], int searchValue) {
        int index;
	//逐次的に探す
	for( index = 0; index < MAX; index++) {
		if( target[ index ] == searchValue ) {
			break;
		}
	}
	//見つかったの?それとも最後まで行っちゃったの?
	if ( index == MAX  ) 
		return -1; 
	return index;
    }
};

int main(void)
{
    int values[MAX] = { 9,3,5,6,2,8,7,0,1,4 };

    //整理前のデータを確認
    cout << "整列前のデータを表示します。" << endl;
    for(int i = 0; i < MAX; i++) cout << values[i] << '\t';
    cout << endl;

    //探索するデータを決定
    int searchValue = 0;
    cout << "検索する数値を0〜9の範囲内で指定して下さい:";
    cin >> searchValue;
	
    //線形探索の結果を表示
    int index = SearchMan::LinearSearch(values, searchValue );
    if ( index == -1 ) {
	cout << "指定された値「" << searchValue << 
		"」は用意された配列内に存在しません。" << endl;
	return -1;
    }
    cout << "指定された値「" << searchValue << "」を" 
	<< ( index + 1 ) << "番目で発見しました!" << endl;
    return 0;
}
※間違いがあったので訂正しました。


どう?見てのとおり不器用なアルゴリズムだね。ソートしていないとデータが探しずらい事がよく分かるピヨね。みんな、整理整頓はマメにしておこう♪じゃ、バイ♪バイ♪
別窓 | C++ | コメント:17 | トラックバック:0 | ∧top | under∨
<<中の人の徒然草68 | 無差別に技術をついばむ鳥 | なでしこをつつく0−なでしこって誰?>>

この記事のコメント

探索時のループでは条件として「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
2008-08-21 Thu 16:44 | URL | とっちゃん #-[ 内容変更]
とっちゃん さんの手段はベストなんだけど、ひとつ問題があるピヨ。それは・・・番兵法の利点が説明できないことですw
だって、番兵とび越えちゃうものw
名前を付けて頂ければ、このブログで紹介するピヨ。
こんな感じで・・・・

「○●アルゴリズム」作者とっちゃん 殿
2008-08-21 Thu 18:18 | URL | インドリ #-[ 内容変更]
あ、番兵がいるのかw

それは考えてなかったわぁw<まじめに記事読め!
2008-08-21 Thu 18:40 | URL | とっちゃん #-[ 内容変更]
いえ、この記事には番兵がいなくて、次の記事で番兵法を紹介しているので、それは仕方がないです。
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 | インドリ #-[ 内容変更]
せんせぇしつもん。

> if ( index == MAX && target[ MAX - 1 ] != searchValue )

条件: target[ MAX - 1 ] != searchValue
は何のためにあるんすか?
2009-04-26 Sun 01:06 | URL | επιστημη #-[ 内容変更]
> せんせぇしつもん。
>
> > if ( index == MAX && target[ MAX - 1 ] != searchValue )
>
> 条件: target[ MAX - 1 ] != searchValue
> は何のためにあるんすか?

済みません。これも旧コードの異物のようです。
必要ありませんね。
今改めてみると混乱しているのが分かります。
2009-04-26 Sun 05:20 | URL | インドリ #-[ 内容変更]
ではココのコメントに関し、
インドリは誤りを認めたのね。

> ステップ実行してみてください。
> そうすればわかると思います。

これについても、インドリあなた自身は
実行/検証しなかった、てことね。
2009-04-26 Sun 13:21 | URL | επιστημη #-[ 内容変更]
> ではココのコメントに関し、
> インドリは誤りを認めたのね。
>
> > ステップ実行してみてください。
> > そうすればわかると思います。
>
> これについても、インドリあなた自身は
> 実行/検証しなかった、てことね。

そうですね。あの当時我ながらアホな間違いをした事を認めます。
結果的にブログに乗っているコードを実行していなかった事になります。
普段は直ぐ認めるのですが、「思い込みが激しいと」とセットにされていたので、気持ちが悪くて拒否してしまいました。
2009-04-26 Sun 13:26 | URL | インドリ #-[ 内容変更]
ブログに書いてあるコードは検証したコードと同じだと「思い込んでいた」
ブログに載っているコードに誤りなんて無いと「思い込んでいた」
C++の文法を確認もしないで↓のループが回りきった後のindexの値がMAX-1だと「思い込んでいた」
for( index = 0; index < MAX; index++)

別にね、この程度の思い込みは、誰にでもあると思うんだ。
でもね、普通の人は1回指摘されれば気付くんだよね。
DD.さんは何回指摘した?
3回だよ。3回も同じこと指摘されても気付かない。
それどころか間違いを指摘してきたDD.さんに確認を促したりする。

これじゃ「思い込みが激しい人」のレッテルを貼られても無理からぬ事だとは思わない?

つかさ、何で認められないの?
インドリ氏は「自分の短所を把握してそれを素直に受け入れて鍛錬する人間」なんでしょ?
今回のこの問題だって「思い込みが激しい」という短所を受け入れて、治すように努力すればいいだけでしょ。
2009-04-26 Sun 23:58 | URL | あ #Q.0G6czI[ 内容変更]
> 普段は直ぐ認めるのですが、「思い込みが激しいと」とセットにされていたので、
> 気持ちが悪くて拒否してしまいました。

余計なヒトコトが反感を買う。
思っていても表に出しちゃダメ。
2009-04-27 Mon 06:09 | URL | επιστημη #-[ 内容変更]
> 余計なヒトコトが反感を買う。
> 思っていても表に出しちゃダメ。

επιστημηさん、忠告有難うございます。
仰るとおりです。以後気をつけます。
2009-04-27 Mon 09:22 | URL | ミーちゃん #-[ 内容変更]
∧top | under∨

コメントの投稿

 

管理者だけに閲覧
 

この記事のトラックバック

∧top | under∨
| 無差別に技術をついばむ鳥 |