手順をヒントにトレースする練習問題｜アルゴリズムとプログラミング問題を解くコツ

矢沢 久雄
2022-11-28 更新

この連載では、基本情報技術者試験で、多くの受験者が苦手意識を持っている科目 B 試験 アルゴリズムとプログラミング分野の「アルゴリズム穴埋め問題」に的を絞って、正解を見出すポイントを詳しく説明します。

苦手を克服するには、短いプログラムを何度も練習して、穴埋めに慣れることが重要です。

そのために、実際の試験問題の一部をアレンジした練習問題を作りました。とても短い問題ですので、気軽に取り組んでください。

練習問題

◯InsertSort(整数型の配列: A, 整数型: N)
  整数型: Idx1, Idx2, Tmp
  論理型: Loop

  for (Idx1 を 1 から N より小さい間 1 つずつ増やす)
    Tmp ← A[Idx1]
    Idx2 ← a
    Loop ← true

    while (Idx2 が 0 以上でかつ Loop が true)
      if (A[Idx2] が Tmp より大きい)
        b
        Idx2 ← Idx2 - 1
      else
        Loop ← false
      endif
    endwhile

    A[Idx2 + 1] ← Tmp
  endfor

ポイント1: 手順の説明とプログラムを対応付ける（その1）

この問題のように、問題文に手順が詳しく示されている場合は、手順の説明とプログラムを対応付けることで、空欄で行う処理がわかる場合がよくあります。

以下は、手順の説明とプログラムを対応付けた例です。ここでは、手順の説明を青色の文字でコメントとして追加しています。実際の試験では、これを頭の中でやってください。

◯InsertSort(整数型の配列: A, 整数型: N)
  整数型: Idx1, Idx2, Tmp
  論理型: Loop

  /* 1. まず、 A[0] と A[1] を整列し、次に A[0] から A[2] までを整列し、*/
  /* その次に A[0] から A[3] までというように、整列する区間の要素を一つ */
  /* ずつ増やしていき、最終的に A[0] から A[N - 1] までを整列する。 */
  for (Idx1 を 1 から N より小さい間 1 つずつ増やす)
    /* 2. 整列する区間が A[0] から A[M] ( 1 ≦ M < N ) までのとき、A[M] を */
    /* 既に整列された列 A[0], more_horiz, A[M - 1] 中の適切な位置に挿入する。 */
    /* その手順は次のとおりである。 */
    /*  a. A[M] の値を、作業領域 Tmp に格納する。 */
    Tmp ← A[Idx1]
    /*  b. A[M - 1] から A[0] に向かって */
    Idx2 ← a
    Loop ← true

    while (Idx2 が 0 以上でかつ Loop が true)
      /* Tmp と比較し、Tmp よりも大きな値を */
      if (A[Idx2] が Tmp より大きい)
        /* 順次隣（要素番号の大きい方）に移動する。 */
        b
        Idx2 ← Idx2 - 1
      else
        Loop ← false
      endif
    endwhile

    /* c. b. で最後に移動した値の入っていた配列要素に Tmp の値を格納する。 */
    /* b. で移動がなかった場合には A[M] に格納する。 */
    A[Idx2 + 1] ← Tmp
  endfor

ポイント2: 手順の説明とプログラムを対応付ける（その2）

手順の説明とプログラムを対応付けたことで、以下がわかります。

  /*  a. A[M] の値を、作業領域 Tmp に格納する。 */
  Tmp ← A[Idx1]

手順の説明で M と呼んでいる変数は、プログラムでは Idx1 です。

  /*  b. A[M - 1] から A[0] に向かって */
  Idx2 ← a
  Loop ← true

  while (Idx2 が 0 以上でかつ Loop が true)

A[M – 1] から A[0] に向かって

を A[Idx2] で示すので、空欄 a で Idx2 に設定する初期値は M – 1 です。説明の M がプログラムでは Idx1 なので、空欄 a は Idx1 – 1 であり、選択肢ウが正解です。

ポイント3: 手順の説明とプログラムを対応付ける（その3）

空欄 b がある分岐では、

  /* Tmp と比較し、Tmp よりも大きな値を */
  if (A[Idx2] が Tmp より大きい)
    /* 順次隣（要素番号の大きい方）に移動する。 */
    b
    Idx2 ← Idx2 - 1

Tmp と比較し、 Tmp よりも大きな値を順次隣（要素番号の大きい方）に移動する。

という処理を行っています。

A[Idx2] が Tmp より大きい

なのですから、 Tmp より大きな値は A[Idx2] であり、この値を順次隣（要素番号の大きい方）に移動するのですから、 A[Idx2 + 1] ← A[Idx2] が適切であり、選択肢ウが正解です。

解答a － ウ, b － ウ

「習うより慣れろ」ということわざがあります。アルゴリズム穴埋め問題の克服に関しては、正にその通りでしょう。

この連載では、これからも短い練習問題を掲載していきますので、穴埋めに慣れることを目指してください。

正解を見出すポイントとして、同じことが示されることもあると思いますが、それは、多くの問題に共通したポイントがあるからです。

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

具体的な値を入れるとプログラムがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

具体例からヒントを掴む練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

プログラムを分割するコツがわかる練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

手順をヒントにトレースする練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

トレースのテクニックが身につく練習問題｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

2進数を掛け算するプログラム | アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

ヒープを配列で実現するプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

ルールに従って検査文字（チェックディジット）を求めるプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

配列のマッチング（突合せ）を行うプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

2進数の知識が必要なプログラム｜アルゴリズムとプログラミング問題を解くコツ

update 2022-11-28

矢沢 久雄

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

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

主な著作物

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