午後問題の歩き方 | 矢沢久雄の アルゴリズム問題の解き方(2)


2020-03-23 更新

前回の記事では、午後試験のアルゴリズム問題を克服する最終ステップとして、ひたすら過去問題を練習して自分流の解法を見出す、というアドバイスしました。

今回の記事では、自分流の解法の例を紹介します。

これは、私流の解法ですので、皆さん流の解法を見出すための参考にしてください。

error 本記事ではわかりやすいよう、問題に背景色を入れています

すぐに設問と選択肢を見て、答えを得るために必要なことを知る

ここでは、アルゴリズム問題の例として、平成 22 年度 春期 午後 問 8「マージソート」を取り上げます。

マージソートは、試験のシラバスに示されている基本アルゴリズムの 1 つです。

配列を要素数が 1 個になるまで分割し、それらを結合( merge = 結合)することを繰り返して、全体をソートします。あらかじめ、この手順を知っている必要があります。

試験問題を全て掲載しますが、ポイントとなる部分だけを見てください(もしも、きちんと解くと 30 分ぐらいかかっちゃいますよ)。

 

アルゴリズム問題は、

プログラムの説明
navigate_next
expand_more
プログラム
navigate_next
expand_more
設問

の順に構成されています。プログラムを隅々まで理解するのではなく、設問に答えることが目的なので、プログラムの説明とプログラムにざっと目を通したら、すぐに設問を見ることが重要 です。

 

以下が、この問題の設問です。

問題とプログラムは、あとで示します。基本情報技術者試験の問題は、すべて選択問題です。したがって、選択肢が大きなヒントになります。とにかく選択肢をよく見てください。

設問 1 プログラム中の       に入れる正しい答えを,解答群の中から選べ。

a に関する解答群
ア num ≧ 0  
イ num ≧ 1
ウ num > 1  
エ num > 2

b に関する解答群
ア list[i]  
イ list[num + i]
ウ list[num1 + i]  
エ list[num2 + i]

c に関する解答群

ア (i < num1) and (j < num2)
イ (i < num1) or (j < num2)
ウ (j < num1) and (i < num2)
エ (j < num1) or (i < num2)
オ (i + j) < (num1 + num2)
カ (i + j) ≦ (num1 + num2)
キ (i + j) > (num1 + num2)
ク (i + j) ≧ (num1 + num2)

announcement横にスクロールできます
(以下、プログラムなども同じ)

設問 2 最初に与えられた配列 list のデータが次の場合,プログラム Sort の α における配列 list の内容の移り変わりとして正しい答えを,解答群の中から選べ。

 配列 list のデータ : 3, 8, 2, 7, 5, 1

なお,解答群の ” → ” は、内容が左から右へ移り変わっていくことを示している。

解答群

ア 2 → 3 → 2,3 → 2,3,8 → 1 → 5 → 1,5 → 1,5,7 → 1,2,3,5,7,8
イ 3 → 8 → 3,8 → 2,3,8 → 7 → 5 → 7,5 → 1,5,7 → 1,2,3,5,7,8
ウ 2,8 → 2,3,8 → 1,5 → 1,5,7 → 1,2,3,5,7,8
エ 3,8 → 2,3,8 → 7,5 → 1,5,7 → 1,2,3,5,7,8
オ 2,3,8 → 1,5,7 → 1,2,3,5,7,8
カ 3,8,2 → 7,5,1 → 1,2,3,5,7,8
設問 3 副プログラム Merge の β 部分と同じ結果を得る処理として正しい答えを,解答群の中から選べ。

■ i < num1
| ・list[i] + slisti[i]
| ・i ← i + 1
■
■ j < num2
| ・list[j] ← slist2[j]
| ・j ← j + 1
■

■ i < num1
| ・list[i + num1] ← slist1[i]
| ・i ← i + 1
■
■ j < num2
| ・list[j + num2] ← slist2[j]
| ・j ← j + 1
■

■ i < num1
| ・list[j + num1] ← slisti[i]
| ・i ← i + 1
■
■ j < num2
| ・list[i + num2] ← slist2[j]
| ・j ← j + 1
■

■ i < num1
| ・list[i + num2] ← slist1[i]
| ・i ← i + 1
■
■ j< num2
| ・list[j + num1] ← slist2[j]
| ・j ← j + 1
■
ア
■ i < num1
| ・list[i] + slisti[i]
| ・i ← i + 1
■
■ j < num2
| ・list[j] ← slist2[j]
| ・j ← j + 1
■

イ
■ i < num1
| ・list[i + num1] ← slist1[i]
| ・i ← i + 1
■
■ j < num2
| ・list[j + num2] ← slist2[j]
| ・j ← j + 1
■

ウ
■ i < num1
| ・list[j + num1] ← slisti[i]
| ・i ← i + 1
■
■ j < num2
| ・list[i + num2] ← slist2[j]
| ・j ← j + 1
■

エ
■ i < num1
| ・list[i + num2] ← slist1[i]
| ・i ← i + 1
■
■ j< num2
| ・list[j + num1] ← slist2[j]
| ・j ← j + 1
■

設問と選択肢からわかること

設問 1
設問 1 は、プログラムの穴埋めです。
設問 1 は、変数 num に対する条件です。
設問 2
設問 2 は、プログラムのトレース(処理の流れを追いかけること)です。
設問 2 は、選択肢の先頭が異なるので、最後までトレースせずに、先頭の処理だけがわかれば正解を選べるでしょう。
設問 3
設問 3 は、プログラムの改良です。
設問 3 は、list 、slist1 、slist2 という配列の操作です。

このように、設問と選択肢を見ることで、答えを得るために何が必要なのかがわかります。その必要なことを見つけるために、プログラムの説明とプログラムを見るのです。

これが、アルゴリズム問題の基本的な解法です。

PR

具体例を想定してプログラムの説明を読む

以下に、プログラムの説明を示します。プログラムの説明を読むときに大事なのは、具体例を想定すること です。

この問題では、配列 list に格納された num 個のデータを昇順にソートしますが、num 個では、プログラムの説明がよくわからないでしょう。

num 個に具体的な値を想定してみましょう。

 

もしも、問題に具体例が示されている場合は、素直にそれを想定しましょう。

出題者は、「制限時間内に問題を解くためのヒントをあげよう」と考えて、具体例を示している からです。

 

この問題では、num = 7 個とした具体例が示されているので、それを想定してください。

〔プログラムの説明〕

 プログラム Sort は配列に格納された整数値のデータを再帰的に分割し,分割したデータの値の大小を比較しながら併合していくことでデータを昇順に整列するプログラムである。Sort は併合に副プログラム Merge を使用する。

(1) num 個 ( num ≧ 1 ) のデータを配列 list に格納して Sort を呼び出すと,整列された結果が配列listに返却される。
(2) Sortでは,次の手順で配列 list に格納された整数値のデータを整列する。
① 配列 list に格納されているデータを,先頭から num ÷ 2 個と残り num - num ÷ 2 個とに分割して,二つの配列 slist1 と slist2 に格納し,それぞれの配列に対して再帰的に Sort を呼び出す。ここで,配列 slist1 と slist2 の大きさは省略されているが,必要な領域は確保されている。この再帰的な呼出しは,引数で渡される配列 list のデータの個数が 1 になると終了する。
② Merge を使用し,二つの配列 slist1 と slist2 を併合して一つの配列 list にする。
(3) Merge では,次の手順で,整列済の二つの配列 slist1 と slist2 を併合し,整列した一つの配列 list を作成する。
① 配列 slist1 又は slist2 のどちらか一方の要素がなくなるまで,次の ② を繰り返す。
② 配列 slist1 と slist2 の要素を順に比較して,小さい方から順に配列 list に格納する。
③ 配列 slist1 又は slist2 の残った要素を配列 list に追加する。
(4) sort と Merge の引数の仕様を表 1,2 に示す。配列の添字は 0 から始まる。
表 1 Sort の引数の仕様
引数名/
返却値
データ型 入力/
出力
意味
list[] 整数型 入力及び出力 データが格納されている 1 次元配列
num 整数型 入力 配列 list のデータの個数
表 2 Merge の引数の仕様
引数名/
返却値
データ型 入力/
出力
意味
slist1[] 整数型 入力 整列済のデータが格納されている 1 次元配列
num1 整数型 入力 配列 slist1 のデータの個数
slist2[] 整数型 入力 整列済のデータが格納されている 1 次元配列
num2 整数型 入力 配列 slist2 のデータの個数
list[] 整数型 出力 併合したデータを格納する 1 次元配列

次のデータを例にして,整列処理の流れを図に示す。

 配列 list のデータ : 5, 7, 4, 2, 3, 8, 1

num = 7 個という具体例を想定すると、プログラムの説明が、とてもわかりやすくなります。

たとえば、プログラムの説明の(2)の ① にある

「配列 list に格納されているデータを、先頭から num ÷ 2 個と 残り num - num ÷ 2 個に分割して、二つの配列 slist1 と slist2 に格納し」

これは num = 7 個を想定すると、

「配列 list に格納されている 7 個のデータ を、先頭から 3 個と 残り 4 個に分割して、二つの配列 slist1 と slist2 に格納し」

と読むことができます。とてもわかりやすいでしょう。

 

label関連タグ テクニック 具体的な値を想定

プログラムは、具体例を想定したプログラムの説明と対応付けて読む

プログラムを読むときは、具体例を想定したプログラムの説明と対応付けて読んでください。そうすると、「この穴埋めでは、こういう処理を行えばよいのだ!」と気付きます。

以下に、プログラムを示します。

このプログラムは、Sort 関数 と Merge 関数 から構成されています(試験問題では、関数を副プログラムや手続と呼ぶ場合もあります)。

先ほど示したプログラムの説明の(2)は、Sort 関数 の説明であり、(3)は Merge 関数 の説明です。


  〔プログラム〕
  /* プログラム Sort */
  ○Sort(整数型: list[], 整数型: num)
  ○整数型: i, numi, num2
  ○整数型: slist1[], slist2[]               /* 配列の宣言 */
  ▲   a  
  | ・num1 ← num ÷ 2                       /* slist1 の要素数計算 */
  | ・num2 ← num - num1                    /* slist2 の要素数計算 */
  | ■ i:0, i < numi, 1 
  | | ・slist1[i] + list[i]
  | ■
  |
  | ■ i:0, i < num2, 1
  | | ・slist2[i] ←   b  
  | ■
  | ・Sort(slisti, num1)
  | ・Sort(slist2, num2)
  | ・Merge(slisti, numi, slist2, num2, list)
  ▼         ◀----------------- α
  /* プログラム Sort の終わり */

  /* 副プログラム Merge */
  ○Merge(整数型: slisti[], 整数型: num1,
      整数型: slist2[], 整数型: num2,
      整数型: list[] )
  ○整数型: i, j
  ・i ← 0
  ・j ← 0
  ■   c  
  | ▲ slist1[i] < slist2[j]
  | | ・list[i + j] ← slisti[i]
  | | ・i ← i + 1
  | +
  | | ・list[i + j] ← slist2[j]
  | | ・j ← j + 1
  | ▼
  ■
■ (i < num1) or (j < num2) | ▲ i < num1 | | ・list[i + j] ← slist1[i] | | ・i ← i + 1 | +     ◀------- β | | ・list[i + j] ← slist2[j] | | ・j ← j + 1 | ▼ ■
/* 副プログラム Merge の終わり */

プログラムの説明の(2)に「この再帰的な呼び出しは、引数で渡される配列 list のデータの個数が 1 になると終了する」とあります。

「再帰的な呼び出し」とは、関数の処理の中で同じ関数を呼び出すことによって、繰り返しを実現するテクニックです。

この説明と対応付けて Sort 関数 のプログラムを見ると、確かに Sort 関数 の処理の中で Sort 関数 を呼び出している部分があります。

それによって「空欄 a は、再帰呼び出しを続ける条件だ!」と気付きます。

 

気付いたら、設問の選択肢を見てみましょう。

「この再帰的な呼び出しは、引数で渡される 配列 list の データの個数 が 1 になると 終了する」の
「引数で渡される 配列 list の データの個数」とは、num のことです。

「num が 1 になると 終了する」のですから、
「num が 1 より大きければ 再帰呼び出しを続ける 」です。

これに該当する選択肢は、ウです。

a に関する解答群

ア num ≧ 0  イ num ≧ 1
ウ num > 1  エ num > 2

 

繰り返し処理の穴埋めは、繰り返しの最初の処理を想定すればわかる

「繰り返し処理を読み取るのが苦手」という人が多いでしょう。

よい解法があります。

繰り返しの最初の処理を想定するのです。

そうすれば、繰り返し処理の中にある穴埋めに、何が入るか簡単にわかります。

繰り返しの穴埋めは、繰り返しのどの時点でも成り立つのですから、最もわかりやすい最初の処理を想定するのです。

 

この問題では、

要素数 7 個の配列を 3 個と 4 個に分割し、
3 個を 1 個と 2 個に分割し、
4 個を 2 個と 2 個に分割し、
2 個を 1 個と 1 個に分割する、

という手順を繰り返していますが、最初の要素数 7 個の配列を 3 個と 4 個に分割する処理を想定して、プログラムを読んでみましょう。

そうすれば、プログラムの空欄 b の穴埋めができます。


  | ■ i:0, i < numi, 1 
  | | ・slist1[i] + list[i]
  | ■
  |
  | ■ i:0, i < num2, 1
  | | ・slist2[i] ←   b  
  | ■

num = 7 個を想定しているので、num1 = 3 個、num2 = 4 個です。

要素数 7 個の配列 list を、要素数 3 個の配列 slist 1 と、要素数 4 個の配列 slist 2 に分割します。

 

上側にある繰り返し処理で、
slist1[0] ~slist1[2] に list[0] ~ list[2] をコピーしました。

 

したがって、下側にある繰り返し処理では、
slist2[0] ~ slist2[3] に list[3] ~ list[6] をコピーします。

このコピーにおいても、繰り返しの最初の処理を想定して、slist[0] に list[3] をコピーしているものを選択肢の中から選びます。

b に関する解答群

ア list[i]  
イ list[num+i]
ウ list[num1+i]  
エ list[num2+i]

繰り返しの最初なのですから i = 0 です。

i = 0 で list の [ ] の中が 3 になるのは、選択肢ウ の list[ num1 + i ] です。num1 = 3 だからです。

いかがでしょう。

繰り返しの最初の処理を想定すると、簡単に答えを選べることがわかったでしょう。

 

過去問題を練習しながら、このように自分流の解法を見出す経験を積み重ねて行けば、アルゴリズム問題を克服できるはずです。

説明が長くなってしまうので、他の設問の解法の説明は省略しますが、ぜひ自分流でやってみてください。

 

以下に、解答とアルゴリズム問題の出題傾向に関する記事を示しておきます。

解答

設問 1 a -ウ、b -ウ、c -ア
設問 2 ウ
設問 3 エ

 

label アルゴリズム問題の出題傾向

アルゴリズム及びデータ構造の出題傾向(午後問8)

午後試験のアルゴリズム問題の制限時間の目安は、150 分÷( 20 点 / 100 点)= 30 分 です。

他人が作ったプログラムを 30 分で理解するのは、はっきり言って困難 でしょう。

プログラムを隅々まで完璧に理解しようなどと思わずに、「問題が解ければいいのだ」と割り切ることが大事です。

設問が解ければよいのです。選択肢から答えを選べればよいのです。

そう思うと、前回の記事で紹介した某講師の「選択肢だけを見て答えを選ぶ」という解法にも、一理あるような気がします。ただし、「選択肢を見て大いにヒントにする」ならです。

それでは、またお会いしましょう!

 

label 関連タグ
実は、午前試験を『免除』できます 独習ゼミで午前免除試験を受けた 85% の方が、
午前分野を免除しています。
2020年 6月 12日 12時
締め切り間近!!
alarm2020年 6月 12日 12時締切!

詳しく見てみるplay_circle_filled
label これまでの『午後問題の歩き方』の連載一覧 label 著者

『プログラムはなぜ動くのか』(日経BP)が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでPCの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識0ベースのITエンジニアや一般書店フェアなどの一般的なPCユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

  • 「プログラムはなぜ動くのか」(日経BP)
  • 「コンピュータはなぜ動くのか」(日経BP)
  • 「出るとこだけ! 基本情報技術者」 (翔泳社)
  • 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」(翔泳社)
  • 「ifとelseの思考術」(ソフトバンククリエイティブ) など多数