2007年08月05日

H16 情報 第5問

IV-5
C言語の関数bsearchを以下のように定義する。渡される引数は,ソートされた整数の配列,その要素数,および,探索すべき値である。配列内を探して見つかった場合は1を,見つからなかった場合は0を返す。
int bsearch(int a[], int N, int x){
 int L, R, m;
 L = 0; R=N−1;
 while (LくR){
  m=(L+R)/2;
  if(xくa[m]) R=m-1;
  else if(x>a[m]) L=m+1;
  else return 1;
 }
 if(x==a[m] return 1; else return0;
}
 この関数を呼び出した場合,引数xと配列の要素を比較した回数の総和は,配列の内容と引数xの値に応じて様々である。Nが8であり,xが配列に含まれるとした場合,比較回数の最小値と最大値を次の中から選べ。

@ 最小値1回,最大値3回
A 最小値1回,最大値7回
B 最小値2回,最大値6回
C 最小値2回,最大値7回
D 最小値2回,最大値8回


解答:C

a[0]=0, a[1]=1,…, a[7]=7とすると、
 x=0:3回
 x=1:3回
 x=2:3回
 x=3:2回
 x=4:4回
 x=5:4回
 x=6:6回
 x=7:7回
となる。

※もっと別の求め方がありそう…。


posted by noumea at 12:00| 東京 🌁| Comment(0) | TrackBack(0) | 技術士過去問 | このブログの読者になる | 更新情報をチェックする
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。