本日は、タイトルの通り二つのアルゴリズムを学びました。
二つの探索法をざっくりと説明します。
【2分探索法】
整列してあるデータの半分の値を調べ、探索したいデータが半分より前半にあるか後半にあるかを調べ、探索範囲を半分に狭めるというものを繰り返すものです。
【ハッシュ表探索法】
データを格納する段階で格納位置を決め、特定のデータを一発で取り出せるようにしたものです。
以上二つの探索法のアルゴリズムが疑似言語^1で載っており、これらをもとにC言語にしてみました。
【2分探索法】
#include<stdio.h>
int main(void){
int t[10]={1,2,3,4,5,6,7,8,9,10}; //配列
int idx,low,middle,tkey; //各種変数の設定
int high;
scanf("%d",&tkey); //探索データの入力
idx=0;
low=1;
high=10;
while(idx == 0 && low<=high){ //継続条件の設定
middle= (low + high)/2;
if(tkey == t[middle]){
idx=middle;
}else if(tkey < t[middle]){
high = middle-1; //最大値を設定
}else{
low = middle+1; //最小値を設定
}
}
printf("%d\n",t[idx]);
return 0;
}
【ハッシュ表探索法】
#include<stdio.h>
int main(void){
int h[]={0,219,-1,532,463,142,-1,-1,-1,298,308}; //配列
int d,n,m,flg;
scanf("%d",&d); //探索データの入力
n=(d % 10) +1; //ハッシュ値の設定
m=n;
flg =0; //終了条件のフラグ設定
while(flg==0){
if(h[m] == d)
flg = m;
else if(h[m] == -1){
flg = -1; //終了フラグ
}
m++;
if(m==11)
m=1;
else if(m==n)
flg = -1; //終了フラグ
}
if(flg > 0)
printf("探索成功\n");
else
printf("該当データなし\n");
}
以上がプログラムになります。
まだまだ、未熟ですが頑張っていきます。
<脚注>
^1:基本情報技術者試験内にて使用される独自の言語である。
[参考文献]
0コメント