【C++線形探索】要素数nの配列v内のkeyと等しい全要素の添字を配列idxに格納する関数search_idxを作成せよ。

ただし、返却するのはkeyと等しい要素の個数とする。

あ～あ～何やってるんだろぉねぇ～～

専攻じゃないのに興味がわくんごぉ～

どうも、メガネです。

今回は番兵法とか言うのを知ったのでそれを自分用にまとめておく。

番兵法

どうやら処理を軽くすることができるらしい。

といってもコンソールレベルのプログラミングなんぞマイＰＣなら爆速で処理できるので実感はできないが。

内容としては、目標の値を見つけるために、一番最後の配列要素を目標とする数値に割り当てて、ちょっとだけ処理を減らすもの、ということらしい。

内容は以下のような感じ。

    int i = 0;
    int count = 0;
    v[n] = key;

    for (i = 0;i<n; i++) {
        if (v[i] == key) {
            idx[count] = i;
            count++;
        }
    }

    return count; 

v[n] = key;

読み込む配列の要素を+1して定義して、目標となる数字を最後に持ってきて、こいつが見つかってしまったら番兵発見、つまり、それまでの過程で異常者なし。ということらしいね。

う～ん、要素数が数十個だとやっぱり実感はできないね。

作ったプログラム

ちょっとだけ悩んだけどなんとか行けた。

出力は要素と指定が１ずれてるのが気に入らないので出力表記は変えた。

#include <iostream>
#define NUMBER 10

int search_idx(int v[], int idx[], int key, int n) {

    int i = 0;
    int count = 0;
    v[n] = key;

    for (i = 0;i<n; i++) {
        if (v[i] == key) {
            idx[count] = i;
            count++;
        }
    }

    return count; //FAILEDって見やすいだけ？
}

int main()
{
    int vx[NUMBER + 1];
    int idx[NUMBER + 1];
    int i, ky, id, x;
    printf("要素数を入力してください。\n");
    for (i = 0; i < NUMBER; i++) {
        printf("vx[%d]", i);
        scanf_s("%d", &vx[i]);
    }

    printf("探す値：");
    scanf_s("%d", &ky);


    id = search_idx(vx, idx, ky, NUMBER);
    if (id == 0) {
        puts("探索失敗");
    }
    else {
        printf("%dは,",ky );
        for (i = 0; i < id;i++) {
            printf("要素[%d]",idx[i]);
            if (i == id - 1) {
                printf("番目にあります\n");
            }
            else
            {
                printf("番目と、");
            }
        }
    }return 0;    
}

出力結果は以下のような感じ。

要素数を入力してください。
vx[0]1
vx[1]2
vx[2]6
vx[3]5
vx[4]3
vx[5]6
vx[6]4
vx[7]9
vx[8]8
vx[9]5
探す値：6
6は,要素[2]番目と、要素[5]番目にあります

まとめ

何べんも数こなしてたらだんだん引数とかconstとかなんだとかが、案外単純なこと言ってたということに気が付き、なぜやってこなかったのかと超絶後悔。

でも、今からなら変えられるだろう。