アルゴリズムとデータ構造

アルゴリズムとデータ構造

第

週 スタックと待ち行列

2014年10月9日 金岡 晃

授業計画

第

週

データ構造とアルゴリズムの基 礎

第

週

アルゴリズムの効率、線型構造、

スタックと待ち行列 第

週

(10/9)

＜演習＞アルゴリズムの効率、

線型構造、スタックと待ち行列 第

週

(10/16)

文字列照合（

法、

法）

＋＜演習＞

第

週

休講 第

週

(10/30)

木の構造、木の走査、二分木、

決定木 第

週

(11/13)

＜演習＞木の構造、木の走査、

二分木、決定木 第

週

(11/20)

中間試験

第

週

休講 第

週

(12/4)

グラフ構造と最短路問題＋

＜演習＞

第

週

データ整列：ヒープソート 法、クイックソート法

第

週

＜演習＞データ整列：ヒー プソート法、クイックソー ト法

第

週

データ探索：ハッシュ法、

木構造探索法 第

週

(1/15)

＜演習＞データ探索：ハッ シュ法、木構造探索法

1/21-2/6

期末試験

【復習】第 2 週

アルゴリズムの効率、線形構造

アルゴリズムとデータ構造

アルゴリズムの効率

𝑚𝑜𝑑

の利用

𝑛 𝑚𝑜𝑑 3

を計算し、0になるかどうかを判定

3

ずつ引いていく

𝑛 = 𝑛 − 3

を繰り返し計算し、1または2になったら0を出

力、0になったら1を出力 各桁の数を足し合わせる

𝑛

の各桁の数字を上位から取り出し、足して3での余りを調べる。すべての数字の 処理が終わった結果が0だったら1を出力、それ以外（1または2）だったら0を出力

• 「𝑚𝑜𝑑

の計算」と「減算」と「数字を取り出し、足して3での余りを調べ る」の3つの作業はすべて同じ時間で実行できる

前提 前提

作業の回数を見る 作業の回数を見る

1回 1回

𝑛/3 回 𝑛/3 回

log₁₀ 𝑛 回 log₁₀ 𝑛 回

オーダ記法

計算時間の近似的な目安 計算時間の近似的な目安

𝑂 𝑓 𝑛 と表現されたときの時間計算量

𝑂 𝑓 𝑛 と表現されたときの時間計算量

𝑂 𝑓 𝑛

𝑛 が十分大きいところでは 𝑓 𝑛 に比例した処理時間にな る。つまり 𝑓 𝑛 の定数倍の時間として十分精度良く近似 できる。

1. 𝑚𝑜𝑑

の利用

2. 3

ずつ引いていく

3.

各桁の数を足し合わせる

𝑂 1 𝑂 𝑛

𝑂 log 𝑛

𝑂 1 < 𝑂 log 𝑛 < 𝑂 𝑛

なので1→3→2の順に効率が良い

レコード

•

データ構造の基本

•

一般に複数のフィールド（Field、欄ともいう）からなる。

•

各フィールドに名前を付け、格納できるデータの型も前もって指定 してある

例 例

レコードの定義： 氏名

（文字列） 年齢

（非負整数） 識別子

（非負整数）

各レコード： 山田太郎

佐藤次郎

鈴木一朗

関係

レコードの集合があって、レコード間に何らかの関係をつくると、

データ構造になる

順序関係

順序関係

アルファベット順

•

出席番号順

•

背の順

•

成績順

全順序関係

全順序関係 任意の2レコード間に必ず順序が決まっている関係

全順序関係の定義

全順序関係 全順序関係

集合

の任意の要素

について、要素間の関係

に関して次の 4つの性質が成り立つものを、集合

上の全順序関係と言う。

１．反射律：

２．推移律：

３．反対称律：

４．

∨：または

∧：かつ

⇒：ならば

例 例

•

数値の大小関係（

）

•

辞書式順序（アルファベット順、アイウエオ順）

データの論理構造

•

レコード

を含むファイル

•

全順序構造がある

𝑎 ≤ 𝑐 𝑎 ≤ 𝑑

𝑏 ≤ 𝑐 𝑏 ≤ 𝑑 𝑐 ≤ 𝑑

本質的には

データの論理構造 データの論理構造

𝑎 𝑏 𝑐 𝑑

レコード

関係

グラフになっている

グラフになっている

データの物理構造

𝑎 𝑏 𝑐 𝑑

上記の論理構造を物理的にコンピュータに格納する必要性がある 順配置

順配置

1 a 2 b 3 c 4 d

リンク配置 リンク配置

a b c d

論理構造から物理構造を構成することはプログラミングの重要な仕事

論理構造から物理構造を構成することはプログラミングの重要な仕事

演習（その１）

平方数を判定する 平方数を判定する

※平方数：ある整数の2乗で表される整数 （例：1, 4, 9, 16, 25)

目的： 入力された値が平方数であるか否かを判定する 入力： 自然数

出力： 0 （平方数でない） または 1（平方数である）

手法

1,2, … , 𝑛

を順に2乗し、

と等しいか確認する。 確認する数：最大

回

制約： 利用できる算術演算は加算（＋）、減算（－）、積（×）のみ

演習：手法

よりも高速（確認する数が少ない）アルゴリズムを考え、実装して

演習（その 2 ）

積木の塔を解く 積木の塔を解く

演習：積木の塔を解くアルゴリズムを考え、実装してみよう 入力：初期状態。（T,T,T,A）のようなベクトル。

※ベクトルの入力方法は任意

出力：目的の状態（B,C,D,T）に至るまでの状態と動作（moveとremove）

の内容の列挙

注：現段階では実現は難しいかもしれないので、

できなかった場合は、どういう考えでやろうとし て（アルゴリズムのイメージ）、どう失敗したか を示せるように

注：現段階では実現は難しいかもしれないので、

できなかった場合は、どういう考えでやろうとし

て（アルゴリズムのイメージ）、どう失敗したか

を示せるように

演習（その 2 ）：実行イメージ

> java Tower T T T A (T, T, T, A)

move (B, C) (T, C, T, A)

remove (D) (T, C, T, T)

move(B,A) (T, A, T, T)

move(C,D) (T, A, D, T)

move(B,C) (T, C, D, T)

move(A,B) (B, C, D, T)

> java Tower T T T A (T, T, T, A)

move (B, C) (T, C, T, A)

remove (D) (T, C, T, T)

move(B,A) (T, A, T, T)

move(C,D) (T, A, D, T)

move(B,C) (T, C, D, T)

move(A,B) (B, C, D, T)

演習（その 3 ）

• 計算量が 𝑂 𝑛 、 𝑂 𝑛

の例をそれぞれ 1 つずつ考え、実装 してみる

– 例：「九九の表を作る」

– 「＊＊という状況で＊＊＊という問題を解く」というまず状況 設定と解かれるべき問題をプログラムのソースコードにコメン ト文として書くこと

– 同じく、コメント文に問題の解き方を書き、それがなぜその オーダになるかを示すこと

計算量を考える 計算量を考える

この例をそのまま使うのは

やめてください

締切と提出方法：演習その 1 ～その 3

•

締切

–

本日（

月

日）の

まで

※本日のこの講義＋演習時間が終わるまで

•

提出方法

–

電子メール

•

メールアドレス

– [email protected]

–

メールのタイトルに「アルゴリズムとデータ構造第

回課題」と書 いてください

–

作ったプログラム（計

つ）をメールに添付してください。

•

注意事項

–

必ず金岡から受領確認メールを返します。

•

必ず日本語で受領確認メールを返します

•

英語のメールはエラーメール（アドレスが間違っている）の可 能性が高いです

–

メールで提出がされていないものは未提出とみなします

第 3 週

スタックと待ち行列

アルゴリズムとデータ構造

本日の到達目標と概要

• 到達目標

– スタックとキューの概要を理解する – 再帰的手続きを理解する

• 概要

– スタックとキュー

– 順配置表現でのスタックとキュー – 再帰的手続き

– ハノイの塔

レコードの追加・削除の形態

線形リストへのレコード追加・削除

スタック（Stack）

スタック（Stack）

レコードの追加・削除ともに線形リストの先頭においてのみ行われる

キュー（Queue）

キュー（Queue）

レコードの追加は線型リストの末尾のみ、削除は先頭においてのみ行われる

スタック

スタック（Stack）

スタック（Stack）

レコードの追加・削除ともに線形リストの先頭においてのみ行われる

追加をプッシュ（push）、削除をポップ（pop）と呼ぶ LIFO（Last-In First-Out）とも呼ばれる

例 例

•

机の上に積んだ本

•

スーパーやコンビニエンスストアの籠

レコードの追加は線型リストの末尾のみ、削除は先頭においてのみ行われる

キュー（待ち行列）

キュー（Queue) キュー（Queue)

追加をEnqueue、削除をDequeueと呼ぶ FIFO（First-In First-Out）とも呼ばれる

例 例

•

有名店の行列

•

コンビニエンスストアの飲料売り場

順配置表現

a[1]

a[n]

先頭の位置 t

a[1]

a[n]

末尾の位置 r 先頭の位置 の1つ前 f スタック（Stack）

スタック（Stack） キュー（Queue) キュー（Queue)

再帰的手続き

再帰的手続き 再帰的手続き

手続き中にその手続き自身を呼び出すこと

再帰性：数学的帰納法、漸化式、フラクタル図形 漸化式の例： 𝑘 _𝑡 = 𝑘 _𝑡−1 + 𝑘 _𝑡−2

フラクタル図形の例：

再帰的手続きの例：ハノイの塔

ハノイの塔 ハノイの塔

19世紀にEdouard Lucasにより発明されたゲーム。

・3本のピンがある

・穴の開いた大きさの異なる円盤が複数枚ある

・最初は左端のピンに小さいものが上になるように積み重ねられている

・すべての円盤を他のピンに移す

・ただし、1度の1枚の円盤しか動かせない

・小さな円盤の上に大きな円盤を載せることはできない

例 例

円盤が3枚のときの

初期状態

ハノイの塔：枚数 3 枚（ 𝑛 = 3 ）のとき

ハノイの塔：枚数 3 枚（ 𝑛 = 3 ）のとき

操作に名称を付ける 操作に名称を付ける

𝑚𝑜𝑣𝑒(𝑖, 𝑗)

：ピン

の頂上の円盤をピン

に移す

1 2 3 1 2 3 1 2 3

1 2 3 1 2 3 1 2 3

𝑚𝑜𝑣𝑒(1,3) 𝑚𝑜𝑣𝑒(1,2)

𝑚𝑜𝑣𝑒(3,2) 𝑚𝑜𝑣𝑒(1,3) 𝑚𝑜𝑣𝑒(2,1)

𝑚𝑜𝑣𝑒(2,3) 𝑚𝑜𝑣𝑒(1,3)

ハノイの塔：枚数 𝑛 枚のとき

操作に名称を付ける 操作に名称を付ける

𝐻𝑎𝑛𝑜𝑖 𝑛, 𝑖, 𝑗

：

枚の円盤をピン

からピン

に移す

1

枚の時

枚の時

𝐻𝑎𝑛𝑜𝑖 2, 𝑖, 𝑗 ∶ 𝑚𝑜𝑣𝑒 𝑖, 𝑘 , 𝑚𝑜𝑣𝑒 𝑖, 𝑗 , 𝑚𝑜𝑣𝑒(𝑘, 𝑗) 𝑘 = 6 − 𝑖 − 𝑗

1 2 3 1 2 3 1 2 3

𝑚𝑜𝑣𝑒(1,2) 𝑚𝑜𝑣𝑒(1,3)

𝑚𝑜𝑣𝑒(2,3)

ハノイの塔：枚数 𝑛 枚のとき

操作に名称を付ける 操作に名称を付ける

𝐻𝑎𝑛𝑜𝑖 𝑛, 𝑖, 𝑗

：

枚の円盤をピン

からピン

に移す

𝑛

枚の時

𝐻𝑎𝑛𝑜𝑖 𝑛, 𝑖, 𝑗 ∶ 𝐻𝑎𝑛𝑜𝑖 𝑛 − 1, 𝑖, 𝑘 , 𝑚𝑜𝑣𝑒 𝑖, 𝑗 , 𝐻𝑎𝑛𝑜𝑖(𝑛 − 1, 𝑘, 𝑗) 𝑘 = 6 − 𝑖 − 𝑗

再帰的手続き

ハノイの塔： 𝑛 = 3 のときの操作分解

𝐻𝑎𝑛𝑜𝑖 3, 𝑖, 𝑗 ∶ 𝐻𝑎𝑛𝑜𝑖 2, 𝑖, 𝑘 , 𝑚𝑜𝑣𝑒 𝑖, 𝑗 , 𝐻𝑎𝑛𝑜𝑖(2, 𝑘, 𝑗) 𝑘 = 6 − 𝑖 − 𝑗

𝐻𝑎𝑛𝑜𝑖 3, 𝑖, 𝑗 ∶ 𝐻𝑎𝑛𝑜𝑖 2, 𝑖, 𝑘 , 𝑚𝑜𝑣𝑒 𝑖, 𝑗 , 𝐻𝑎𝑛𝑜𝑖(2, 𝑘, 𝑗)

𝐻𝑎𝑛𝑜𝑖 2, 𝑖, 𝑘 ∶ 𝐻𝑎𝑛𝑜𝑖 1, 𝑖, 𝑗 , 𝑚𝑜𝑣𝑒 𝑖, 𝑘 , 𝐻𝑎𝑛𝑜𝑖 1, 𝑗, 𝑘 𝐻𝑎𝑛𝑜𝑖 1, 𝑖, 𝑗 ∶ 𝑚𝑜𝑣𝑒 𝑖, 𝑗

𝐻𝑎𝑛𝑜𝑖 1, 𝑗, 𝑘 ∶ 𝑚𝑜𝑣𝑒 𝑗, 𝑘

𝐻𝑎𝑛𝑜𝑖 2, 𝑖, 𝑘 ∶ 𝑚𝑜𝑣𝑒(𝑖, 𝑗), 𝑚𝑜𝑣𝑒 𝑖, 𝑘 , 𝑚𝑜𝑣𝑒(𝑗, 𝑘)

𝐻𝑎𝑛𝑜𝑖 2, 𝑘, 𝑗 ∶ 𝐻𝑎𝑛𝑜𝑖 1, 𝑘, 𝑖 , 𝑚𝑜𝑣𝑒 𝑘, 𝑗 , 𝐻𝑎𝑛𝑜𝑖 1, 𝑖, 𝑗 𝐻𝑎𝑛𝑜𝑖 1, 𝑘, 𝑖 ∶ 𝑚𝑜𝑣𝑒 𝑘, 𝑖

𝐻𝑎𝑛𝑜𝑖 1, 𝑖, 𝑗 ∶ 𝑚𝑜𝑣𝑒 𝑖, 𝑗

𝐻𝑎𝑛𝑜𝑖 2, 𝑘, 𝑗 ∶ 𝑚𝑜𝑣𝑒(𝑘, 𝑖), 𝑚𝑜𝑣𝑒 𝑘, 𝑗 , 𝑚𝑜𝑣𝑒(𝑖, 𝑗) 𝐻𝑎𝑛𝑜𝑖 3, 𝑖, 𝑗 ∶ 𝑚𝑜𝑣𝑒 𝑖, 𝑗 , 𝑚𝑜𝑣𝑒 𝑖, 𝑘 , 𝑚𝑜𝑣𝑒 𝑗, 𝑘 , 𝑚𝑜𝑣𝑒 𝑖, 𝑗 ,

𝑚𝑜𝑣𝑒(𝑘, 𝑖), 𝑚𝑜𝑣𝑒 𝑘, 𝑗 , 𝑚𝑜𝑣𝑒(𝑖, 𝑗)

再帰的手続きの例：フィボナッチ数列

フィボナッチ数列 フィボナッチ数列

Leonard Fibonacciにちなんで名づけられた数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

・次の数は、最後の数とその前の数を足した数になる

𝑓 𝑖 = 𝑓 𝑖 − 1 + 𝑓(𝑖 − 2)

再帰的手続き

フィボナッチ数列： 𝑖 = 4 のとき

𝑓 4 = 𝑓 3 + 𝑓(2)

= 𝑓 2 + 𝑓(1) + 𝑓(2)

= 𝑓(1 + 𝑓 0 ) + 𝑓(1) + 𝑓 1 + 𝑓 0

= 1 + 1 + 1 + 1 + 1

= 2 + 1 + 1 + 1

= 3 + 2

= 5

本日の到達目標と概要

• 到達目標

– スタックとキューの概要を理解する – 再帰的手続きを理解する

• 概要

– スタックとキュー

– 順配置表現でのスタックとキュー – 再帰的手続き

– ハノイの塔

演習（その 4 ）

ハノイの塔を解く ハノイの塔を解く

演習：ハノイの塔を解くプログラムを実装してみよう

入力：積木の数, 最初のピンの位置（1, 2, 3のいずれか）, 最後のピンの位 置（1, 2, 3のいずれか）

出力：目的の状態に至るまでの状態と動作（move）の内容の列挙

演習（その 4 ）：実行イメージ

> java Hanoi 3 1 2 ----

1: 3 – 2 – 1 2:

3:

----

move(1,2) ----

1: 3 – 2 2: 1 3:

----

move(1,3) ----

1:3 2:1

> java Hanoi 3 1 2 ----

1: 3 – 2 – 1 2:

3:

----

move(1,2) ----

1: 3 – 2 2: 1 3:

----

move(1,3) ----

1:3 2:1

演習（その 5 ）

フィボナッチ数列 フィボナッチ数列

演習：フィボナッチ数列を表示するプログラムを実装してみよう 入力：数列の長さ

出力：数列の長さまでのフィボナッチ数列の表示

演習（その 5 ）：実行イメージ

> java Fibo 7

1, 1, 2, 3, 5, 8, 13

> java Fibo 7

1, 1, 2, 3, 5, 8, 13

締切と提出方法：演習その 4 ～その 5

•

締切

–

来週（

月

日）の

まで

※来週のこの講義＋演習時間が終わるまで

•

提出方法

–

電子メール

•

メールアドレス

– [email protected]

–

メールのタイトルに「アルゴリズムとデータ構造第

回課題」と書 いてください

–

作ったプログラム（計

つ）をメールに添付してください。

•

注意事項

–

必ず金岡から受領確認メールを返します。

•

必ず日本語で受領確認メールを返します

•

英語のメールはエラーメール（アドレスが間違っている）の可 能性が高いです

–

メールで提出がされていないものは未提出とみなします