見出し画像

2-8. 英単語張の更新アルゴリズムを作成する　第2章完了

Tohoku I-STH

　本記事では、英単語張の更新アルゴリズムについて、問題演習を通して解説します。2分探索アルゴリズムを応用する問題です。
　問題のレベルは、基本情報技術者試験レベルです。
　本問題演習で、第2章の探索アルゴリズムの内容は完了です。

問題　次のプログラムの説明、擬似言語の記述形式及びプログラムを読んで、設問1、2に答えよ。

[プログラムの説明]

　英単語帳ファイル（レコード数≧1）を更新するプログラムである。利用者が英単語と日本語の訳語を入力し、英単語張ファイルにその英単語があれば訳語を書き換え、なければその英単語と訳語を追加する。
(1) 英単語帳ファイルの内容を、英単語の配列eitan と訳語の配列yaku に読み込む。
(2) 英単語張ファイルの単語数は、ファイルを読み込んだ時に変数n に代入される。
(3) 入力データとして英単語(E) と訳語(J) を入力し、Ｅを2分探索法を用いて検索する。
(4) Eが配列eitan 中にあれば、その訳語をＪに置き換える。なければ、配列eitan とyaku の内容をそれぞれ配列の最後尾から順にずらしていき、ＥとＪを正しい位置に挿入する。
(5) Ｅが空白文字の時データ入力処理を終了し、配列eitan とyaku の内容を英単語帳ファイルに書き出す。

設問1

　ファイル入力処理を実行した直後のeitan と yaku の配列として、このプログラムで正しく処理されるものを、解答群の中から選べ。

解答群

図1. 設問1の解答群

[プログラム]

〇プログラム名：英単語帳の更新
　文字型：E, J
　整数型: H, L, i, k, n
　文字型配列：eitan[100], yaku[100]　/* eitan[n]: n 番目の要素を示す */ ファイル： fail-A
〇手続：ファイル入力（faile-A, eitan, yaku, n）
　　　　/* ファイルfail-A の内容を配列eitan, yakuに読み込む手続 */
 　　　　/* n には読み込んだ単語数が代入される */
〇手続：ファイル出力（faike-A, eitan, yaku, n）
　　　　/* 配列 eitan, yaku の内容をファイルfaile-A に書き込む手続 */
　　　　/* n には書き込む単語数を指定する */
〇手続：データ入力（E, J）
　　　　/* 入力データの英単語と日本語の訳語をE, J に読み込む手続 */
ファイル入力（faile-A, eitan, yaku, n）
データ入力（E, J）
while (E ≠ 空白文字)
　H ← n
　L ← 1
　k ← int ((H + L) ÷ 2)  /* int () は、小数点以下を切り捨てる関数 */
   while (H ≧ L and E ≠ eitan[ k ] )
　　if (E ＜ eitan [k])
　　　L ← k + 1
　　endif
　　k ← int((H + L) ÷ 2)
 　endwhile
　if (E ＝ eitan[k])
α)　yaku[k] ← J
else
 i ← n
 while (i ≧ L)
β)　eitan[i +1] ← eitan[ i ]
     yaku[i + 1] ← yaku[ i ]
    i ← i - 1
   endwhile
γ)　eitan[L] ← E
　yaku[L] ← J
　n ← n + 1
  endif
  データ入力（E, J)
endwhile
ファイル出力（faile-A, eitan, yaku, n）

設問2　設問1の正しい配列を用いて、表の入力データを順に読み込むとき、□に入れる正しい答えを、解答群の中から選べ。

図2. 表の入力データ

　プログラム中のα～γの処理のうち、表の入力データ①では、αだけが実行され、入力データ②では□a が実行され、入力データ③では□b が実行される。また、入力データ②が挿入される位置は、配列の □c である。

a, b に関する解答群
ア　α～γのすべて
イ　αだけ
ウ　αとβだけ
エ　αとγだけ
オ　βだけ
カ　βとγだけ
キ　γだけ

c に関する解答群
ア　先頭
イ　1番目と2番目の間
ウ　2番目と3番目の間
エ　3番目と4番目の間
オ　4番目と5番目の間
カ　5番目と6番目の間
キ　6番目と7番目の間
ク　末尾

設問1　ア
設問2　(a) カ、(b) キ、(c) ウ

解説

本文中の整数型の意味と役割

図3. プログラム中の整数型の役割と意味

英単語帳が昇順で並ぶが、前提条件として、この配列が昇順でならんでいる理由

　本問題文に、「配列 eitan は常に昇順に並んでいる」という前提は、明示的に書かれていません。 しかし、文章中のヒントからそのルールを推測することができます。以下、どのように読み取るかを解説します。

1. 二分探索（バイナリサーチ）が使われている

　文章中には 「二分探索」 を用いると書かれています。

二分探索（バイナリサーチ）の前提条件

　二分探索は 配列が単調増加（または減少）に並んでいるときにのみ使える 探索手法です。
　無秩序な配列では二分探索は成立しないため、eitan が昇順にソートされていることが暗示されている のです。

2. 「挿入するときに後ろをずらす」処理

　文章中に 「ずらして挿入する」処理 があることが記述されています。
これは 「挿入後も特定の順序を維持する必要がある」 ことを示唆しています。

例えば、配列がランダムな順序で良いのであれば、
eitan[length] = 新単語; のように 末尾に追加するだけ で済むはずです。

しかし、「挿入時にずらす」処理があるということは、
　既存の並び順を壊さないようにしている → 昇順を維持している と推測できます。

3. 挿入の位置を決めるために探索を行う

文章の流れとして、
　「まず二分探索で挿入位置を探す → 必要ならずらす → 挿入する」 という処理が説明されています。

　これは、挿入するときに「どこに入れるか」を決める必要があるということを意味します。
　「適切な位置に挿入しないといけない」=「何らかの順序が存在する」=「昇順に並んでいる」 という推測ができます。

4. 既存の単語がある場合は「上書き」

　もし eitan にすでに登録されている単語 E が見つかった場合は、
その訳語を 上書き（αの処理） するようになっています。

このルールも、eitan において 単語が重複しない ことを示唆しています。
　つまり、eitan は 「一意な単語リスト」 であり、順序を守りながら格納されていることが分かります。

5. これらのヒントを総合すると……

　「eitan はアルファベット順に並んでいる」というルールが文中に明記されていなくても、以下の事実から推測できます。

  1. 二分探索（バイナリサーチ）を使う → 必ずソートされている配列である必要がある

  2. 挿入時にずらす処理がある → 順序を維持する必要がある

  3. 適切な位置を決める処理がある → 無秩序ではなく、特定のルール（昇順）がある

  4. 上書き処理がある → 各単語は一意であり、適切な位置で管理されている

結論

　「eitan が昇順である」ことは、明示的には書かれていないが、文中の処理から推測できるルールである。
　これは、アルゴリズムの問題ではよくあるパターンで、文章を細かく読み解くことで、前提条件を把握する力が求められます。

1. 昇順に並ぶとは？

　配列 eitan は常に昇順（A→Zの順番）に保たれる ルールになっています。
　つまり、新しく単語を追加するときも「アルファベット順」を守る必要があります。

　例えば、元の配列が以下のようになっているとします：

eitan = ["apple", "bread", "head", "program", "water"]

　このとき "computer" を追加すると、アルファベット順に並ぶようにしないといけません。
「bread」と「head」の間に "computer" を入れる必要があります：

eitan = ["apple", "bread", "computer", "head", "program", "water"]

2. β（ずらす処理）とは？

　新しい単語を 途中に挿入するとき は、単純にその場に入れるわけにはいきません。
　そのままだと既存の単語が上書きされてしまうからです。

　そのため、挿入位置より後ろにある単語をすべて1つ後ろにずらす（βの処理） が必要になります。

例：computer を追加

元の配列：

eitan = ["apple", "bread", "head", "program", "water"]

　「computer」は "bread" と "head" の間に入るべきなので、"head" 以降を1つ後ろにずらします：

eitan = ["apple", "bread", "head", "head", "program", "water"]  ← "head" を1つ後ろにずらす
eitan = ["apple", "bread", "head", "program", "program", "water"]  ← "program" もずらす
eitan = ["apple", "bread", "head", "program", "water", "water"]  ← "water" もずらす

　これで、eitan[2] に "computer" を入れる準備ができました。

3. γ（挿入処理）とは？

　ずらした後、空いたスペースに新しい単語を 実際に挿入 します。
　つまり、「ずらす」処理（β）の後に、「挿入」処理（γ）が行われる」 ということです。

例：computer を追加（続き）

eitan = ["apple", "bread", "computer", "head", "program", "water"]

　こうして "computer" の挿入が完了しました。

4. 探索（検索）→ ずらす（β）→ 挿入（γ）の流れ

  1. 二分探索で単語 E の位置を探す

    • 存在するなら yaku[k] を 上書き（α）

    • 存在しないなら、挿入すべき位置 k を決める

  2. もし E を追加するなら

    • k より後ろの要素をすべて1つずつ後ろにずらす（β）

    • E を k に挿入（γ）

5. まとめ

  • β（ずらす処理） は 途中に単語を挿入するとき に必要

  • γ（挿入処理） は 新しい単語を入れるとき常に必要

  • 探索 → ずらす（β） → 挿入（γ） の流れを理解すると、設問の答えがスムーズに出せる！

細かく解説

1. プログラムの動作の流れ

　ファイルから単語と訳語を読み込んだ後、以下の処理が実行されます。

  1. 二分探索で単語の位置を検索する

    • 配列 eitan に単語 E が存在するかを検索する。

    • もし E が既に eitan[k] にあるなら、その位置 k で yaku[k] を 上書き する。

    • もし E が存在しないなら、適切な位置 k を求めて 挿入 する。

  2. 単語が存在する場合（上書き処理）

    • if (E == eitan[k]) という条件が成り立つ場合
      → yaku[k] = J により、訳語が 上書き される。

  3. 単語が存在しない場合（挿入処理）

    • 配列 eitan に E がない場合、新しい単語 E を 適切な位置に挿入 する。

    • このとき、後続の要素を1つ後ろにずらす処理（β） が行われる。

    • ずらした後、新しい単語 E を挿入（γ） する。

2. 設問2の解答の導出

　では、具体的な例で考えてみましょう。
　もともとの eitan 配列は 昇順に並んでいる ので、設問1の「ア」の状態を初期配列とします。

(a) "program" の処理

  • "program" は既に eitan に存在する（設問1の「ア」より）。

  • if (E == eitan[k]) が成立し、訳語 yaku[k] が上書き されるだけ。

  • 挿入処理（βやγ）は 行われない。

  • 選択肢「イ（αだけ）」が正解。

(b) "computer" の処理

  • "computer" は配列に 存在しない ので、新しく追加する必要がある。

  • "computer" の挿入位置を二分探索で探すと、
    "bread" と "head" の間に入る（bread < computer < head）。

  • 挿入のために 後続の要素を1つ後ろにずらす（β） 必要がある。

  • その後、新しい単語 "computer" を挿入（γ） する。

  • 選択肢「カ（βとγ）」が正解。

(c) "zoo" の処理

  • "zoo" は "water" の後に入るため、配列の末尾に追加 すればよい。

  • 末尾に追加する場合、他の要素を動かす必要がないため γ（新規挿入）のみが実行 される。

  • 選択肢「キ（γだけ）」が正解。

3. 最終的な解答

  • 設問1 → ア

  • 設問2

    • (a) イ（αだけ）

    • (b) カ（βとγ）

    • (c) キ（γだけ）

まとめ

  • 上書き（α） は、単語がすでに存在する場合に yaku[k] を更新するだけ。

  • 挿入（β, γ） は、新しい単語を追加するときに使われる。

    • 途中に挿入する場合、後続の要素をずらす（β）が必要。

    • 末尾に追加する場合はそのまま（γのみ）。

　このように、プログラムの処理を 二分探索の結果に応じて分類 することで、解答を導くことができます。

補足
Java と Python でコーディング

　Java と Python で、eitan 配列を 昇順に保ちつつ、二分探索を用いた単語の挿入と上書き を行うプログラムを実装します。

📌 処理の概要

  1. 二分探索 で挿入位置を特定

  2. 既に単語が存在する場合は 上書き（αの処理）

  3. 存在しない場合は 挿入 し、以降の要素を 後ろにずらす（βとγの処理）

Java の実装

　Java では ArrayList を使って可変長配列として実装し、Collections.binarySearch を活用します。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class EitanDictionary {
    private ArrayList<String> words = new ArrayList<>();
    private ArrayList<String> meanings = new ArrayList<>();

    // 単語を挿入または上書き
    public void insertOrUpdate(String word, String meaning) {
        int index = Collections.binarySearch(words, word);

        if (index >= 0) {
            // 既に存在する → 上書き（αの処理）
            meanings.set(index, meaning);
            System.out.println("Updated: " + word + " → " + meaning);
        } else {
            // 新規挿入（βの処理）
            int insertPos = -index - 1;
            words.add(insertPos, word);
            meanings.add(insertPos, meaning);
            System.out.println("Inserted: " + word + " → " + meaning);
        }
    }

    // 辞書の内容を表示
    public void display() {
        for (int i = 0; i < words.size(); i++) {
            System.out.println(words.get(i) + " : " + meanings.get(i));
        }
    }

    public static void main(String[] args) {
        EitanDictionary dict = new EitanDictionary();
        dict.insertOrUpdate("apple", "りんご");
        dict.insertOrUpdate("banana", "バナナ");
        dict.insertOrUpdate("cherry", "さくらんぼ");
        dict.insertOrUpdate("banana", "黄色い果物"); // 上書きされる
        dict.insertOrUpdate("grape", "ぶどう");

        dict.display();
    }
}

Java のポイント

  • Collections.binarySearch() を利用し、O(log N) で検索

  • 見つかった場合 は上書き、見つからなかった場合 は -index - 1 を計算して挿入位置を決定

  • ArrayList を使い、要素の挿入時に自動で後続の要素をシフト

Python の実装

　Python では bisect モジュールを使って、リストを 昇順に保ちながら挿入 します。

import bisect

class EitanDictionary:
    def __init__(self):
        self.words = []
        self.meanings = []

    def insert_or_update(self, word, meaning):
        index = bisect.bisect_left(self.words, word)

        if index < len(self.words) and self.words[index] == word:
            # 既に存在する → 上書き（αの処理）
            self.meanings[index] = meaning
            print(f"Updated: {word} → {meaning}")
        else:
            # 新規挿入（βの処理）
            self.words.insert(index, word)
            self.meanings.insert(index, meaning)
            print(f"Inserted: {word} → {meaning}")

    def display(self):
        for word, meaning in zip(self.words, self.meanings):
            print(f"{word} : {meaning}")

# テスト
dict_obj = EitanDictionary()
dict_obj.insert_or_update("apple", "りんご")
dict_obj.insert_or_update("banana", "バナナ")
dict_obj.insert_or_update("cherry", "さくらんぼ")
dict_obj.insert_or_update("banana", "黄色い果物")  # 上書きされる
dict_obj.insert_or_update("grape", "ぶどう")

dict_obj.display()

Python のポイント

  • bisect.bisect_left() を使い、O(log N) で挿入位置を探索

  • 見つかった場合は上書き、見つからなかった場合は 適切な位置に挿入

  • list.insert() で 要素を後ろにずらして挿入（リストの昇順を維持）

Java と Python の比較

図4. 本プログラムにおけるJava とPython の違い

💡 まとめ

  • Java / Python ともに二分探索（O(log N)）で挿入位置を決定

  • 既存単語があれば上書き、なければ適切な位置に挿入

  • 配列は常に昇順に保たれる

  • Java は Collections.binarySearch、Python は bisect を活用

整数型の H, L, i, k, n について、それぞれの役割を整理します。
このプログラムは 二分探索を用いた挿入・上書き を行うものなので、それに沿って解説します。

追加補足

整数変数の役割

図4. 整数型の役割と意味

二分探索における変数の動き

  1. 初期化

    • L = 0（最初の要素）

    • H = n - 1（最後の要素）

  2. 二分探索を実行

    • i = (L + H) / 2（中央のインデックスを取得）

    • 比較対象の単語 eitan[i] と挿入したい word を比較

    • word が eitan[i] より小さいなら 左側を探索 (H = i - 1)

    • word が eitan[i] より大きいなら 右側を探索 (L = i + 1)

  3. 探索結果

    • word が eitan[i] に 一致する場合 → k = i にして上書き（αの処理）

    • word が 存在しない場合 → k = L にして挿入位置を決定（βの処理）

  4. 挿入処理（ずらして挿入）

    • eitan[k] 以降の要素を後ろにシフト（γの処理）

    • eitan[k] = word をセット

    • n を +1 して要素数を増やす

変数の役割まとめ

図5. 各整数型がプログラム中のどこで使われるか

💡 例

eitan = ["apple", "banana", "cherry", "grape"] に "blueberry" を挿入するとき

  • 初期 L = 0, H = 3 (n = 4)

  • 1回目の探索 → i = (0+3)/2 = 1（eitan[1] = "banana"）
    → "blueberry" は "banana" より後 → L = i + 1 = 2

  • 2回目の探索 → i = (2+3)/2 = 2（eitan[2] = "cherry"）
    → "blueberry" は "cherry" より前 → H = i - 1 = 1

  • L > H になったので k = L = 2 に挿入

  • "cherry" 以降の要素を 後ろにシフト

  • eitan[2] = "blueberry" をセット

  • n += 1 → eitan = ["apple", "banana", "blueberry", "cherry", "grape"]

🔹 まとめ

H, L, i, k, n はそれぞれ 二分探索と挿入処理 において 検索範囲の管理、挿入位置の決定、配列の拡張 を担っている。
特に k が 上書き or 挿入の分岐点 となることがポイント！

第3章は、整列アルゴリズムについて解説します。

以上です。

いいなと思ったら応援しよう！