カテゴリ: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
正解は、エです。

■H25春
問7 配列Aに対して次の手続を実行して,2≦k≦100である素数kだけを全て出力したい。a,b,cに入るループの初期値,終値,増分として,適切な組合せはどれか。

for k = 2 to 100 step 1:
  A[k] = 1;
for m = 2 to 10 step 1:
    for k =[   a   ] to [   b   ] step [   c   ]:
   A[k] = 0;
for k = 2 to 100 step 1:
  if A[k]≠0:
   print k;

H25h-問7
【正解】イ
実際のプログラムの例は以下
#include<stdio.h>   // stdio.h(標準入出力を行うための関数が定義されたファイル)を読み込む
// main関数。引数は取らない。処理後に値を返さない
void main() {
    int A[101];    // 配列変数Aを定義。保存可能個数は101個でA[0]-A[100]を使用可能。
    int k, m;  // 整数型の変数kとmを定義
    // kを2から100まで、1ずつ増やす(k++)
    for (k = 2; k <= 100; k++) {
        A[k] = 1;  // A[2]-A[100]をすべて1にしている
    }
    // 2の倍数-10の倍数をリストから消していく
    for (m = 2; m <= 10; m++) { // mを2から10まで1ずつ増やす
        for (k = 2*m; k <= 100; k += m) {
            // kを2mから100までmずつ増やす
            // つまりkは2m, 3m, 4m,・・・と変化
            A[k] = 0;  // kはmの倍数=素数ではないから0にする
        }
    }
    for (k = 2; k <= 100; k++) { // kを2から100まで1ずつ増やす
        if (A[k] != 0) {  // A[k]が0でない、つまりkが素数なら
            printf("%d,", k);  // kを表示
        }
    }
}
【処理の解説】
・エラトステネスのふるい法を使って素数を求めています。
・変数Aは、0か1の値になるが、A[k]=0なら非素数、A[k]=1なら素数(処理の途中では「素数の可能性」)
・まず2から100をすべて素数かもしれないリストに入れる
   (k=2-100についてA[k] = 1)
素数とは「約数として自分と1だけもつ」ことから、「何かの倍数であれば素数ではない」という考えで、倍数をすべて消していく。具体的にはA[k] = 0

 

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

↑このページのトップヘ