ここからは暫し探索を扱います．検索ではなく，探索です．この二つは似て非なるものでして，探索は「リストの中に探し物はありますか？どうですか？」を確認するもの・・・とでも考えておいてください．

探索の中でも，最も単純な線形探索を行います．
まっ，早い話しが「リストの最初から順に比べて探し物があるかどうかを調べる．」というアルゴリズムです．

作るプログラムは，0 ～ 100 の整数からなる 50 個の要素をもつリスト（配列）を用意して，その中に任意に定めた数が存在するかどうかを調べるというものです．

Cording

何はともあれ，今回は書いたプログラムとその実行結果を示して，その後にプログラムの内容についてご説明したいと思います．

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
 
int main(int argc, char *argv[]) {
    int a[51];
    int target = atoi(argv[1]);
    int target_num = 0;
    bool find_out = false;

    srand(time(NULL));
    for (int i = 0; i < 50; i++) {
        a[i] = rand() % 101;
    }
    a[50] = 1000;

    while (target <= 100 && !find_out && a[target_num] < 1000) {
        find_out = (target == a[target_num++]);
    }

    printf("データリストは [\n");
    for (int i = 0; i < 5; i++) {
        print(" ");
        for (int j = 0; j < 10; j++) {
            printf("%3d ", a[10 * i + j]);
        }
        printf("\n");
    }
    printf("] です．\n);

    if (find_out) {
        printf("%d は%d番目の位置に見つかりました．\n, target, target_num);
    } else {
        printf("%d は見つかりませんでした．\n", target);
    }

    return 0;
}

yossii@penguin:~/C/search$ ./liner_search 17
データリストは [
   1  60   5  79   4   6  65  35  96  18
  95  79  98  65   6  82  95  50  22   4
  45  30  87  45  72 100  32  52  70  28
  86  88  54  58  32  58  64  97  93  25
  81  53   3  79  84   9  60  78  26  48
] です
17 は見つかりませんでした．
yossii@penguin:~/C/search$ ./liner_search 17
データリストは [
   4  75  99  40  43  23  19  70  18   1
  55  84  17  62  85  67  96  62  70  42
   1  66  18  34  39 100  14  46  94  20
  24  65  95  89  71   3  11  56  73  30
  57  95  13  40  56  64   6  17  92  42
] です
17 は13番目の位置に見つかりました．

#include <stdlib.h> 

後述する関数 rand() 及び srand() を利用するためにヘッダファイル stdlib.h をインクルードします．

#include <time.h> 

後述する関数 time() を利用するためにヘッダファイル time.h をインクルードします．

#include <stdbool.h> 

bool型変数 を利用するためにヘッダファイル stdbool.h をインクルードします．

rand()

乱数を返す関数です．返される値は，0 からライブラリ内で定められた最大値までの整数値です．完全な乱数ではないため，専門家の方は疑似乱数と呼ぶようですが，私は素人なので素直に「乱数」と言います．
乱数を利用するときは，ある範囲の乱数という形で使います，例えば 0 ～ 9 までの乱数というように．このような乱数を作るためには，割り算の余りを用います．演算子は「%」ですね．
　　x = rand() % 10;
と書けば，0 ～ 9 の乱数が得られます．
ところがこの関数は，そのまま使うと，常に同じ値の並びを返してきます．これでは，乱数が欲しいときに必ずしも役立ちません．それを解決するのが，srand() です．

srand()

先頭の s は seed を表します．つまり，乱数の種を与えるという意味です．しかし・・・更に困ったことに srand(1)，srand(2)，srand(3)，・・・などと指定すれば，それぞれ異なる数値の並びになるのですが，括弧内の数値が同じだと同じ乱数を常に返します．ん～！困りましたねぇ．
そこで，よく用いられるのが，srand() の括弧内にその時の時刻を指定するという方法です．

time(NULL)

これについは，お得意のおまじないと考え
　　srand(time(NULL));
と使うと，欲しい乱数が得られる・・・今のところはそう覚えておきましょう．
変数型やら返り値について若干の説明をする必要がありまして，今はこういうものだと思った方が幸せです．
関係のないお話しですが，数学をやる方の中には「このようなことが気になって気になってしかたがない」という方がいらっしゃいます．気が済むまで気にしてください．気付いたときにはドツボにハマっている・・・などということがよくあります．
私事で恐縮ですが，似たような経験から，大学入学後僅か一週間で数学の才能のないことを知り，以後，卒業まで大学にはほとんど行きませんでした．それでも卒業できるという良き時代？でしたが f＾＾;

find_out = (target == a[target_num++]);

特に説明する必要はないと思いますが，bool型の変数として find_out という変数を定義しています．初期値は false で，target である数値と同じデータが見つかったときに true に変わります．これが true になったら，while のループから抜け出せるということです．当然，結果を書き出す際にも使っています．

番兵法

この例では，データリストの要素数が 50 となっています．ただし，状況によっては，要素の最後が上手く見つけられないという場合があります．（と書きつつ，私自身はホントかいな？と思っていますが）そのようなときに，データリストの最後にあり得ないデータを配置し，あり得ないデータに出くわしたら終わりという方法をとるそうです．これを番兵法といいます．情報技術者試験には出題されるそうです．

Last modified: Friday, 1 September 2023, 1:00 PM