カテゴリ:2.ソフトウェア > 2.3 アルゴリズム

 

1.整列アルゴリズムとは

整列アルゴリズムとは、昇順または降順に並び替えることです。
たとえば、以下が昇順に整列させたようすです。
45836 →34568

整列アルゴリズムには、いくつかの方法があります。
試験ではそれほど問われませんが、たまに問われる内容です。順に見ていきましょう。

2.選択ソート

過去問(H17秋SW午前問12)では、「未整列の並びに対して,最小のキー値をもつ要素と先頭の要素とを入れ換える。同様の操作を,未整列の並びの長さを一つずつ減らしながら繰り返す。」と述べられています。

3.バブルソート(交換法)

過去問(H20春SW午前問11不正解選択肢)では、「隣り合う要素を比較して,大小の順が逆であれば,それらの要素を入れ替えるという操作を繰り返す。」と述べられています。

簡単な例を述べます。小さい数字が上に来るように並べ替えます。一番下の2とその上の1を比べます。次に、1と4を比べます。1の方が小さいので入れ替えます。次に、1と3を比べ、小さい1を上にします。こうやって、一番上にはもっとも小さい数字が来ます。これを繰り返します。

aa
 
では、以下をやってみましょう。6個の要素を持つ以下の配列があります。
a(6)={21,5,53,71,3,17}
右から左へのバブルソートによって、昇順に整列させます。
比較するのは、6つ目と5つ目、5つ目と4つ目、4つ目と3つ目・・・・2つ目と1つ目です。そして、小さい方に入れ替えます。1回目は以下のようになります。
アルゴリズム
右から左なので、17と3を比較し、3の方が小さいのでそのままです。次に、3と71を比較し、3の方が小さいので入れ替えます。
このようにすると、最後は
3  21  5  53  71  17 です。
2回目→ 3  5  21  17  53  71
3回目→ 3  5  17  21  53  71
となり、3回で整列します。しかし、実際にはもう少し時間がかかる場合もあれば、最初から整列している場合には、1回もやらずに整列する場合もあります。最長は、5回(n-1)です。
では、これをアルゴリズムにしてみましょう。1回目の操作だけに着目します。

①a[6](=17) とa[5](=3)を比較し、a[5]の方が大きければ、a[5]とa[6]を入れ替えます。
②a[5](=3) とa[4](=71)を比較し、a[4]の方が大きければ、a[4]とa[5]を入れ替えます。
③・・・
⑤a[2](=3) とa[1](=21)を比較し、a[1]の方が大きければ、a[1]とa[2]を入れ替えます。

なんとなく、アルゴリズムが見えてきましたね。
・ループ条件:j=6(初期値)、j>=2(継続条件)、j--(増分の式)
・判断:a[j-1]>a[j]
・処理(Yesの場合):a[j-1]とa[j]を入れ替え。

ただし、a[j-1]とa[j]を入れ替えるのは、人間には簡単ですが、プログラムでは工夫が必要です。
・a[j-1]→w (値をwに退避)
・a[j]→a[j-1] 
・w→a[j]

この処理を、何回も繰り返すだけです。
では、何回繰り返すでしょうか。それは、要素数をNとすると、最長はN-1回です。1回処理することに、一番小さい数字が一番左に行きます。N-1回繰り返せば、必ず整列します。
また、2回目、3回目と繰り返す際に、上記の処理は1回ずつ少なくて済みます。なぜなら、1番小さい数は一番左にすでに配置されているからです。
なので、アルゴリズムとしては、以下のようになります。※a[j-1]とa[j]を入れ替えは簡略化されています。

過去問(H25秋AP午前問9)を見てみましょう。
問9 未整列の配列α[i] (i=1,2, …,n)を,流れ図で示すアルゴリズムによって昇順に整列する。n=6でa[1]~a[6]の値がそれぞれ, 21,5,53,71,3,17の場合,流れ図において,a[j-1]とa[j]の値の入替えは何回行われるか。
流れ図

ア 3  イ 6  ウ 8 エ 15





バブルソートを利用しています。【正解】ウ

4.マージソート

過去問(H26秋AP午後問3)では、マージソートに関して、「マージソートは,整列(ソート)したいデータ(要素)列を,細かく分割した後に,併合(マージ)を繰り返して全体を整列する方法である」と述べています。

過去問(H26秋AP午後問3)に具体的なイメージがあるので、みてみましょう。
問3 マージソートに関する次の記述を読んで,設問1~3に答えよ。
 マージソートは,整列(ソート)したいデータ(要素)列を,細かく分割した後に,併合(マージ)を繰り返して全体を整列する方法である。
 ここでは,それぞれの要素数が1になるまでデータ列の分割を繰り返し,分割されたデータ列を昇順に並ぶように併合していくアルゴリズムを考える。例として,要素数が8の場合のアルゴリズムの流れを図1に示す。
2
(後半略)
 応用情報技術者試験を勉強する成子 

分割したあと、併合(マージ)するからマージソートですね!
では、過去問を見てみよう!
■H26秋AP
問6 データ列が整列の過程で図のように上から下に推移する整列方法はどれか。ここで図中のデータ列申の縦の区切り線は,その左右でデータ列が分割されていることを示す。
H26a-問6
ア クイックソート     イ シェルソート
ウ ヒープソート      エ マージソート
【正解】エ

5.挿入ソート 

過去問(H17秋SW午前問12)では、「未整列要素の並びの先頭の要素を取り出し,その要素を整列済みの要素の申の正しい位置に挿入する。」と述べられています。

6.シェルソート

過去問(H20春SW午前問11不正解選択肢)では、「ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し,更に間隔を詰めて同様の操作を行い,間隔が1になるまでこれを繰り返す。」と述べられています。

7.クイックソート

過去問(H20春SW午前問11不正解選択肢)では、「中間的な基準値を決めて,それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。次に,それぞれの区分の中で同様な処理を繰り返す。」と述べられています。

8.ヒープソート

まず、ヒープとはなんでしょう。
過去問(平成17年春FE午後問4)では、以下の解説があります。 
ヒープとは,図のように,各節の値が自分の子の節の値以上になっている2分木である。
17-FE問4-1
このように、ヒープ(2分木)を使って整列させる方法です。過去問(H20春SW午前問11)では、「ヒープソートでは,未整列の部分を順序木に構成し,そこから最大値又は最小値を取り出して既整列の部分に移す。この操作を繰り返して,未整列部分を縮めていく。」とあります。
da
かなり簡略化していますが、イメージをつかんでいただきたいと思います。
まず、(ⅰ)で、3412を2分木にします。
(ⅱ)一番大きな値である4が一番上に来るように入れ替えます。
(ⅲ)最大値の4を取り出します。
(ⅳ)以降、このような最大値を取り出すことを繰り返します。

■過去問平成28年秋期 午前 問6
問6 ヒープソートの説明として,適切なものはどれか。
ア ある間隔あきに取り出した要素から成る部分列をそれぞれ整列し,更に間隔を詰めて同様の操作を行い,間隔が1になるまでこれを繰り返す。
イ 中間的な基準値を決めて,それよりも大きな値を集めた区分と,小さな値を集めた区分に要素を振り分ける。次に,それぞれの区分の中で同様な処理を繰り返す。
ウ 隣り合う要素を比較して,大小の順が逆であれば,それらの要素を入れ替えるという操作を繰り返す。
エ 未整列の部分を順序木にし,そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して,未整列の部分を縮めていく。





アはシェルソート
イはクイックソート
ウはバブルソート
正解は、エです。
 
みましょう。
問11 データの整列方法に関する記述のうち,適切なものはどれか。
ア クイックソートでは,ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し,更に間隔を詰めて同様の操作を行い,間隔が1になるまでこれを繰り返す。
イ シェルソートでは,隣り合う要素を比較して,大小の順が逆であれば,それらの要素を入れ替えるという操作を繰り返す。
ウ バブルソートでは,中間的な基準値を決めて,それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。次に,それぞれの区分の中で同様な処理を繰り返す。
エ ヒープソートでは,未整列の部分を順序木に構成し,そこから最大値又は最小値を取り出して既整列の部分に移す。この操作を繰り返して,未整列部分を縮めていく。





アはシェルソート
イはバブルソート
ウはクイックソート正解は、エです。 平成17年春期 FE 午後 問4
問4 次のプログラムの説明及びプログラムを読んで,設問1~3に答えよ。

〔プログラムの説明〕
 副プログラムHeapSortは,配列に格納されている整数値をヒープソートで昇順に整列するプログラムである。

(1)整列するNum個(Num≧2)の整数値は,大域変数の配列A[1],A[2],・・・,A[Num]に格納されている。

(2)ヒープソートは,2分木を用いてデータを整列する。2分木を配列で表現するには,ある節がA[i]に対応するとき,その左側の子の節をA[2×i]に,右側の子の節をA[2×i+1]に対応させる。図では,丸が節を,丸中の数字が節の値を示し,実際に値が格納されている配列の要素を丸の脇に示している。

(3)ヒープとは,図のように,各節の値が自分の子の節の値以上になっている2分木である。
17-FE問4-1
(4)整列の手順は,次のとおりである。
 ① 配列Aの中の,A[1],A[2],・・・,A[Num]を整列対象とする。
 ② 整列対象の各要素が,(2)で述べたような2分木を表現しているものとして,要素の値を入れ換えてヒープを作る。その結果,木の根(A[1])には整列対象の要素の最大値が入る。
 ③ 木の根(A[1])の値と,木の最後の節(整列対象の最後の要素に対応する節)の値とを交換する。
 ④ 木の最後の節を2分木から取り除く(整列対象の要素を一つ減らす)。 
 ⑤ ④の結果が,木の根だけになるまで,②~④の処理を繰り返す。

(5)ヒープを作り直す手順は,次のとおりである。
 ① 木の根を親の節とする。
 ② 子の節がなければ終了する。
 ③ 二つの子の節のうち値が大きい方と親の節の値を比較し,親の節の方が小さいときは,値を交換する。親の節の値が子の節の値以上のときは,何もしないで終了する。
 ④ 値を交換した子の節を根とする部分木に対して,①~③の処理を繰り返す。
17-FE問4-3
 
設問1 プログラム中の[   ]に入れる正しい答えを,解答群の中から選べ。

aに関する解答群
 ア L ← Top
 ウ L ← Top × 2
 イ L ← Top + 1
 エ L ← Top × 2 + 1

bに関する解答群
 ア L ≦ Last
 ウ R ≦ Last - 1
 イ L  < Last
 エ R ≦ Last - 2
正解は、
a ウ
b ア です。


設問2 次の記述中の[   ]に入れる正しい答えを,解答群の中から選べ。

 図のヒープを用いて,〔プログラムの説明〕の(4)の③,④を1回だけ実行して,②が終了したとき,最初A[10]に入っていた値12が格納されている配列要素の添字は[ c ]である。また,それまでに節の値を交換した回数は[ d ]である。

解答群
ア 2  イ 3  ウ 4  エ 5  オ 6
カ 7  キ 8  ク 9
正解は、
c キ
d ウ です。


設問3 最初にヒ―プを作成する副プログラムInitHeapはMakeHeapを使って作る
ことができる。次のプログラム中の[   ]に入れる正しい答えを,解答群
の中から選べ。
17-FE問4-4
解答群
ア Idx: 1,Idx ≦ Last,2
イ Idx: 1,Idx ≦ Last ÷ 2,1
ウ Idx: Last,Idx ≧ 1,-2
エ Idx: Last ÷ 2,Idx ≧ 1,-1
正解は、エです。

 

1.再帰とは

再帰」とは、「再び帰ってくる」ですが、どこに帰ってくるかというと、自分自身です。
過去問(H29春AP問7を部分的に抜粋)では、「再帰的プログラムは,手続の中でそれ自体を呼び出すプログラム」とあります。

f:id:mamori_yuto:20181103063502j:plain

以下に、再帰的(リカーシブ)、再入可能(リエントラント)などを含めて解説しています。

sm.seeeko.com

2.過去問および再帰的なプログラムの具体例

(1)H29秋AP午前問7

問7 fact(n)は,非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。
ア if n=0 then return 0 else return n×fact(n-1)
イ if n=0 then return 0 else return n×fact(n+1)
ウ if n=0 then return 1 else return n×fact(n-1)
エ if n=0 then return 1 else return n×fact(n+1)

【正解】ウ

fact(1)=1
fact(2)=2×fact(1)=2×1=2
fact(3)=3×fact(2)=3×2×1=6
fact(4)=4×fact(3)=4×3×2×1=24

たとえばn=3とすると
fact(3)=3×fact(2)
fact(2)=2×fact(1)
fact(1)=1×fact(0)
fact(0)= ←ここを0にしてしまってはダメで、1にすべき。
そうしないと
fact(3)=3×2×1×0=0になってしまう。

実際のプログラムは、以下に記載しました。
 

sm.seeeko.com

http://sm.seeeko.com/archives/65924343.html
これの、再帰的に書く方です。

(2)H25秋AP

問8 再帰的に定義された手続procで,proc(5)を実行したとき,印字される数字を順番に並べたものはどれか。
     proc(n)
      n=0ならば戻る
      そうでなければ
      {
       nを印字する
       proc(n-1)を呼び出す
       nを印字する
     }
     を実行して戻る

ア 543212345
イ 5432112345  
ウ 54321012345  
エ 543210012345

【正解】イ

実際のプログラムは以下

#include<stdio.h> // stdio.h(標準入出力を行うための関数が定義されたファイル)を読み込む

// proc関数。整数を一つ(int n)受け取って処理を行い、処理後に値は返さない(void)
void proc(int n) {
    if (n == 0) // もしnが0なら
        return; //   何もせず戻る
    else        // そうでなければ(nが0以外なら)
    {
        printf("%d", n); // nを表示
        proc(n-1);       // proc(n-1)を実行
        printf("%d", n); // nを表示
    }
}

// main関数。引数は取らない。処理後に値を返さない
void main() {
    proc(5);
}


補足解説
  proc(n)の流れは
    ・nを表示
    ・proc(n-1)を実行
    ・nを表示
  の3段階。
 
  したがって、proc(5)を呼び出すと、
    ・5を表示
    ・proc(4)を実行
    ・5を表示
 
  proc(4)の処理は
    ・4を表示
    ・proc(3)を実行
    ・4を表示
  

  これを続けていくと、
    ・5を表示
     ・4を表示
      ・3を表示
       ・2を表示
        ・1を表示
         ・proc(0)を実行
        ・1を表示
       ・2を表示
      ・3を表示
     ・4を表示
    ・5を表示

  proc(0)は何もせずにreturnするため、
  最終的に、
      ・5を表示
     ・4を表示
      ・3を表示
       ・2を表示
        ・1を表示
        ・1を表示
       ・2を表示
      ・3を表示
     ・4を表示
    ・5を表示
  という処理になる。

1.アルゴリズムとは

アルゴリズムとは、「コンピュータに,ある特定の目的を達成させるための処理手順(H25春IP問53)」です。
また、アルゴリズムを視覚的に表したものがフローチャートです。

sm.seeeko.com

2.アルゴリズムに関する過去問

(1)過去問(H25春IP)
問53 コンピュータを利用するとき,アルゴリズムは重要である。アルゴリズムの説明として,適切なものはどれか。
ア:コンピュータが直接実行可能な機械語に,プログラムを変換するソフトウェア
イ:コンピュータに,ある特定の目的を達成させるための処理手順
ウ:コンピュータに対する一連の動作を指示するための人工言語の総称
エ:コンピュータを使って,建築物や工業製品などの設計をすること





アはコンパイラ
ウはプログラム言語
エはCAD です。

正解はイです。

■H28春
問6 流れ図に示す処理の動作の記述として,適切なものはどれか。ここで,二重線は並列処理の同期を表す。
H28h-問6
ア ABC又はACBを実行してデッドロックになる。
イ AB又はACを実行してデッドロックになる。
ウ Aの後にBC又はCB,  BC又はCB,…と繰り返して実行する。
エ Aの後にBの無限ループ又はCの無限ループになる。





【正解】ウ

■H27春
問6 モンテカルロ法によって,正方形に内接する円の面積を近似的に求める方法はどれか。
ア 円に内接する正多角形の面積によって求める。
イ 正方形内に多数の小円を重ならないようにぎっしり詰めて,円の中にある小円の個数によって求める。
ウ 正方形内に乱数を用いて多数の点を一様に打ち,円の中にある点の個数によって求める。
工 正方形内を微細な間隔の格子点で区切り,円の中にある格子点の個数によって求める。





【正解】ウ

■H26春
問5 記憶領域を管理するアルゴリズムのうち,ベストフィット方式の特徴として,適切なものはどれか。
ア 空きブロック群のうち,アドレスが下位のブロックを高い頻度で使用するので,アドレスが上位の方に大きな空きブロックが残る傾向にある。
イ 空きブロック群のうち,要求された大きさを満たす最小のものを割り当てるので,最終的には小さな空きブロックが多数残る傾向にある。
ウ 空きブロックの検索にハッシュ関数を使用しているので,高速に検索することができる。
エ 空きブロックをアドレスの昇順に管理しているので,隣接する空きブロックを簡単に見つけられ,より大きな空きブロックにまとめることができる。





【正解】イ

過去問(H27秋AP午前問6)を見てみましょう。
問6 次に示すユークリッドの互除法(方法1,方法2)で,正の整数a, bの最大公約数は,それぞれmとnのどちらの変数に求まるか。ここで,mod nは,mをnで割った余りを表す。
flow
【正解】ウ

 

1.フローチャートとは

流れ図(フローチャート)に関して過去問(H27春IP問59)では、「プログラムの処理手順を図式を用いて視覚的に表したもの」と述べられています。

過去問(H25秋AP午前問9)を使って、流れ図の記号の意味を解説します。
loop
 また、並行四辺形の記号が出てくることがあります。これは、「入出力」が一般的です。
なので、ユーザからの入力や、画面表示になります。

2.フローチャートの問題

過去問(H27春IP問48)では、以下の流れ図があります。
問48 表に示す構成のデータを,流れ図の手順で処理する場合について考える。流れ図中のx,y,zをそれぞれデータ区分A, B, Cと適切に対応させれば,比較(“xか?”,“yか?”',“zか?”)の回数の合計は,最低何回で済むか。
流れず

ア 170  イ 190  ウ 230  工 250





正解:ア

平成29年春期 午前 問6
問6 次の流れ図の処理で,終了時のxに格納されているものはどれか。ここで,与えられたa,bは正の整数であり,mod(x,y)はxをyで割った余りを返す。

H29h-問6
ア aとbの最小公倍数
イ aとbの最大公約数
ウ aとbの小さい方に最も近い素数
エ aをbで割った商
実際に数字を入れてみるといいでしょう。
mod(x,y)はxをyで割った余りを返す。とありますから、xの方を大きくしましょう。
たとえば、a=10、b=3とします。
x=10、y=3

ループ1の1回目(y=0ではないので)
t=1(10÷3=3 余り1)
x=3
y=1

ループ1の2回目(y=0ではないので)
t=0
x=1
y=0
つまり、x=1であることが分かります。では、選択肢の4つを見ると
ア aとbの最小公倍数 ⇒30なので×
イ aとbの最大公約数 ⇒1なので○
ウ aとbの小さい方に最も近い素数 ⇒1なので○
エ aをbで割った商 ⇒3なので×
よって、イかウです。

イではないかとあたりをつけて、a=12、b=8、xが最大公約数である4になるかを確かめましょう。
たとえば、a=12、b=8とします。
x=12、y=8

ループ1の1回目(y=0ではないので)
t=4(12÷8=1 余り4)
x=8
y=4

ループ1の2回目(y=0ではないので)
t=0
x=4
y=0
と、xが最大公約数である4になりました。これは、選択肢ウのaとbの小さい方に最も近い素数である2とも違います。よって、イが正解です。

過去に似たような問題が出題されていますので、このアルゴリズムは最大公約数を求めるものだと覚えておくとよいでしょう。

【正解】イ
補足および実際のプログラムはこちら
http://sm.seeeko.com/archives/65924350.html

 

1.探索アルゴリズムとは

「探索」とは、言葉の通り、探すことです。たとえば、英和辞典で「network」の意味を調べる際、膨大な単語の中から「network」という文字を探します。この探索方法ですが、思いつくのは、辞書の先頭ページから順番に探していく方法です(線形検索といいます)。でも、あまり効率的ではありませんよね。

そこで、べつの方法を考えます。辞書はアルファベット順に並んでいるので、辞書の真ん中の単語を探します。(たとえばmeanとします)。「network」が探した単語(mean)より前か後ろかを比較します(後ろですよね)。次は、後ろの部分の真ん中の文字を探し、「network」と比較します。こうして半分にしていって検索する方法が2分検索で、検索時間は線形検索に比べて少なくなります。

探索アルゴリズムには、主に以下の3つです。
・線形探索
・2分探索
・ハッシュ表探索

順に解説します。

2.線形探索

(1)線形検索とは

線形探索は、名前をつけるほどの探索技法ではなく、単に、先頭から順に探す方法です。もし、n個から1つを探索するときに、先頭に探したい値があれば、1回で見つけることができます。しかし、最後(n番目)にあれば、全部の値と比較する必要があり、比較回数はn回です。

よって、平均比較回数は(n+1)÷2 となり、nが大きくなると、比較回数はとても大きくなります。

(2)線形検索の過去問

■H26春AP
問6 従業員番号と氏名の対がn件格納されている表に線形探索法を用いて,与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。
 ここで,検索する従業員番号はランダムに出現し,探索は常に表の先頭から行う。また,与えられた従業員番号がこの表に存在しない確率をaとする。

H26h-問6ans






【正解】エ

■H19春SW
問13 配列上に不規則に並んだ多数のデータの中から,特定のデータを探し出すのに適したアルゴリズムはどれか。
ア 2分探索法 ウ ハッシュ法
イ 線形探索法 エ モンテカルロ法







不規則に並んだデータは、線形検索しかできません

正解:イ

3.2分探索

(1)2分探索とは

冒頭の辞書の例で説明しましたが、データが大きい順または小さい順に並んでいる場合に、それを2分した中央値と比較していくことで、目的の値を探す方法です。

 
(2)2分探索をやってみよう!!
2分探索のシンプルな例を考えましょう。
100個の要素が入っている配列Aがあったとします。
配列Aは、昇順に並んでいます。

配列A[100]={1,3,7,8,12,20,22・・・}

ここで、20という数字がどこ(何番目)にあるかを探します。
1つ1つ頭から比較していくのが逐次検索(線形検索)です。
これは、非常に時間がかかります。最大、100回比較をする必要があります。
そこで、2分探索です。
真ん中の値と比較します。
ここからは、H23秋AP午前問8を参考に進めます。

変数の説明
in:探索値(検索する値。今回は75)
sch:検索が見つかった場合の添え字(配列の何番目か)。初期値は、見つかっていないという意味で-1
left:探索する左端の添字の値。初期値は0
right:探索する右端の添字の値。初期値はn-1
center:探索する配列の中央値の添字
※中央値が小数になった場合、小数は切り上げまたは切り捨て。

■アルゴリズム
分かりやすく、
配列A[7]={1,3,7,8,12,20,22}
でやってみましょう。

①初期値のセット
・in←20 (探索する20を入れる)
・sch←-1
・left←0
・right←6

②中央値との比較・・・見つかるまでループ

・中央値をセット
center←(left + right)/2=3
・中央値と比較
 X[center]:in X[3]=8とin=20を比較
 inの方が大きいので、次は、centerとrightの中央値を取って比較する。
  X[center]<in であれば、leftにcenterの値を入れる(left←center)。このとき、centerとは一致していなかったので、center+1とする方が効率的。
 left=4
 center←(4+6)/2=5 として、再度ループ
  X[center]:in X[5]=20とin=20を比較。等しいので、もとめるschにcenterを入れる。sch←center
 
■アルゴリズム
ではこれを、nを使って作り上げます。
①初期値のセット
・in←20 (探索する20を入れる)
・sch←-1
・left←0
・right←n-1

②中央値との比較・・・見つかるまで(sch=-1のまま)ループ、または探索範囲がなくなったとき(たとえば、left>right)も実施★この部分は後で解説。

・中央値をセット
center←(left + right)/2
・中央値と比較
 X[center]:in 
search
さて、★の検索条件です。設問にもなっています。正解は、left<=rightです。ポイントは、left=rightの場合も含むということです。
どんな場合があるか、試してみましょう。
X[2]={1,3} ※X[0],X[1]
left←0
right←1
in=3
center←(0+1)/2=0.5 ・・・0とする
X[0](=1)とin(=3)を比較し、X[0]<inであるため、right=center-1=0としてループが続きます。

4.ハッシュ探索

過去問(H21春AP午後問2)では、「配列に対して,データを格納すべき位置(配列の添字)をデータのキーの値を引数とする関数(ハッシュ関数)で求めることによって,探索だけではなく追加や削除も効率よく行うのがハッシュ法である。」とあります。
aae62d2c

なんだかよく分かりませんね。
たとえば、ハッシュ関数によって、演算した結果(たとえば10で割った余り)をデータを保存する番地にしてしまうのです。
324、543、127、99、875などとデータが並んでいるとしてハッシュ値を番地にすると以下のようになります。

番地  値
3   543
4   324
5   875
7   127
9    99

今回は数字にしていますが、英単語を調べる辞書と思えばいいでしょう。543という英単語を調べたいとき、その情報がどこにあるか。543をハッシュ演算すると3になります。3番地を見ればいいと分かります。つまり、どれだけ数があっても、1回で探索できるのです。
ただ、衝突があるので、そこが注意点です。

このあとの過去問(H25春AP午前問5)に「コードから一意に決まる場所に格納した探索表」とあります。ハッシュ関数を用いて、コードから一意に決まる場所に値を格納する探索方法と考えてもいいでしょう。

ハッシュ探索の問題は以下です。

■H27秋
問5 キーが小文字のアルファベット1文字(a,b,…,zのいずれか)であるデータを,大きさが10のハッシュ表に格納する。ハッシュ関数として,アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは,昇順に連続した2進数が,アルファペット順にコードとして割り当てられている。
ア aとi     イ bとr     ウ cとl     エ dとx





アルファベットのASCIIコードおよび1の位の数は次のようになります。
アルファベット ASCIIコード 1の位の数
   a    97   7
   b    98   8
   c    99   9
   d    100   0
   ・・・
   i    105   5
   ・・・
   r    114   4
   ・・・
   x    120   0
ただ、ASCIIコードを覚えている人はいないことでしょう。
2つも文字がいくつ離れているのかを考えれば衝突するかがわかります。dとxは、20離れていて、ハッシュ関数は、1の位の数を用いているので、衝突することがわかります。
【正解】エ

■H27春
問5 自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(r)を
    h(x) = x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,nはハッシュ表の大きさであり,x  mod nはxをnで割った余りを表す。
ア a+bがnの倍数
イ a-bがnの倍数
ウ nがa+bの倍数
エ nがa-bの倍数






【正解】イ

■H26春
問19 ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで,複数のデータが同じハッシュ値になることはないものとする。

H26h-問19






【正解】エ

■H25秋
問7 自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
    h(x) = x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,nはハッシュ表の大きさであり,x mod n はxをnで割った余りを表す。
ア a+bがnの倍数   ウ nがa+bの倍数
イ a-bがnの倍数    エ nがa-bの倍数





【正解】イ
 

5.探索アルゴリズムの過去問

(1)H25春AP午前問5
問5 探索表の構成法を例とともにa~cに示す。最も適した探索手法の組合せはどれか。
  ここで,探索表のコードの空欄は表の空きを示す。
H25h-問5





a:コード順に並んでいるので、2分検索が使えます
b:使用頻度順ということは、つまり、バラバラということです。よって、線形検索しか使えません。

【正解】ア

(2)H24秋FE問3
問3 探索方法とその実行時間のオーダの適切な組合せはどれか。ここで,探索するデータの数をnとし,ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また,実行時間のオーダが,nの2乗であるとは、n個のデータを処理する時間がc×nの2乗(cは定数)で抑えられることをいう。

 2分探索  線形探索 ハッシュ探索
ア log2n    n      1
イ nlog2n    n     log2n
ウ nlog2n    n2     1
工 n2乗     1    n

まず、ここでいうオーダとは探索する最大時間と考えてください。
まあ、計算する上では「最大実行回数」で考えるといいです。探索する時間=回数×1回の処理時間です。なのせ、1回の処理時間がここでいうcと考えればいいでしょう。
862492bc

問題文の最後の意味がよく分かりません。なぜnの2乗?
これもあくまでも一例です。表のnの2乗があるので、それを例にしているだけです。余談ですが、nの乗数が一番多いものに左右されますよね。
では答を考えましょう。線形探索でn個の数を順番に探していくと、運が悪いと最大n回かかります。なので、線形探索のオーダはnです。探索時間にすると、この場合はc×nになります。
ハッシュ探索は常に1です。

正解:ア

H27秋FE問3
問3 関数f(x)は,引数も戻り値も実数型である。この関数を使った,①~⑤から成る手続を考える。手続の実行を開始してから②~⑤を十分に繰り返した後に, ③で表示されるyの値に変化がなくなった。このとき成立する関係式はどれか。
① x←a
② y←f(x)
③ yの値を表示する。
④ x←y
⑤ ②に戻る。

ア f(a)=y イ f(y)=0 ウ f(y)=a エ f(y)=y

解説
まず、引数と戻り値に関しては以下

順番に入れてみよう。
①でxにaを入れている。が、あくまでもこれは初期値。しばらくすると何かの値になるので、aにはあまり意味がない。
実効しているのは、②と④の繰り返し。
②でy=f(x)、④では、yをxに入れて、②の処理をする。
つまり、②ではy=f(y)になる。よって、エである。
わかりにくいので、具体例が欲しいところ。
以下に関数fを「2で割って、余りがあるときは切り上げにする関数」という分かりやすい例があった。
https://oshiete.goo.ne.jp/qa/988684.html

正解は、エ

↑このページのトップヘ