アルゴリズムとプログラミング ざっくりまとめ（応用情報技術者試験）

対応するシラバスの範囲（応用情報技術者試験シラバス Ver.7.2）：大分類「基礎理論」の中分類2「アルゴリズムとプログラミング」

---

リスト

• 一言で言うと：
  • データを「順番に並べて持つ」2つの方法（配列と連結リスト）と、連結リストでの追加・削除の手間、リストで2分木を表す方法の話。

並べ方を選ぶ（配列か連結リストか）→ 出し入れする（先頭・末尾での追加と削除）→ 木も表せる（リストによる2分木）

覚え方の軸

• 配列は「場所が決まっている」、連結リストは「ポインタでつながっている」：
  • 配列は好きな場所をすぐ読めるが、途中の出し入れが遅い。連結リストはその逆
• 連結リストの種類は「ポインタの向き」で3つ：
  • 次だけ（単方向）、前と次（双方向）、最後が先頭に戻る（循環）
• HeadとTailをもつリストの処理量は「追加は先頭も末尾も同じ、削除だけ末尾が重い」：
  • 末尾を消すには、1つ手前の要素を探してHeadから順にたどる必要がある
• だからこのリストは「末尾に足して先頭から取る」キュー向き
• 2分木のノードは「自分のデータ＋親・左の子・右の子への3本のポインタ」

リストの実現方法：配列か、連結リストか

• リスト：
  • 順序づけられたデータの並び
  • 一般に「リスト」といったら連結リストを指すことが多い
• リストを表現する主なデータ構造は、配列と連結リスト
• 配列：
  • 個々の要素の位置を固定して、要素の番地（アドレス）を簡単に計算できるようにしたデータ構造
  • 同じ型のデータを、決まった個数だけ並べた形。記憶装置の連続した番地に順に格納するので、**要素番号（添字）**で直接アクセス（ダイレクトアクセス）できる
  • 長所：
    • 任意の要素を参照できる
  • 短所：
    • 挿入・削除のときは、その位置より後ろの要素を1つずつ後ろ（または前）にずらすので、処理効率が悪い
    • あらかじめ最大データ数分の領域を確保しておく必要があり、実際のデータが少ないと無駄が出る
• 連結リスト：
  • 各要素をポインタでつないだデータ構造
  • 長所：
    • 要素の追加・削除は、少しのポインタの付け替えだけでできる（例：単方向リスト「東京→大阪→福岡」から「大阪」を消すなら、「東京」のポインタ部に「大阪」のポインタ部の値（福岡のアドレス）を入れるだけ）
    • 使うデータの個数だけ動的に領域を確保できるので、無駄な領域が出ない（動的確保には、通常ヒープ領域を使う）
  • 短所：
    • 要素の位置が固定されていないので、要素番号を使った任意の要素の参照はできない
    • 要素ごとにポインタ部が別に要るので、データ1個あたりの記憶域は配列の方が小さい
• 連結リストの種類

種類	別名	ポインタのもち方
単方向リスト	片方向リンク、線形リスト	各要素が次の要素へのポインタをもつ。最後の要素は「次がない」
双方向リスト	双方向リンク	各要素が前と後ろの要素へのポインタをもつ
循環リスト	−	各要素が次の要素へのポインタをもち、末尾の要素は先頭要素へのポインタをもつ

• 各要素は、データ部とポインタ部でできている

連結リストにおける要素の追加と削除：先頭と末尾で手間が違う

• 試験では、**先頭要素へのポインタ（Head）と末尾要素へのポインタ（Tail）**をもつ連結リストが出る
  • ★試験では、リストの先頭と末尾での、要素の追加と削除の処理量が問われる
• 例のリスト：
  • Head → A → B → C → D（TailはDを指す）
• 要素の追加：
  • 先頭でも末尾でも処理量は同じ
  • 先頭にZを追加する手順：
    • ① Zのポインタ部に、HeadがもつAのアドレスを入れる → ② HeadにZのアドレスを入れる
  • 末尾にEを追加する手順：
    • ① TailからたどったDのポインタ部に、Eのアドレスを入れる → ② TailにEのアドレスを入れる
• 要素の削除（読み出したあとで削除）：
  • 先頭より末尾の方が処理量が多い
  • 先頭要素Aを削除する手順：
    • ① HeadからたどったAのポインタ部の値（Bのアドレス）をHeadに入れる（1手で終わる）
  • 末尾要素Dを削除する手順：
    • ① Headから順にCまでたどる → ② Cのポインタ部を**NULL（空値）**にする → ③ TailにCのアドレスを入れる
    • 末尾要素の削除にかかる時間は、要素数にほぼ比例する
    • 理由：
      • 単方向リストでは「1つ手前（C）」へ戻れないので、先頭から順にたどるしかない
• メモリリーク：
  • 動的に作ったリストでは、削除したデータの記憶領域を解放する必要がある。解放しないで不要な領域が増えると、使えるメモリがだんだん減っていく
• HeadとTailをもつリストの用途：
  • 「追加は末尾、取り出しは先頭」で行う**キュー（FIFO）**の実現に向いている
  • 先頭で追加と削除をするスタックとしても使えるが、その場合Tailは不要
  • リストでキューを作る場合、途中への要素の追加・削除は、単方向リストより双方向リストの方がやりやすい

操作	先頭	末尾
追加	ポインタ2か所の変更	ポインタ2か所の変更（同じ）
削除	Headを1か所変えるだけ（軽い）	手前までたどる必要がある（重い。要素数に比例）

リストによる2分木の表現：ポインタで親子をつなぐ

• リスト構造で2分木を表現できる
• ノードのデータ構造：
  • data（ノードのデータ値）、Parent（親ノードへのポインタ）、Left（左の子へのポインタ）、Right（右の子へのポインタ）
• 配列で表した例（「－」は指す先がないこと）

番号	data	P（Parent）	L（Left）	R（Right）
1	40	－	2	3
2	30	1	4	5
3	50	1	－	－
4	20	2	－	－
5	35	2	－	－

• 木の形：
  • 根が40、その左の子が30、右の子が50。30の左の子が20、右の子が35
• 親の子を指す書き方：
  • ノードnの親がもつ左の子へのポインタは Left［Parent［n］］、右の子へのポインタは Right［Parent［n］］
• ノードを追加する例：
  • データ値35のノードの右に、データ値37のノード（番号6）を追加するときは、次の2つを行う
  • 番号5（35）のRightに、番号6を指すポインタを入れる
  • 番号6（37）のParentに、番号5を指すポインタを入れる
  • ポイント：
    • 親から子へ、子から親への両方向を設定する

混同しやすいペア

• 配列（任意の要素をすぐ読める、挿入・削除は遅い、領域を最初に確保）／連結リスト（任意の要素は読めない、挿入・削除はポインタの付け替えだけ、動的に確保）
• 単方向リスト（次だけ）／双方向リスト（前と次）／循環リスト（末尾が先頭を指す）
• 先頭の削除（Headを付け替えるだけ）／末尾の削除（手前までたどる。要素数に比例）
• キューとして使う（Head・Tailとも必要）／スタックとして使う（Tailは不要）
• データ1個あたりの記憶域：
  • 配列の方が小さい（連結リストはポインタ部の分だけ大きい）

---

スタックとキュー

• 一言で言うと：
  • データの「取り出す順番」が決まった2つの入れ物の話。最後に入れたものから出すのがスタック、最初に入れたものから出すのがキュー。

2つの入れ物（スタックとキュー）→ 使い道（グラフの探索）→ 計算にも使う（逆ポーランド表記）

覚え方の軸

• スタックは「積み重ねた皿」、キューは「レジの行列」：
  • スタック＝LIFO（後入れ先出し）、キュー＝FIFO（先入れ先出し）
• 操作の名前は組で覚える：
  • スタックはPUSH／POP、キューはENQ／DEQ
• 探索との対応：
  • 深さ優先探索はスタック、幅優先探索はキュー
• 関数の呼び出しはスタック：
  • 戻り番地・引数・局所変数を積み、戻るときに取り出す（再帰もこれで動く）
• 逆ポーランド表記は「数字ならPUSH、演算子なら2つPOPして計算してPUSH」

スタックとキューの基本操作

• スタック：
  • 最後に入れたデータから順に取り出すLIFO（Last In First Out：後入れ先出し）方式
  • 挿入はPUSH（プッシュ）、取り出しはPOP（ポップ）。どちらも常に**最上段（頂上）**で行う
  • 配列かリストで実現する。配列なら、トップの位置を表す変数top（初期値0）だけで操作する
    • PUSH(x)：
      • top ← top＋1、S［top］← x
    • POP：
      • top ← top−1、S［top＋1］を返す
• スタックと関数呼び出し：
  • スタックは、**関数呼び出し（再帰的処理を含む）**の実現に欠かせない
  • 関数を呼ぶときに戻り番地、引数、局所変数をスタックに積み、戻るときに取り出して、実行途中の状態を管理する
  • 制御スタック：
    • 関数呼び出しのときに使うスタック。コールスタックともいう
  • スタックフレーム：
    • 関数ごとに積まれるデータのまとまり
  • スタックポインタ：
    • スタックの最上段の位置を指す
  • フレームポインタ：
    • スタックフレーム内の特定の位置を指す
• 局所変数：
  • 関数（手続）の中だけで使えるローカル変数
• グローバル変数：
  • プログラム（コンパイル単位）内の、どの手続からでも参照できる変数
• キュー：
  • 最初に入れたデータから順に取り出すFIFO（First In First Out：先入れ先出し）方式
  • 追加はいつも一方の端、取り出しはもう一方の端で行うので、一番古いデータから処理できる
  • 挿入はENQ（エンキュー）、取り出しはDEQ（デキュー）
  • 配列で作る場合、格納位置を表すxと処理位置を表すyを使う。配列の最後まで格納したら、先頭に戻る

	スタック	キュー
取り出す順	LIFO（後入れ先出し）	FIFO（先入れ先出し）
入れる操作	PUSH	ENQ
出す操作	POP	DEQ
例え	積み重ねた皿	レジの行列
主な用途	関数呼び出し、再帰、深さ優先探索、逆ポーランド記法の計算	幅優先探索、到着順の処理

• 例題：
  • 空の入れ物に「1を入れる → 2を入れる → 1つ出す → 3を入れる → 1つ出す → 1つ出す」を行う
  • スタックなら出てくる順は 2 → 3 → 1
  • キューなら出てくる順は 1 → 2 → 3

グラフの探索：深さはスタック、幅はキュー

• ある出発点から目的点までの経路を調べるときに、スタックやキューを使う
  • 深さ優先探索：
    • スタックを使う
    • 一般に、保持する情報が少なく、記憶域の消費が少ない効率のよい探索ができる
    • ただし局所的に探索していくので、最適な経路にならない場合がある
  • 幅優先探索：
    • キューを使う
  • 深さ優先探索と幅優先探索は、後の「木構造」でも詳しく扱う

スタックを使った演算（逆ポーランド表記）

• 逆ポーランド表記（後置表記）：
  • 演算子を数値（オペランド）の後ろに書く書き方
  • 例：
    • 算術式（4＋6）＊3 → 逆ポーランド表記 4 6 ＋ 3 ＊
• スタックを使い、左端から右へ順に、次の規則で計算できる
  • 規則1：
    • 数値（オペランド）を読んだら、スタックにPUSHする
  • 規則2：
    • 演算子を読んだら、スタックから2つPOPし、「後から取り出した数値 演算子 先に取り出した数値」を計算して、結果をPUSHする
• 上の例の手順：
  • 4、6をPUSH → 「＋」で6、4をPOPして4＋6＝10をPUSH → 3をPUSH → 「＊」で3、10をPOPして10＊3＝30をPUSH（これが答え）
• 例題：
  • 4 1 − 2 3 ＋ ＊ を計算する
  • 4、1をPUSH → 「−」で4−1＝3 → 2、3をPUSH → 「＋」で2＋3＝5 → 「＊」で3＊5＝15
  • 元の式は（4−1）＊（2＋3）
  • 注意：
    • 引き算・割り算は順番が大事。「4 1 −」は4−1（後から取り出した4から、先に取り出した1を引く）

混同しやすいペア

• スタック（LIFO、PUSH／POP）／キュー（FIFO、ENQ／DEQ）
• 深さ優先探索（スタック、記憶域が少ない、最適経路とは限らない）／幅優先探索（キュー）
• スタックポインタ（最上段を指す）／フレームポインタ（フレーム内の特定の位置を指す）
• 局所変数（関数の中だけ）／グローバル変数（どの手続からでも）
• 制御スタック（＝コールスタック。関数呼び出し用のスタック全体）／スタックフレーム（関数1回分のデータのまとまり）

---

木構造

• 一言で言うと：
  • データを「親子の階層」で持つ木の話。木の名前の付け方、完全2分木の数え方、木のたどり方、探しやすい木（2分探索木）と、その偏りを防ぐ木（バランス木）が出てくる。

木の部品と種類 → きれいな木を数える（完全2分木）→ 木をたどる（走査法）→ 探しやすい木（2分探索木）→ 偏らない木（バランス木）

覚え方の軸

• 木の用語は「家系図」で覚える：
  • 一番上が根、子がいないのが葉、根から下への枝の数が深さ
• 完全2分木の公式は「葉＝2のH乗、葉以外＝葉−1」：
  • 深さHなら葉は2ᴴ個、葉以外は2ᴴ−1個
• 走査は「節を見るタイミング」で3つ：
  • 先（節→左→右）、中（左→節→右）、後（左→右→節）。2分探索木を中間順でたどると昇順になる
• 2分探索木は「左は小さい、右は大きい」：
  • バランスがよければ比較回数はlog₂n、片側に偏るとn
• 偏りを防ぐのがバランス木：
  • 2分木ベースのAVL木（高さの差1以下）、多分木ベースのB木（外部記憶向け）

木の構造と種類：木の部品の名前

• 木（tree）：
  • データの親子関係など、階層的な構造を表すのに向いたデータ構造
• 木の部品
  • 節（ノード、節点）：
    • 図の○の部分
  • 枝（branch）：
    • 親子の節を結ぶ線。枝の上側の節が親、下側の節が子
  • 根（root）：
    • 親がない節
  • 葉（leaf）：
    • 子をもたない節
  • 根以外の節がもつ親は1つだけ。葉以外の節がもつ子の数には制限がない
  • 節の深さ：
    • 根からその節に着くまでの枝の数
  • 木の高さ：
    • 根から一番深い節までの深さ
  • 部分木：
    • ある節から下の部分も木になっている（例：根の右部分木）
  • 分節数：
    • 1つの節から出ている枝の数（＝子の数）。分節数が0の節は葉
• 子の数による分類
  • 2分木（2進木）：
    • 各節の子の数が高々2（2以下）の木
  • 多分木（n進木）：
    • 各節の子の数がn（n＞2）の木
• 順番に意味があるかによる分類
  • 順序木：
    • 親と子の間や、子どうしの間に何らかの順序が決まっている木。左右の子を入れ替えると別の木になる
  • 非順序木：
    • 順序がない木。子が左右どちらにあっても同じ（等価な）木
  • 例：
    • 根Aの下にB（左）とC（右）がある木と、C（左）とB（右）がある木は、BとCに順序関係があれば別の2分木、なければ同じ2分木

完全2分木：葉と節の数の公式

• 完全2分木：
  • 葉以外の節がすべて2つの子をもち、根から葉までの深さ（根から葉までの枝の個数）がすべて等しい木
• 葉の個数：
  • 深さごとの節数は 1（2⁰）→ 2（2¹）→ 4（2²）→ 8（2³）と倍々に増える
  • 木の深さがHなら、葉の個数＝2ᴴ
• 葉以外の節の個数：
  • 深さ0〜H−1の節の合計＝2⁰＋2¹＋…＋2ᴴ⁻¹
  • これは初項1（＝2⁰）、公比2の等比数列の和なので
  • 式：
    • 初項×（1−公比ᴴ）÷（1−公比）＝ 2⁰×（1−2ᴴ）÷（1−2）＝ 2ᴴ−1
• 等比数列：
  • 隣り合う2項の比が一定の数列。例：
    • 2、6、18、54、… は初項2、公比3の等比数列
• ★試験では、完全2分木の葉の個数と葉以外の節の個数の関係が問われる
  • 葉の個数＝2ᴴ
  • 葉以外の節の個数＝2ᴴ−1
  • 葉の個数がnなら、葉以外の節の個数はn−1
• 例題：
  • 深さH＝3の完全2分木
  • 葉の個数＝2³＝8
  • 葉以外の節の個数＝2³−1＝7（1＋2＋4＝7で検算OK）
  • 節の総数＝8＋7＝15
• 例題2：
  • 葉が64個の完全2分木の、葉以外の節の個数は？
  • 64−1＝63（64＝2⁶なので深さは6）

2分木の走査法（巡回法）：木をどの順にたどるか

• 走査（巡回）：
  • 木の各節を1つずつ調べること。系統的な方法に幅優先探索と深さ優先探索がある
• 例の木の形：
  • 根A、Aの左の子B、右の子C。Bの左の子D。Cの左の子E、右の子F
• 幅優先探索（幅優先順）：
  • 根に近い節から順に調べる。同じ深さの節は「左→右」の順
  • 例の木：
    • A→B→C→D→E→F
  • 配列で表すと楽：
    • 先頭要素A［1］を根とし、A［i］の左の子をA［2i］、右の子をA［2i＋1］とした配列を、先頭から順に調べれば幅優先探索になる
• 深さ優先探索（深さ優先順）：
  • 根から葉へ向かって、できるだけ分岐せずに枝をたどり、葉に着いたら1つ前の節に戻って、もう一方をたどる
  • 節の値を調べるタイミングで3つに分かれる

方法	別名	調べる順	例の木の結果
先行順	行きがけ順	節 → 左部分木 → 右部分木	A→B→D→C→E→F
中間順	通りがけ順	左部分木 → 節 → 右部分木	D→B→A→E→C→F
後行順	帰りがけ順	左部分木 → 右部分木 → 節	D→B→E→F→C→A

• 3つの子だけの木（根A、左B、右C）で覚える
  • 先行順：
    • A→B→C（節Aを調べてから、子を順に）
  • 中間順：
    • B→A→C（最初の子を調べてから節A、その後に残りの子）
  • 後行順：
    • B→C→A（子をすべて調べてから節A）
• 覚え方：
  • 「先・中・後」は節（親）を見るのが、先か、真ん中か、後か

2分探索木：左は小さく、右は大きく

• 2分探索木：
  • 2分木の各節に大小比較できるデータをもたせた木。どの節nから見ても、左部分木（左子孫節）のデータはすべて節nより小さく、右部分木（右子孫節）のデータはすべて節nより大きい
  • 例：
    • 根50、左の子30（その子が20と40）、右の子70（その右の子が80）
  • 2分探索木を深さ優先探索の中間順でたどると、昇順に整列されたデータが得られる
    • 例の木なら 20→30→40→50→70→80
• 2分探索木での探索：
  • 根のデータと探すデータを比べ、探すデータが小さければ左部分木へ、大きければ右部分木へ進む。これを、見つかるか、進む節がなくなるまで繰り返す
• 探索の計算量：
  • 枝分かれしている節の深さで決まる
  • 最良（要素数nの完全2分木のように左右のバランスがよい）：
    • 最大比較回数は log₂n
  • 最悪（片方だけに偏った木）：
    • 最大比較回数は n
  • log₂nになる理由：
    • 最大比較回数をSとすると、n個の要素を半分、さらに半分…とS回絞るので、n＝2ˢ。よってS＝log₂n
  • ★試験では、最良と最悪の計算量の式が問われる。どんなときに最悪になるか（片側に偏ったとき）も問われる
• 例題：
  • 要素数1,024（＝2¹⁰）の2分探索木で、最良なら最大比較回数は log₂1024＝10回。片側に偏った最悪の木なら最大1,024回
• 例（データ10を探す）
  • バランスのよい木（根40、その下に20と60、さらに10・30・50・70）：
    • 40 → 20 → 10 と進むので、比較回数＝3回
  • 偏った木（70→60→50→40→30→20→10と一直線）：
    • 比較回数＝7回
• 節の挿入：
  • 挿入するデータを、探索と同じ方法で根から順にたどり、たどる部分木がなくなったところに挿入する
  • 挿入するデータが複数あるときは、挿入の順序によって木の形が変わる
  • 例（根50、左30、右70、30の子が20と40の木に、45 → 42 の順に挿入）：
    • 45は 50→30→40 とたどり、40の右に部分木がないので40の右に入る。次に42は 50→30→40→45 とたどり、45の左に部分木がないので45の左に入る
    • 42 → 45 の順に挿入すると、42が40の右に、45が42の右に入るので、別の形になる
• 節の削除（★削除する節の状態で処理が変わる）
  • 葉の場合：
    • 単純にその葉を削除する
  • 左右どちらかの部分木しかもたない場合：
    • 削除する節を、その子で置き換える
  • 左右両方の部分木をもつ場合：
    • 削除する節を、左部分木の最大値の節か、右部分木の最小値の節で置き換える
  • 例（根50、左30（子20・40）、右70（左の子60））：
    • 葉の40を消す → そのまま消す
    • 左の子60だけをもつ70を消す → 60で置き換える
    • 両方の子をもつ根50を消す → 左部分木の最大値40か、右部分木の最小値60で置き換える
  • 理由：
    • 左の最大値か右の最小値なら、置き換えても「左は小さい、右は大きい」のルールが崩れない

バランス木：偏らないように組み直す木

• 2分探索木は、1回の比較で左右どちらを探せばよいかが決まる。だから左右のバランスがよいと速く、悪いと遅い
• バランス木（平衡木）：
  • 根から葉までの深さがほぼ一定になるように作られた木
  • 要素の追加や削除でバランスが悪くなったら、バランスを保つように木を再構成する機能をもつ
  • 2分木をベースにしたAVL木と、多分木をベースにしたB木がある
• AVL木：
  • どの節でも、左右の部分木の高さの差が1以下の木
  • 例：
    • 左右部分木の高さの差が2になる節が1つでもあれば、AVL木ではない
  • 再構成の方法には1重回転と2重回転がある
  • 1重回転の例：
    • 根50（左30（子20・40）、右60）に10を追加すると、10は20の左に入り、根50から見て左が深くなりすぎる（左の高さ2、右の高さ0）
    • 左部分木の根30を中心に、木全体を右方向に回転させる → 根が30、左20（左の子10）、右50（子40・60）になり、高さの差が1以下に戻る
• B木：
  • 外部記憶装置にデータを格納するために考えられた、多分木のデータ構造
  • 実現方法はいろいろあり、2分探索木のように各節にデータをもたせる方法もある。ここでは、データは葉だけに入れ、葉以外の節には枝と枝の境目を示すキーの値だけをもたせるB木で説明する（上が索引部、葉がデータ部のイメージ）
  • 節のデータ構造：
    • p0 k1 p1 k2 p2 … kn pn
    • 1つの節にキーをn個まで入れられる（nは偶数）
    • p0〜pnには子へのポインタが入る
    • k1〜knは、節の中で昇順に並んでいる
  • ポインタが指す部分木のキーの範囲
    • p0の先：
      • すべてk1より小さい
    • pi（1≦i＜n）の先：
      • すべてkiより大きく、ki＋1より小さい
    • pnの先：
      • すべてknより大きい
  • キーの探索：
    • 2分探索木とほぼ同じ。根から順に、節のキーと探すキーを比べてポインタをたどる
  • 新しいキーの挿入（1つの節にキーが2個までの例）：
    • 根［50］、左の葉が［20, 35］、右の葉が［70］のB木に42を入れる
    • 入れる先の［20, 35］は満杯なので、新しい節を作り、20、35、42を昇順に並べて分割し直す
    • 中央のキー35を、新しい節へのポインタと一緒に親の節の適切な位置に入れる → 親は［35, 50］、葉は［20］［42］［70］になる
• B木の種類
  • B＊木：
    • ①データを葉に入れ、葉以外の節にキーを入れる ②節が満杯のとき、兄弟節が空いていればそれを使い、2つの兄弟節がどちらも満杯のときに分割する
  • B＋木：
    • B＊木で、最下位の葉どうしをポインタで結んだもの。B＋木を使ったインデックスをB＋木インデックスという（データベースのインデックスで使われる）

混同しやすいペア

• 根（親がない）／葉（子がない）
• 節の深さ（根からその節までの枝の数）／木の高さ（根から一番深い節までの深さ）
• 2分木（子が2以下）／多分木（子がn個、n＞2）
• 順序木（左右を入れ替えると別の木）／非順序木（入れ替えても同じ木）
• 完全2分木の葉（2ᴴ）／葉以外の節（2ᴴ−1）
• 先行順（節→左→右）／中間順（左→節→右）／後行順（左→右→節）
• 行きがけ順＝先行順／通りがけ順＝中間順／帰りがけ順＝後行順
• 幅優先（根に近い順、キュー）／深さ優先（行けるところまで下る、スタック）
• 2分探索木の最良（log₂n）／最悪（n、片側に偏った木）
• AVL木（2分木ベース、高さの差1以下）／B木（多分木ベース、外部記憶向け）
• B＊木（兄弟節の空きを使う）／B＋木（葉どうしをポインタでつなぐ）

---

探索アルゴリズム

• 一言で言うと：
  • たくさんのデータの中から目的のデータを探す3つの方法（端から順に、半分ずつ、場所を計算して一発で）と、その速さを表す「オーダ」の話。

端から順に探す（線形探索法、番兵法）→ 半分ずつ絞る（2分探索法）→ 場所を計算する（ハッシュ法）→ 速さの物差し（オーダ）

覚え方の軸

• 3つの探索法は「1回の比較でどれだけ絞れるか」で並ぶ：
  • 線形探索は1個ずつ（O(n)）、2分探索は半分ずつ（O(log n)）、ハッシュは計算で一発（理想はO(1)）
• 前提条件の違い：
  • 線形探索は並んでいなくてもよい、2分探索は整列済みが必要、ハッシュはハッシュ関数が必要
• ハッシュは「ぶつかったとき（シノニム）にどうするか」で2つ：
  • 空いている隣を探す（オープンアドレス法）、リストでつなぐ（チェイン法）
• オーダは「一番増え方の大きい項だけ残す」：
  • O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²) ＜ O(2ⁿ) ＜ O(n!)

線形探索法と2分探索法：端から順か、半分ずつか

• 線形探索法（逐次探索法）：
  • 探索対象データの先頭から順に探す
  • データがn個のとき、最小比較回数は1回、最大比較回数はn回、平均比較回数は （n＋1）／2回
  • nが十分大きいときの平均比較回数は n／2 と考える
  • 計算量のオーダは O(n)
    • 意味：
      • 探索にかかる時間が、データの個数nに比例する
• オーダ：
  • アルゴリズムが答えを出すまでに、どれくらいの計算時間が必要かを表す概念（後の「オーダ」で詳しく扱う）
• 番兵法：
  • 線形探索の終了判定は、ふつう「見つかったか」と「最後まで探したか」の2つ。比較のたびに2つ判定するのは時間の無駄
  • そこで、探すデータと同じデータ（番兵）を末尾に追加し、終了判定を「見つかったか」だけにする
  • 例：
    • 6 2 9 4 7 3 の末尾A［7］に、探すデータ5を番兵として置く。A［1］〜A［6］になくても、A［7］で必ず一致する（A［7］で見つかったら「データはなかった」と判断する）
  • 番兵を使っても計算量のオーダは変わらないが、終了判定が1つになって実行ステップ数が減るので、実際の速度は上がる
• 2分探索法：
  • 大小比較を使う探索法の中で、一番シンプルなもの
  • 昇順か降順に整列されたデータにしか使えない
  • 整列されたデータの中央の位置midの値（中央の値）と探すデータを比べる
    • 探すデータ＞中央の値：
      • 次はmidより右を探す
    • 探すデータ＜中央の値：
      • 次はmidより左を探す
  • 1回の比較ごとに探索範囲が1／2になるので、n個ならlog₂n回比べれば範囲が1以下になって終わる
  • 計算量のオーダは O(log₂n)。底の2を省略して O(log n) と書くことが多い
  • log₂nになる理由：
    • データが1つになるまでの比較回数をaとすると 2ᵃ＝n。2を底とする対数をとって a＝log₂n
• 線形探索法との比較：
  • 一般に2分探索法の方が効率がよい
  • 例：
    • 整列された1,000個のデータなら、線形探索は平均で約500回、2分探索は約10回
    • log₂1,000＝log₂10³＝3×log₂10 ≒ 3×3.32＝9.96
  • 注意：
    • 2分探索法がいつも速いとは限らない。探すデータが先頭にあれば、線形探索の方が断然速い

	線形探索法	2分探索法
前提	並んでいなくてよい	整列済みであること
最大比較回数	n回	約log₂n回
平均比較回数	（n＋1）／2回	約log₂n回
オーダ	O(n)	O(log n)

• 例題：
  • 整列済みの1,024件から探す
  • 線形探索の平均比較回数：
    • （1,024＋1）÷ 2 ≒ 512回
  • 2分探索の最大比較回数：
    • log₂1,024＝10回（1,024＝2¹⁰）

ハッシュ法：キーから格納場所を計算する

• ハッシュ法：
  • 探すデータのキー値から、データの格納場所（アドレス）を直接計算する方法
  • 長所：
    • 一意探索（1件を探す）に優れていて、線形探索法や2分探索法より探索時間が短い
  • 短所：
    • 連続したデータの探索（範囲の探索）には向かない
• ハッシュ関数：
  • 格納場所の計算に使う関数
• ハッシュ値（ハッシュアドレス）：
  • キー値からハッシュ関数で求めた値
• 値域：
  • ハッシュ関数から得られる値の範囲
• 衝突（シノニムの発生）：
  • 異なるキー値から、同じハッシュ値が求められること
  • 理想は「異なるキーから同じハッシュ値は出ない」ことだが、実現は難しい。どんなハッシュ関数を使っても、シノニムの発生は防げない
• シノニム：
  • 衝突が起きて、本来入れるべき場所に入れられないデータ
• ホーム：
  • その場所に先に入っているデータ
• シノニムを最少にするには、ハッシュ値が偏らない一様分布になるようなハッシュ関数を選ぶ
• 探索時間とデータ数の関係（★試験では「データ数と探索時間の関係を表すグラフ」が問われる）
  • シノニムが発生しないなら、データ1個あたりの探索時間は、データの個数に関係なく一定（横一直線のグラフ）
  • シノニムが発生するなら、探索時間は格納領域の使用率に左右される
• 例題：
  • ハッシュ関数を「キー値を5で割った余り」とする
  • キー12 → 12÷5＝2余り2、キー17 → 17÷5＝3余り2
  • どちらもハッシュ値2なので**衝突（シノニム）**が起きる
• シノニムが起きたときの対策は2つ
• オープンアドレス法：
  • シノニムが起きたら、別のハッシュ関数で再ハッシュする
  • 一般には「求めたハッシュ値＋1」を新しいハッシュ値にし、空いていればそこに入れ、空いていなければ同じ操作で次を探す。最後まで行っても見つからなければ先頭に戻って探す
  • ハッシュ表は環状につながっていると考えて後ろの空きを順に探す。空き要素が1つだけになったら、格納せずにオーバフローとする
  • 上の例題なら、キー17はハッシュ値2が埋まっているので、2＋1＝3番に入れる
  • クラスタリング：
    • 使用中の要素が連続する現象
  • 問題点：
    • 要素番号3〜6が連続して埋まっていると、6番のデータは本当はハッシュ値3〜5のデータが後ろにずれて入ったものかもしれない
    • 全部ハッシュ値3なら、途中の5番を削除すると、6番のデータが探索できなくなる（3から順に見ていって、空いた5番で「ない」と判断してしまう）
    • そのため削除したときは、探せなくなるデータを1つずつ前にずらす処理が必要
• チェイン法（チェーン法、連鎖法）：
  • 同じハッシュ値をもつデータを、ポインタでつないだリストとして格納する
  • 例：
    • データPとデータQが同じハッシュ値5なら、ハッシュ表の5番にはPへのポインタを入れ、QはPの次にポインタでつなぐ
• チェイン法の探索の計算量：
  • 全データ数N、ハッシュ表の大きさM、各リストの長さがほぼN／M個とする
  • ハッシュ値hを求め、ハッシュ表［h］（ハッシュ表のh番目の要素）が指すデータからリストを順にたどる
  • 比較回数は最小1回、最大N／M回。計算量はN／Mで決まる
  • Mが大きければ計算量は少なく、小さければ多い
  • Mを、データ数Nに対して十分大きくすれば、計算量は最良の**O(1)**になる
  • 例：
    • N＝1,000件、M＝100なら、1本のリストは約10件なので、最大で約10回の比較

	オープンアドレス法	チェイン法
衝突したら	再ハッシュ（一般に＋1）して空きを探す	同じハッシュ値のデータをリストでつなぐ
格納場所	ハッシュ表の中だけ	ハッシュ表＋リスト
注意点	クラスタリング、削除時に前へずらす処理が必要	計算量はN／Mで決まる

オーダ（order）：O記法

• オーダ：
  • アルゴリズムの評価に使う計算量の表し方の一つ
• 計算量の種類
  • 時間計算量：
    • 答えを出すまでにどれくらいの時間がかかるか
  • 領域計算量：
    • どれくらいの**領域（メモリ）**が要るか
  • 単に「計算量」といったら、時間計算量のことが多い
• オーダ記法：
  • データ数nが増えると計算量がどう増えるか、上限はどれくらいか、という計算量の概要（漸近的な振舞い）を、**O（ビッグオー）**の記号で表す
  • 計算量をnの関数で表し、定数や係数を除き、nについて最も速く増える項だけで評価する
  • 例：
    • f(n)＝2n²＋5n＋3 なら O(n²)
    • g(n)＝log₂n なら O(log n)
    • O(n²)とO(log n)の2つの部分からなるなら、全体はO(n²)＋O(log n)だが、**O(n²)**に簡略化する
• 大小関係（覚える）：
  • O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²) ＜ O(2ⁿ) ＜ O(n!)
• オーダを求める2つの規則
  • 規則1（順次処理）：
    • 順に並んだ部分は、大きい方のオーダが全体のオーダになる
  • 規則2（繰返し処理）：
    • 繰り返す部分のオーダに繰返し数を掛けたもの（定数は無視）が全体のオーダになる
  • 例：
    • O(n)の処理をn回繰り返すなら O(n²)。O(log n)の処理をn回繰り返すなら O(n log n)
• 例題：
  • n＝1,024のときの目安
  • log₂n＝10、n＝1,024、n log₂n＝10,240、n²＝1,048,576（約100万）
  • オーダが1つ上がると、計算量が大きく変わることがわかる

混同しやすいペア

• 線形探索法（先頭から順、O(n)、整列不要）／2分探索法（半分ずつ、O(log n)、整列が必要）
• 平均比較回数：
  • 線形探索は（n＋1）／2（nが大きければn／2）、2分探索は約log₂n
• 番兵法（実行ステップ数が減る）／オーダ（番兵法を使っても変わらない）
• シノニム（衝突して入れない側のデータ）／ホーム（先にその場所に入っているデータ）
• オープンアドレス法（＋1して空きを探す）／チェイン法（リストでつなぐ、連鎖法）
• 時間計算量（時間）／領域計算量（メモリ）
• ハッシュ法の得意（一意探索）／不得意（連続したデータの探索）

---

整列アルゴリズム

• 一言で言うと：
  • データを小さい順（または大きい順）に並べ替える方法の話。遅いが単純な3つの基本整列法と、速い3つの整列法（クイック、ヒープ、マージ）、その考え方と計算量・安定性が出てくる。

基本の3つ（バブル・選択・挿入）→ 考え方で分ける（逐次添加・分割統治・データ構造）→ 速い3つ（クイック・ヒープ・マージ）

覚え方の軸

• 速さで2グループ：
  • 基本整列法（バブル、単純選択、単純挿入）はO(n²)、高速整列法（クイック、ヒープ、マージ）はO(n log n)
• 基本3つは「何をするか」の動詞で区別：
  • バブル＝隣と交換、選択＝最小を選んで先頭へ、挿入＝正しい位置に差し込む
• 安定かどうかの○×：
  • 安定＝バブル、単純挿入、マージ。安定でない＝クイック、ヒープ（単純選択は実装しだい）
• 例外を押さえる：
  • 単純挿入は最良O(n)（ほぼ整列済みに強い）、クイックは最悪O(n²)（整列済みで最小・最大を基準値にしたとき）
• 考え方は3つ：
  • 1つずつ増やす（逐次添加法）、分けて解く（分割統治法：クイック・マージ）、データ構造を使う（ヒープ）

基本的な整列アルゴリズム：遅いけれど単純な3つ

• 整列（ソート）：
  • 1列に並んだデータを、ある規則に従って並べ替える処理
• 安定な整列：
  • 同じキー値をもつデータの順序が、整列の前と後で変わらないもの
  • 基本整列法のうち、バブルソートと単純挿入法は安定
  • 単純選択法は、実装するアルゴリズムしだいで安定にもできる
• 3つの基本整列法

整列法	別名	やり方
バブルソート	隣接交換法	隣り合う要素を比べ、大小が逆なら交換する。交換が要らなくなるまで繰り返す
単純選択法	最小値（最大値）選択法	未整列の中から一番小さい（大きい）要素を選び、未整列部分の先頭と入れ替える。最後から2番目に正しい要素が入るまで繰り返す
単純挿入法	−	未整列の先頭の要素を取り出し、整列済みの中の正しい位置に挿入していく

• バブルソートの例（7 4 9 5 を昇順に）：
  • 1回目：
    • 7と4を交換 → 4 7 9 5、7と9はそのまま、9と5を交換 → 4 7 5 9（最大値9が末尾に決まる）
  • 2回目：
    • 7と5を交換 → 4 5 7 9
  • 3回目：
    • 比べても交換なし 4 5 7 9
• 単純選択法の例（7 4 9 5 を昇順に）：
  • 最小値4を見つけて先頭と交換 → 4 7 9 5
  • 残りから最小値5を見つけて2番目と交換 → 4 5 9 7
  • 残りから最小値7を見つけて3番目と交換 → 4 5 7 9
• 単純挿入法の例（7 4 9 5 を昇順に）：
  • 7を整列済みとみなす
  • 7と4を比べ、4を正しい位置に挿入 → 4 7 9 5
  • 7と9を比べ、順が正しいのでそのまま → 4 7 9 5
  • 9と5を比べ、逆なので5を1つずつ前と比べて正しい位置に挿入 → 4 5 7 9
• シェルソート（改良挿入法）：
  • 一定の間隔おきに取り出した要素の部分列を、それぞれ単純挿入法で整列し、間隔を狭めて同じ操作を繰り返す。間隔が1になるまで続ける
• 計算量（整列の計算量は比較回数で評価する）
  • バブルソートと単純選択法の比較回数は、データ数nのとき n(n−1)／2回 → O(n²)
  • 単純挿入法の比較回数は、最悪 n(n−1)／2回、最良 n−1回
  • 単純挿入法の計算量は、平均と最悪がO(n²)、最良がO(n)
  • 元のデータがほぼ正しい順に並んでいると、単純挿入法の計算量はO(n)に近くなる
• 例題：
  • データ数10のバブルソートの比較回数は 10×9÷2＝45回
  • 単純挿入法なら、すでに整列済みのとき（最良）は 10−1＝9回
• 計算量が n log₂n、つまり O(n log n) の高速な整列法として、クイックソート、ヒープソート、マージソートがある（後述）

整列法の考え方：3つの発想

• データ整列法の考え方は、大きく分けて逐次添加法、分割統治法、データ構造の利用の3つ
  • このほかにランダム化法という考え方もある
• 逐次添加法：
  • n個を整列する途中で、（k−1）個が整列済みのとき、1つの要素を加えて整列済みをk個にする。これをk＝2、3、4、…、nまで繰り返す
  • バブルソート、単純選択法、単純挿入法がこの考え方
• 分割統治法：
  • 大きな問題を小さな問題に分割し、それぞれの解を結合して全体の解を求める考え方
  • 分割とは、対象の集合や定義域を分けること。分割処理の多くは再帰的な処理で行う
  • クイックソートとマージソートがこの考え方
• データ構造の利用：
  • 整列の効率を上げるためにデータ構造を使う考え方
  • 一番代表的なのがヒープソート
  • 単純挿入法でも、整列済みのデータを2分探索木で表せば、計算量をO(n log n)に抑えられる
  • 二分挿入法：
    • 挿入する場所を2分探索法で探す方法

高速な整列アルゴリズム：速い3つ

• クイックソート：
  • 整列対象から中間的な基準値を選び、それより小さい値の区分と大きい値の区分に振り分けて分割する。分割した区分ごとに再帰的にクイックソートを行い、データ数が1つになるまで繰り返す
  • 基準値は、軸またはピボット（pivot）ともいう
  • 分割統治法の考え方。高速だが、安定ではない
  • 平均計算量はO(n log n)
  • ★最悪はO(n²)：
    • あらかじめ整列されたデータに対して、最小値か最大値を基準値にした場合（分割が片寄って、毎回1個しか減らない）
    • 試験では「どんなときに計算量が最悪になるか」が問われる
  • 安全クイックソート：
    • 最悪でもO(n log n)に抑える方法の一つ。再帰呼出しの回数（段数）が一定を超えたらヒープソートに切り替える
  • 例（15 9 18 12 20 8 6、基準値12）：
    • 12より小さい「9 8 6」と、大きい「15 18 20」に分ける
    • それぞれ基準値8、18で同じことを繰り返す → 6 8 9 12 15 18 20
• ヒープソート：
  • ヒープ：
    • 各節に「親のデータ≦子のデータ」（またはその逆）の関係をもたせた順序木
    • ヒープは完全2分木か、完全2分木の葉を右からいくつか取り除いた形になる
    • 親と子の間にだけ順序が決まっていて、兄弟どうしには決まりがないので、厳密には半順序木
  • 降順に整列する手順：
    • 未整列のデータで「親≦子」のヒープを作り、配列で表す → ヒープの根（配列の先頭）にある最小値を取り出して整列済みの部分に移す → ヒープを再構成する。この「根の取り出し → ヒープの再構成」を繰り返して、未整列部分を縮めていく
    • 昇順に整列するときは、「親≧子」のヒープを作る
  • 配列での表し方：
    • 根をT［1］に置き、T［i］の左の子をT［2×i］、右の子をT［2×i＋1］に置く
  • 高速で、どんなデータ列でも計算量はO(n log n)で変わらない。ただし安定ではない
  • ヒープの再構成の例（T＝3 6 10 9 14 16 11）：
    • 根の3を取り出し、ヒープの最後のデータ11を根に移す（空いたところには取り出した3を整列済みとして入れる）→ 11 6 10 9 14 16 ｜3
    • 11より小さい子（6と10）があるので、小さい方の子6と交換 → 6 11 10 9 14 16
    • 11より小さい子（9と14のうち9）があるので、9と交換 → 6 9 10 11 14 16。これで「親≦子」が回復
  • ヒープソートの処理概要
    • ① nにヒープの大きさ（節数）を入れる
    • ② nが1になるまで、③〜⑥を繰り返す
    • ③ T［1］とT［n］を入れ替える
    • ④ nを1減らす（ヒープを1つ小さくする）
    • ⑤ rに1を入れる
    • ⑥ T［r］より小さい値の子がある間、小さい方の子とT［r］を交換し、rに交換した子の添字を入れる（⑤⑥がヒープの再構成）
  • 最初にヒープを作る処理：
    • ① i＝節数÷2 ② i＜1になるまで、T［i］を根としてヒープを再構成し、iを1減らす
    • 例：
      • 節数7なら、i＝3、2、1の順に再構成する（葉ではない節を、下の方から順に整える）
• マージソート：
  • 整列対象のデータ列の分割と**併合（マージ）**を繰り返し、最後に1つの整列済みデータ列を作る
  • 大きさが1になれば、整列済み（整列完成）とみなす。分割する大きさmは場合によって違う（ここではm＝1）
  • 例（6 3 8 1）：
    • 前半「6 3」と後半「8 1」に分割（①）→ 前半を「6」「3」に分割（②）→ 併合して「3 6」（④）→ 後半を「8」「1」に分割（③）→ 併合して「1 8」（⑤）→ 全体を併合して「1 3 6 8」（⑥）
    • 前半 → 後半の順に再帰的に処理するので、処理順は ①→②→④→③→⑤→⑥
  • 分割統治法の考え方で、再帰処理を使う
  • **どんなデータ列でも計算量はO(n log n)**で、安定
  • データ数の半分程度の作業領域が必要
  • 外部記憶装置上の大量のデータの整列に使われる

整列法	平均	最悪	安定	考え方・特徴
バブルソート	O(n²)	O(n²)	○	逐次添加法。隣と交換
単純選択法	O(n²)	O(n²)	実装しだい	逐次添加法。最小を選ぶ
単純挿入法	O(n²)	O(n²)	○	逐次添加法。最良O(n)
クイックソート	O(n log n)	O(n²)	×	分割統治法。基準値で分ける
ヒープソート	O(n log n)	O(n log n)	×	データ構造の利用
マージソート	O(n log n)	O(n log n)	○	分割統治法。作業領域が要る

混同しやすいペア

• バブルソート（隣と交換）／単純選択法（最小を選んで先頭と入れ替え）／単純挿入法（正しい位置に差し込む）
• 安定（バブル、単純挿入、マージ）／安定でない（クイック、ヒープ）
• クイックソート（平均O(n log n)、最悪O(n²)）／ヒープソート・マージソート（いつもO(n log n)）
• 単純挿入法の最良（O(n)、ほぼ整列済み）／クイックソートの最悪（O(n²)、整列済みで最小・最大を基準値にしたとき）
• 逐次添加法（バブル、選択、挿入）／分割統治法（クイック、マージ）／データ構造の利用（ヒープ）
• 降順のヒープソート（親≦子のヒープ、最小値を取り出す）／昇順のヒープソート（親≧子のヒープ）
• シェルソート（間隔を空けて挿入法、改良挿入法）／二分挿入法（挿入位置を2分探索で探す）
• 安全クイックソート（深くなったらヒープソートに切り替える）

---

再帰法

• 一言で言うと：
  • 関数の中で自分自身を呼び出す「再帰」の話。階乗や最大公約数のような計算と、木の探索で使う例が出てくる。午前の頻出計算問題があるテーマ。

再帰関数の定義（階乗、最大公約数）→ 木の探索で使う（探索関数）

覚え方の軸

• 再帰関数は「止まる条件」と「1つ小さい自分を呼ぶ式」の2つでできている：
  • 階乗なら、n＝0で1を返す（止まる）、それ以外はn×f(n−1)（自分を呼ぶ）
• 再帰は「下りて行って、帰りに計算する」：
  • f(3) → f(2) → f(1) → f(0)と呼び出し、f(0)＝1が返ってきてから、1 → 1 → 2 → 6と掛け算していく
• 計算問題は「式に数字を入れて1行ずつ書き下す」だけ：
  • F(252, 105)のような問題は、止まる条件（y＝0）になるまで書き換える
• 木は再帰的な構造なので、再帰と相性がよい：
  • 左（右）部分木を探すには、左（右）の子へのポインタを引数にして自分を呼ぶ

再帰関数：自分で自分を呼ぶ関数

• 再帰関数：
  • 関数の定義の中で、自分自身を使って定義する関数
• 階乗関数（n！）：
  • 再帰関数の代表
  • n！＝n×（n−1）×（n−2）×…×2×1
  • 定義1（プログラムの形）：
    • f(n)：if n＝0 then return 1 else return n×f(n−1)
    • 受け取ったnが0なら1を返し、それ以外ならn×(n−1)！を返す
  • 定義2（数式の形）：
    • n＞0のとき f(n)＝n×f(n−1)、n＝0のとき f(n)＝1
• 漸化式：
  • 定義2のような式。f(1)、f(2)、…、f(n)、…という関数の列で、f(1)〜f(n)のいくつかを使ってf(n＋1)を求める法則を表す式
• 3！を求める流れ
  • ① f(3)：
    • nが0でないので、f(2)を呼び出す
  • ② f(2)：
    • nが0でないので、f(1)を呼び出す
  • ③ f(1)：
    • nが0でないので、f(0)を呼び出す
  • ④ f(0)：
    • nが0だから1を返す
  • ⑤ f(1)：
    • 1×1＝1を返す
  • ⑥ f(2)：
    • 2×1＝2を返す
  • ⑦ f(3)：
    • 3×2＝6を返す
  • ポイント：
    • 呼び出しの途中の状態はスタックに積まれ、後から呼んだものから先に終わる（LIFO）
• 例題：
  • f(4)＝4×f(3)＝4×6＝24
• ★頻出パターン（最大公約数を求める再帰関数）
  • 定義：
    • F(x, y)：y＝0のときx、y＞0のとき F(y, x mod y)
    • mod は割り算の余り
  • F(252, 105)の値は？
    • ＝F(105, 252 mod 105)＝F(105, 42)（252÷105＝2余り42）
    • ＝F(42, 105 mod 42)＝F(42, 21)（105÷42＝2余り21）
    • ＝F(21, 42 mod 21)＝F(21, 0)（42÷21＝2余り0）
    • ＝21（y＝0なのでxを返す）
  • これはユークリッドの互除法で、答えは252と105の最大公約数（252＝2²×3²×7、105＝3×5×7なので3×7＝21。検算OK）
• 例題：
  • F(48, 18)＝F(18, 12)＝F(12, 6)＝F(6, 0)＝6（48と18の最大公約数は6）

再帰関数の実例：2分探索木を再帰で探す

• 再帰的な構造：
  • 自分自身の一部が、自分自身と同じ形をしている構造。木構造がその代表。だから木を使った探索には再帰処理が便利
• ノードのデータ構造：
  • value：
    • ノードがもつデータ
  • left：
    • 左の子のノードを指すポインタ
  • right：
    • 右の子のノードを指すポインタ
  • 子がない場合は nil
• ポインタの書き方：
  • 変数pがあるノードへのポインタのとき、そのノードのメンバは p->value、p->left、p->right と書く
  • p->leftの値をpに代入すると、pは左の子へのポインタになる
• 探索関数search（データxが2分探索木の中にあるかを判定する）

function search( x, p )
    // x：探したいデータ、p：今見ているノードへのポインタ
    if ( p が nil )
        return FALSE                   // 行き止まり＝見つからない
    endif
    if ( x ＝ p->value )
        return TRUE                    // 見つかった
    elseif ( x ＜ p->value )
        return search( x, p->left )    // 小さいので左部分木で自分を呼ぶ
    else
        return search( x, p->right )   // 大きいので右部分木で自分を呼ぶ
    endif
endfunction

• 流れ：
  • pがnil（もう進む先がない）→ FALSE
  • xとp->valueが等しい → TRUE
  • xの方が小さい → 左部分木を探す、大きい → 右部分木を探す
• ★試験では、再帰呼出しのときの引数が問われる
  • 左（右）部分木を探すには、左（右）部分木の根のノードへのポインタ（p->left、p->right）を引数にして、自分自身を呼び出せばよい

混同しやすいペア

• 止まる条件（n＝0なら1、y＝0ならx）／自分を呼ぶ式（n×f(n−1)、F(y, x mod y)）
• 呼び出す順（f(3)→f(2)→f(1)→f(0)）／計算が終わる順（f(0)→f(1)→f(2)→f(3)、スタックなので逆順）
• F(x, y)の引数の入れ替わり：
  • 次の呼び出しでは、yが前に、x mod yが後ろに来る
• p->left（左の子へのポインタ、小さいとき）／p->right（右の子へのポインタ、大きいとき）
• FALSE（pがnil＝見つからない）／TRUE（p->valueと等しい＝見つかった）

---

プログラム言語

• 一言で言うと：
  • プログラムの性質（何度でも・同時に・どこでも動けるか）、手続の呼び出し方と変数の寿命、言語の種類、JavaやXML関連の用語の話。

プログラムの性質（再入・再帰・再使用・再配置）→ 呼び出しと記憶域（値呼出し・参照呼出し、static・auto、ヒープ）→ 言語の種類（手続型・関数型・論理型・オブジェクト指向、マークアップ言語、Java・XML用語）

覚え方の軸

• プログラム特性は「再〜」の4つを、できることの違いで区別する：
  • 再入可能＝同時に呼ばれてもOK、再帰＝自分を呼べる、再使用可能＝ロードし直さずに何度も使える（ただし順番に）、再配置可能＝どのアドレスに置いても動く
• 再入可能の作り方は「手続部分は共有、データ部分はタスクごと」
• 引数の渡し方は「値をコピーするか、アドレスを渡すか」：
  • 値呼出しは呼出し元に影響しない、参照呼出しは呼出し元の変数も変わる
• 変数の寿命は「プログラムの終わりまで（static）」か「手続の終わりまで（auto）」
• 言語は「何を書くか」で4つ：
  • 手順（手続型）、関数（関数型）、事実と規則（論理型）、オブジェクト（オブジェクト指向）

プログラム特性：同時に、何度も、どこでも動けるか

• 再入可能（リエントラント）：
  • 複数のタスクから同時に呼び出されても、それぞれに正しい結果を返せるプログラム
  • 実現方法（★試験によく出る）：
    • 実行で内容が変わるデータ部分と、変わらない手続部分に分ける。手続部分は複数のタスクで共有し、データ部分はタスクごとに用意する
• 再帰（リカーシブ）：
  • 手続の中で自分自身を呼び出して使えるプログラム
  • 特徴：
    • 自分自身を呼び出せる
    • 実行途中の状態は、スタックを使ってLIFO方式で管理される
    • 再入可能である
• 再使用可能（リユーザブル）：
  • 一度実行したプログラムを、ロードし直さずにもう一度実行しても、正しい結果を返せるプログラム
  • プログラムの最初か最後で各変数の値を初期化して、逐次使えるようにしている
  • 再入可能の性質はもたないので、あるタスクが使っている間は、他のタスクは待たされる
  • 逐次再使用可能（シリアリリユーザブル）ともいう
  • 逐次処理（シリアライジング）の実現には、セマフォなどを使う
• 再配置可能（リロケータブル）：
  • 主記憶上のどのアドレスに配置しても実行できるプログラム
  • 仕組み：
    • ベースレジスタにプログラムの先頭アドレスを入れ、命令を実行するときにベースレジスタの値をアドレス部の値に加えて有効アドレスにする。だからプログラムを変えずにどこに置いても動く

特性	英語	一言で	ポイント
再入可能	リエントラント	同時に呼ばれてもOK	手続部分は共有、データ部分はタスクごと
再帰	リカーシブ	自分を呼べる	スタック（LIFO）で管理。再入可能でもある
再使用可能	リユーザブル	ロードし直さず何度も使える	変数を初期化する。同時は不可（他は待つ）
再配置可能	リロケータブル	どのアドレスでも動く	ベースレジスタ＋アドレス部＝有効アドレス

プログラム制御：手続の呼び出し方と変数の寿命

• 手続（プロシージャ）：
  • 特定の目的のための一連の動作をまとめて定義したもの。必要なときに呼び出して使う
• 仮引数：
  • 手続の中で定義された引数
• 値呼出し（call by value）：
  • 主プログラムから値そのものを引数として渡す
  • 手続の中で変数の値を変えても、主プログラムの変数には一切影響しない
• 参照呼出し（call by reference）：
  • 主プログラムから変数のアドレスを渡す
  • 手続の中で変数の値を変えると、主プログラムの変数の値も変わる
• 例（手続calc(X, Y)、Xは値呼出し、Yは参照呼出し）：
  • 主プログラム：
    • X＝3、Y＝5 にして calc(X, Y) を呼ぶ
  • 手続calc：
    • X＝X×2、Y＝X＋Y
  • 1行目：
    • 手続内のXに 3×2＝6 が入るだけ（主プログラムのXは3のまま）
  • 2行目：
    • 主プログラムのYに 6＋5＝11 が入る
  • 戻った後の主プログラム：
    • X＝3、Y＝11
• 変数の記憶期間：
  • 変数には、記憶場所と存続期間を指定できる
  • 静的変数（staticを付けて宣言）：
    • プログラムの実行中ずっと（プログラムが終わるまで）記憶域がある
    • 初期化は、プログラムの実行前に一度だけ
  • 自動変数（autoを付けて宣言）：
    • 手続が呼ばれたときに記憶域が確保され、手続が終わると自動的に解放される
    • 初期化は、記憶域を確保した時点でその都度行う。ただし初期化されるのは、変数宣言で初期化を書いている場合だけ（例：auto int x＝0; なら0で初期化される）
  • 例（手続count(u)の中に static int v＝0; v＝v＋u; return v;）：
    • x＝count(5) → vは5
    • y＝count(5) → vは前の値が残っているので 10
    • vが自動変数なら、毎回0から始まるので、どちらも5になる
• 動的メモリの割当て：
  • プログラムの実行中に、領域を動的に確保すること。通常、ヒープという領域を使う
  • 長所：
    • 必要な領域をその都度確保できる
  • 短所：
    • 確保を繰り返していると、どこからも参照されない領域ができることがある
  • ゴミ（ガーベジ、garbage）：
    • 不要になったのに解放されず、どこからも参照されないまま残った領域。増えるとヒープの空き領域が足りなくなり、領域を確保できなくなる
  • メモリリーク：
    • 不要になった領域を解放せずにそのままにしておくこと。または、それで空き領域が不足すること
  • ガーベジコレクション：
    • ゴミになった領域を解放・回収して、再び使えるようにする機能（Javaなど）
    • 解放された領域は空き領域リストに追加される。隣り合う空き領域があれば結合して、1つの大きな空き領域にすることがある
    • 注意：
      • ガーベジコレクションがあっても、動的確保のときは確保が成功したかの確認処理を書く必要がある

言語の分類：何を書く言語か

• 手続型言語：
  • 問題解決の処理手順（アルゴリズム）を、1文（命令）ずつ順を追って書く
  • 文の種類：
    • 宣言文（変数などを宣言）、代入文（変数に値を設定）、制御文（分岐や繰返し）
  • 制御文を使うと、1文ずつ順に実行するだけでなく、変数の値で命令の実行順序を変えられる
  • 代表例：
    • Fortran、COBOL、PL/I、Pascal、BASIC、C
• 関数型言語：
  • 再帰処理向きの言語。関数の定義とその呼出しでプログラムを書く
  • 基本の書き方は「関数（引数の並び）＝式」。右辺に「if 条件 then 式 else 式」のような条件式も書ける
  • 関数定義の中で、定義済みの関数や自分自身を使える
  • Lisp：
    • リストや2分木などの再帰的データ構造を直接定義する仕組みがあり、自分自身のプログラムもリストで表せる
• 論理型言語：
  • 述語論理を基礎にした論理式でプログラムを書く
  • 「〜ならば…である」という推論が必要な問題に向いている
  • プログラムに“事実”と“規則”を書けば、処理系の導出原理で結論（“質問”に合う事実）を導ける
  • 代表例：
    • Prolog
  • ユニフィケーション（単一化）：
    • 推論の規則に質問のパターンを比べ、変数に値を代入するなどして、同じ形のものを作っていく操作
  • バックトラック（後戻り）：
    • 途中で単一化に失敗したら、それまでの単一化の効果をすべて元に戻し、別のパターンで比較・単一化し直す操作
  • エキスパートシステムの開発に使われる
    • エキスパートシステム：
      • 知識ベースを使って推論し、その分野に詳しくない人でも正しい結論を導けるシステム。知識ベースと推論エンジンでできている
    • 知識ベース：
      • いろいろな事実や常識、人間の知識や経験則を、「もし〜ならば…」の形で蓄えた特殊なデータベース
• オブジェクト指向言語：
  • “オブジェクト”をプログラムの基本にする言語。すべてのデータはオブジェクトで、すべての計算はオブジェクトにメッセージを送ることで行う
  • 代表例：
    • C++、Java

分類	何を書く？	向いていること	代表例
手続型	処理手順を1文ずつ	一般的な処理	Fortran、COBOL、C など
関数型	関数の定義と呼出し	再帰処理	Lisp
論理型	事実と規則（述語論理）	推論、エキスパートシステム	Prolog
オブジェクト指向	オブジェクトとメッセージ	部品化	C++、Java

• その他の言語
  • マークアップ言語：
    • 文書の一部をタグ（<…>と</…>）で囲み、文書の構造や文字の大きさなどの修飾情報を書く言語
  • XML（Extensible Markup Language）：
    • マークアップ言語の代表。利用者が目的に応じて任意のタグを定義できる
  • YAML：
    • XMLと比べられる規格。タグの代わりにインデントでデータの構造を表す
    • 「YAML Ain’t a Markup Language（YAMLはマークアップ言語ではない）」の略
  • JSON（JavaScript Object Notation）：
    • JavaScriptの言語仕様のうち、オブジェクトの表記法などの一部を基に決めた規格
    • 「名前と値の組の集まり」と「値の順序付きリスト」の2つの構造でオブジェクトを表す
    • 書き方：
      • オブジェクトは“｛”で始まり“｝”で終わる。ダブルクォーテーション（”）で囲んだ名前と値をコロン（:）で区切る（例：{“score”:80}）。組が複数あるときは“，”で区切る。［ ］は配列
    • 例：
      • {“番号”:”3″, “名前”:”HANA”, “年齢”:28, “趣味”:[“読書”,”登山”]}
  • スクリプト言語：
    • 比較的かんたんにコードを書いたり実行したりできるプログラミング言語
    • JavaScript：
      • 動的なWebサイトの作成に使う
    • Python：
      • AI開発に向いた言語として注目されている
    • PHP、Ruby、Perl：
      • Webアプリケーション開発に向いている
• Java・XMLに関連する用語

用語	一言で言うと
Javaアプレット（アプレット）	Webサーバ上のJavaバイトコードをWebブラウザがダウンロードし、Java仮想マシン（Java VM）で実行するプログラム
Javaサーブレット（Servlet）	Webクライアントの要求に応じてWebサーバ上で実行されるJavaプログラム。一度ロードされるとサーバに常駐し、スレッドとして実行される
JavaBeans	Javaで作ったプログラムを、アプリケーションの**部品（コンポーネント）**として扱うための規約
EJB	Enterprise JavaBeansの略。JavaBeansの規約に、エンタープライズ向け（サーバ側の処理）の機能を加えたもの
J2EE	Java 2 Platform, Enterprise Editionの略。Webベースの大規模企業システムで、サーバ側アプリケーションを作るための枠組み（プラットフォーム技術の仕様）。構成技術はServlet、JSP、EJB、JDBCなど
Ajax	Asynchronous JavaScript＋XMLの略。JavaScriptの非同期通信で、画面遷移が起こらない動的なユーザインタフェースを実現する技術
CSS	Cascading Style Sheetsの略。HTMLやXML文書の文字の大きさ、色、行間などの見た目の情報を扱う仕様。文書の表現の定義をHTMLから分離する
DTD	Document Type Definitionの略。XMLの文書構造（データの書き方）を定義するスキーマ言語、またはその記述
XSLT	XML Stylesheet Language Transformationsの略。XML文書を、別の形式のXML文書やHTML文書などに変換するための仕様
SMIL	Synchronized Multimedia Integration Languageの略。動画や音声などのマルチメディアのレイアウトや再生のタイミングをXMLで書くためのW3C勧告（例：「○秒ごとに動画を切り替える」）
SVG	Scalable Vector Graphicsの略。W3Cが作った、矩形や円、直線などの図形をXML形式で表す規格。ベクタ形式なので拡大・縮小しても輪郭が粗くならない。メモ帳などのテキストエディタでも作れる
ebXML	XMLを使った、Webサービス間の通信プロトコルやビジネスプロセスの書き方、取引情報の形式などを定義する一連の仕様

• Javaバイトコード：
  • Javaのソースコードをコンパイルして作られる中間コード
• Java仮想マシン：
  • Javaバイトコードを解釈し、プラットフォームに合ったオブジェクトコード（機械語）に変換して実行するプログラム
• ベクタ形式：
  • 画像を、点や線などの図形を表す数値（計算式）の集まりで表す形式
• W3C：
  • Webで使う技術の標準化を行う非営利団体
• CSS3のメディアクエリ：
  • CSSのメディアタイプを拡張した機能。いろいろなデバイスの画面サイズに合わせて表示するレスポンシブWebデザインを実現できる
• 注意（古くなっている情報）：
  • Javaアプレットは、主要ブラウザがプラグインのサポートをやめたため、今はほぼ使われていない。Applet APIはJDK 26（2026年3月）で削除された。試験ではまだ用語として出る可能性があるので、意味は覚えておく
  • J2EEは、2006年にJava EEに、2018年にEclipse Foundationへ移管されてJakarta EEに名前が変わった。試験では旧名のJ2EEのまま出ることがある

混同しやすいペア

• 再入可能（同時に呼ばれてもOK）／再使用可能（ロードし直さず何度も使えるが、同時は不可）
• 再帰（自分を呼べる、再入可能でもある）／再配置可能（どのアドレスでも動く、ベースレジスタ）
• 値呼出し（値を渡す、呼出し元は変わらない）／参照呼出し（アドレスを渡す、呼出し元も変わる）
• 静的変数 static（プログラムの終わりまで残る、初期化は一度だけ）／自動変数 auto（手続の終わりで解放、初期化はその都度）
• ゴミ（ガーベジ）（参照されなくなった領域）／ガーベジコレクション（ゴミを回収する機能）／メモリリーク（解放し忘れで空きが減ること）
• 関数型（Lisp、再帰向き）／論理型（Prolog、推論向き）
• ユニフィケーション（単一化。パターンを合わせる）／バックトラック（失敗したら元に戻してやり直す）
• Javaアプレット（ブラウザ側で動く）／Javaサーブレット（サーバ側で動く）
• JavaBeans（部品化の規約）／EJB（そのサーバ向け版）
• DTD（XMLの文書構造を定義）／XSLT（XMLを別の形式に変換）／CSS（見た目を指定）
• XML（タグで構造を表す）／YAML（インデントで構造を表す）／JSON（名前と値の組、｛ ｝と［ ］）

---

ひとことでまとめると

リスト	配列と連結リストの違い、先頭・末尾での追加・削除の手間、リストで2分木を表す
スタックとキュー	LIFOのスタックとFIFOのキュー、関数呼び出し、グラフ探索、逆ポーランド表記
木構造	木の用語、完全2分木の公式、走査法（先行・中間・後行）、2分探索木、AVL木・B木
探索アルゴリズム	線形探索 O(n)、2分探索 O(log n)、ハッシュ法とシノニム対策、オーダ記法
整列アルゴリズム	基本整列法 O(n²)、高速整列法 O(n log n)、安定性、分割統治法
再帰法	自分を呼ぶ関数（階乗、最大公約数）、再帰で2分探索木を探す
プログラム言語	再入・再帰・再使用・再配置、値呼出しと参照呼出し、言語の4分類、Java・XML用語