アルゴリズムとデータ構造 2010年4月9日の復習

アルゴリズムとデータ構造
第1章アルゴリズムと計算量
4月15日
情報知能学科
白井英俊
アルゴリズム＋データ構造＝プログラム
• 本講義は「プログラミング」の講義ではない。
復習
• 使用するプログラミング言語に（あまり）依存しな
い、いろいろな種類のプログラムを作るための
「基本的な知識と技術の習得」
が本講義の目的
• その基本知識と技術が
アルゴリズムとデータ構造
2
例えて言えば...
復習
• アルゴリズムは料理のレシピ
入力 ... 料理の材料（小麦粉、キャベツなど)
出力 ... 料理（お好み焼き、カレーライスなど)
料理を作るには材料をどんな手順でどのように調理
するか、が必要 ... アルゴリズム
• データ構造は、料理のための道具
• レシピが読めても、料理を作れないのでは意味が
ない！⇒ ちゃんと動くプログラムを書けなければ
意味がない。。。さらに効率性も大事。。。
3
前回の問題：配列を使ったプログラム
• 問題１．変数aには配列が値として入っている。
たとえば、 a= [ 1, 2, 3,“a”,“ab”,“abc” ]
ここで、a[1]とa[2]の値を取り換えるコード（プ
ログラムの断片）は？
• 問題２．変数aには配列が値として入っている。
aの偶数番目の要素と奇数番目の要素をす
べて取り換えるコードは？
たとえば、 a= [ 1, 2, 3,“a”]ならa= [ 2,1, “a”,3]となる
4
問題１． a[1]とa[2]の値を取り換える
例題: a= [ 1, 2, 3,“a”,“ab”,“abc” ]
一案:
a= [ 1, 3, 2, “a”,“ab”,“abc” ]
これは確かに例題には適用できるが
aがどんな値でもできるものではない --- 解として不適
問題１の関連問題
• 変数x と y の値を取り替える(swap)
x=3, y=5ならば、これによりx=5, y=3になる
ｘ，ｙの値に関係なくちゃんと動くことが条件
; は複数のコードを一行で書くためのもの
ダメな解答: x = y ; y = x
その理由が即答できない人は『よく考えてみよう』
正解：使われていない変数（ここではｚとする）を用いる
z = x; x = y ; y = z
別解(Rubyの特性): x, y = y, x
プログラミング言語における＝の意味
プログラミング言語の等号（＝）の左辺と右辺は
だから、アルゴリズムの記述では代入に←を
意味が異なる
使ったりする
＊例えば、数学的には、 x = x+1 はありえない
= の右側は「値」（変数なら、それが記憶している数
値や文字列）
=の左側は「記憶場所」
＊ x = x+1 x ← x+1 と書いた方がしっくりくる？
xの値に１を足した結果を記憶場所xに記憶
＊a[1] = a[2]
a[2]の「値」をa[1]の場所に書き込む
問題１． a[1]とa[2]の値を取り換える
例題: a= [ 1, 2, 3,“a”,“ab”,“abc” ]
一案:
別解:
使われていない変数ｘを用いて
x = a[1] ; a[1] = a[2] ; a[2] = x
a[1], a[2] = a[2], a[1]
Rubyでは多重代入と呼びます
問題２．配列aの偶数番目の要素と奇数番目の要素を
すべて取り換えるコード
a= [ 1, 2, 3,“a”]
なら
a= [ 2,1, “a”,3]
となる
ダメな解答(1)： a[2n] = a[2n+1]; a[2n+1] = a[2n]
ダメな解答(2):
a[0], a[1], a[2], a[3] = a[1], a[0], a[3], a[2]
配列の要素の個数だけ、「値の取替」の必要がある
⇒ 繰り返しを使う
例題だけではなく、より広い範囲で（「一般
解答例： i = 0
的」に）適用できる解を求める！
while ( i < a.length)
a[i], a[i+1] = a[i+1],a[i]
i = i+2
end # while
アルゴリズムの例
入力
• 問題（教科書p.1)： n個の実数x1, x2, …, xnが
与えられて、その中の最大値を求める
出力
• 素朴版(p.1)
x1, x2, …, xnを順にみていく。その途中でいつ
も、「それまでに見た数の最大値」を覚えてお
く。最後まで見終わったとき、「それまでに見
た数の最大値」が求めるべき最大値
10
アルゴリズムの例（続)
• より明確な記述(p.2)
入力：正の整数nとn個の実数値x1, x2, …, xn
出力： x1, x2, …, xnの中の最大値
手続き：
「変数y に x1の値を代入する」
1. y ← x1 (yは「それまでの最大値」を記録）
2. i = 2,3,…,nに対して順に次を行う：
xi > y ならば y ← xi
3. yを出力する
11
アルゴリズムの例（続)
MAXはアルゴリズムの名前。続けて、入
力である「引数」を書く。だからnが必要
• 「プログラム」風(p.3)
Algorithm MAX(n, x1, x2, …, xn)：
入力（Input): 正整数 n と n 個の実数x1, x2, …, xn
出力（Output): x1, x2, …, xnの中の最大値
記法の注意：ここではプログラムの
手続き（Procedure):
命令の後に「；」を書く
1. y ← x1 ;
ここでの記法についてはウェブページの
「教科書のアルゴリズムの記述とRUBY言
2. for i ← 2 until n do
語の対応」参照
if xi > y then y ← xi ;
アルゴリズムにおいて「出力する」とは、
printするという意味でなく、returnによって
3. return y;
値を「返す」ということ
12
アルゴリズムの検証
•このアルゴリズムがちゃんと動くかは
(1)頭で考え、手を動かす
(2)アルゴリズムを反映したプログラムを作り、
適切な入力を与えて動かし、結果を調べる
ことで検証する、つまり、正しいかどうかを確認
する
13
アルゴリズムからRubyプログラムへ
• 2ページと3ページのどちらの記述でもよいが
それに基づいてRubyプログラムを書く
• それにはRuby言語の書き方を知らないといけ
ない…
君たちはちゃんとマスターしていると信じたい！
14
アルゴリズムからRubyプログラムへ(続
き：代入と配列の使用）
• 入力は、変数nとxとする。
ただし、nの値は正整数、
xの値は実数を要素とす Algorithm MAX(n, x1, x2, …, xn)：
入力（Input): 正整数 n と n 個の実
る配列
数x1, x2, …, xn
出力（Output): x1, x2, …, xnの中
• 手続きの最初をRubyで
の最大値
手続き（Procedure):
書くのは簡単…
1. y ← x1 ;
← はアルゴリズムの記述における
『代入』の書き方。Rubyプログラムで
は＝を使う
y = x[1]
2. for i ← 2 until n do
if xi > y then y ← xi ;
3. return y;
実はこれだと問題があるが、今はこれで進める
15
アルゴリズムからRubyプログラムへ(続
き：繰り返し）
2番目の手続きは「繰返し」
Rubyには、『繰り返し』のメソッ
ドはいろいろある:
while, for, downto, times,
… (適切なものを選べる
ようにしよう！）
ここではforを使うのが適切
Algorithm MAX(n, x1, x2, …, xn)：
入力（Input): 正整数 n と n 個の実
数x1, x2, …, xn
出力（Output): x1, x2, …, xnの中
の最大値
手続き（Procedure):
1. y ← x1 ;
2. for i ← 2 until n do
if xi > y then y ← xi ;
3. return y;
実はこれだと問題があるが、今はこ
れで進める
書き方： for i in 2..n 繰り返される処理 end
16
アルゴリズムからRubyプログラムへ(続
き：条件分岐）
•「繰り返される処理」は
Algorithm MAX(n, x1, x2, …, xn)：
正整数 n と n 個の実
ここでは「条件分岐」である。入力（Input):
数x1, x2, …, xn
出力（Output): x1, x2, …, xnの中
Ｒｕｂｙの条件文の書き
の最大値
方：
手続き（Procedure):
if (条件式）
「条件式が成り立つ時の処理」
else
「条件式が不成立の時の処理」
end
1. y ← x1 ;
2. for i ← 2 until n do
if xi > y then y ← xi ;
3. return y;
elseと「条件式が不成立の時の処理」は、なくても可
17
アルゴリズムからRubyプログラムへ(2番
目の処理のまとめ）
• 2番目の処理をまとめ
Algorithm MAX(n, x1, x2, …, xn)：
入力（Input): 正整数 n と n 個の実
ると以下のように書け
数x1, x2, …, xn
出力（Output): x1, x2, …, xnの中
る：
の最大値
手続き（Procedure):
for i in 2..n
1. y ← x1 ;
2. for i ← 2 until n do
if (x[i] > y)
if xi > y then y ← xi ;
3. return y;
y = x[i]
end #if
これらは本来必要ないものだが、
end #for
プログラムを書くときには役に立つもの
18
アルゴリズムからRubyプログラムへ(３番
目の処理）
•3番目の return y はyの値を返すも
の。
•でも、どこに返すのか？
•ここでの選択
(1) 画面に表示する(printを使う）
(2) アルゴリズムＭＡＸの結果として
MAXを呼び出したモノに返す
Algorithm MAX(n, x1, x2, …, xn)：
入力（Input): 正整数 n と n 個の実
数x1, x2, …, xn
出力（Output): x1, x2, …, xnの中
の最大値
手続き（Procedure):
1. y ← x1 ;
2. for i ← 2 until n do
if xi > y then y ← xi ;
3. return y;
ここでは(2)を考える。
でも、「アルゴリズムＭＡＸの結果とし
て返す」とはどういうこと？
19
アルゴリズムからRubyプログラムへ
（関数／メソッド）
•「アルゴリズムＭＡＸの結 Algorithm MAX(n, x1, x2, …, xn)：
入力（Input): 正整数 n と n 個の実
果として返す」とは、
数x1, x2, …, xn
出力（Output): x1, x2, …, xnの中
Ruby の関数（メソッド）を
の最大値
手続き（Procedure):
つくり、それにmaxと名を
1. y ← x1 ;
つけ、maxの関数の処理と 2. for i ← 2 until n do
if xi > y then y ← xi ;
して1から3までの処理を
3. return y;
やらせる、
Ｒｕｂｙでは関数名を大文字にできないのでmaxとする
ということ
return文が大事
20
アルゴリズムを関数として表現
関数：入力を取り、それに基づいて一連の手続き
（計算）を行い、その結果を出力する（返す）、という
プログラムの単位
21
関数について
関数定義の引数(xとｙ)
は仮引数という。『定義』
のための仮のもの
• 関数名を func とすると
関数の定義の書き方：
def func(x,y)
… プログラム(「コード」とも)…
…どこかにreturn文が必要…
end
関数呼出の引数(3と5)
は実引数。計算に用い
関数の呼び出し：
られる実物。
ans = func(3,5)
22
関数の利点
• 一連の手続きに『名前』をつけ、入力と出力を
明示することで、その手続きが何をしているか
が明確になる
• プログラムを関数に分けることで、そのプログ
ラムの構造が明確になる
• 関数ごとにデバッグをすることで、誤りが発見
しやすい。また変更も容易になる
• 同じような処理をする場合に、冗長性が減る
• 『再帰』は関数を使わないと書けない
23
アルゴリズムからRubyプログラムへ
（完成）
• 関数は以下のようにdef を使っ
て定義する：
def max(n,x)
y = x[1]
for i in 2..n
if (x[i] > y)
y = x[i]
end # if
end # for
return y
end # def
Algorithm MAX(n, x1, x2, …, xn)：
入力（Input): 正整数 n と n 個の実
数x1, x2, …, xn
出力（Output): x1, x2, …, xnの中
の最大値
手続き（Procedure):
1. y ← x1 ;
2. for i ← 2 until n do
if xi > y then y ← xi ;
3. return y;
Rubyのプログラムでは、endがdefやforやifなどと
対応するため対応関係がわかりにくい。そこで、
インデント(段付け）をして対応が分かるように書く
24
実際に検証してみよう
• 先のプログラムは単に「アルゴリズム」をプログ
ラムに直しただけ。
• それがちゃんと期待通りに計算するかは、
(1) 具体的な（入力）データを与える
(2) アルゴリズムが返した結果を表示させる
ということが必要。
25
実際に検証してみよう(続き）
具体的には以下のようなプログラムを作る：
# maxアルゴリズムの検証
def max(n,x)
y = x[1]
for i in 2..n
if (x[i] > y)
y = x[i]
end # if
end # for
return y
end # def
# ここからが検証用のデータ
print max(10, [0.3, 0.1, 0.7, 0.9, 1, 0.2, 0.5, 0.8, 0.4, 1.0])
この内容をmax.rbとして、実行させてみると…
26
動かない…
• ちゃんと書いたはずなのだが、以下のようなエ
ラーメッセージが出て動かない…
max.rb:5:in `max': undefined method `>' for
nil:NilClass (NoMethodError)
from max.rb:4:in `each'
from max.rb:4:in `max'
from max.rb:12
27
めげない！
• エラーメッセージに理由が書いてある。それを
読んで、理由を理解して、直してみよう。
• 講義用のウェブページにある「Rubyのエラー
メッセージとその対処」を読んでみよう。
• これはそのうちのどこにあたるか？
28
プログラムの修正
• 「(5) 未定義(undefined)なメソッド(method)／関数に
よるエラー」に相当することが分かる
• 解釈：この場合は、5行目に使われている＞という
「未定義なわけがない」演算子がやり玉にあがって
いる。ここは、つまり「for nil:NilClass」が問題。つまり
「nil」には＞が使えない、と言っている。
• 対処法：このようなエラーが起きるのは、配列の要素
の指定が間違っているか、要素の値の初期化(例え
ば0にする)ことを忘れている場合が多い
29
プログラムの修正(続き)
• わかっただろうか？配列の要素の指定に問題があったので
ある。
• プログラムを見てみよう：
def max(n,x)
ｙに配列の先頭の要素を与えた「つもり」
y = x[1]
for i in 2..n
配列の2番目の要素から最後の要素ま
if (x[i] > y)
で、要素を一つ一つ調べている「つもり」
y = x[i]
end # if
Ｒｕｂｙの配列のインデックスは、いくつから始まり、いく
end # for
つが最後の要素をさすものだったかな？
return y
end # def
30
プログラムの修正(完成）
# maxアルゴリズムの検証
def max(n,x)
y = x[0]
for i in 1..(n-1)
if (x[i] > y)
y = x[i]
end # if
end # for
return y
end # def
# ここからが検証用のデータ
print max(10, [0.3, 0.1, 0.7, 0.9. 1.1, 0.2, 0.5, 0.8, 0.4, 1.0])
実行させた結果は…
31
参考
• プログラミング言語Cで書くと：
float max(int n, float x[ ]) {
int i;
float y=x[0];
for (i=1; i < n; i++) {
if (x[i] > y) { y=x[i]; }
}
return y;
}
実際には以下のプログラムに挿入
#include <stdio.h>
#define Num 10
/* ここにいれる */
int main() {
static float data[Num] = {
0.3, 0.1, 0.7, 0.9. 1.1, 0.2, 0.5,
0.8, 0.4, 1.0};
printf(“%f\n”, max(Num,data));
}
32
4月15日の課題
2. 配列aのx番目の要素とy番目の要素を取り
換えて得られる配列を返す関数定義
torikae(a,x,y)
例: a = [1,2,3,4,5] 、とすると torikae(a,1,3)は
[1,4,3,2,5] を返す
回答
概略は次のようになる（わからない人はいます
か？）
4月15日の課題(2)
2. 配列aのx番目の要素とy番目の要素を取り換えて
得られる配列を返す関数定義torikae(a,x,y)
def torikae(a,x,y)
z = a[x]
配列aのｘ番目の要素とｙ番目の
ここに課題を満たすコード
a[x] = a[y]
要素を取りかえるコードは？
（プログラム）を書く
a[y] = z
# 最後に配列を返す---
return a
end # def
参考：最初の３行は
a[x], a[y] = a[y], a[x]
とも書ける
4月15日の課題(3)
3. ２つの要素(いずれも数)をもつ配列aの中身
を、小さいものから大きいものになるよう並び
かえた配列を返す関数の定義seiret2
例: a = [1,2] とすると seiret2(a)は [1,2] を返し、
a = [20,10] とすると seiret2(a)は [10,20] を返
す
回答
概略は次のようになる（わからない人はいます
か？）
4月15日の課題(3)続
3. ２つの要素(いずれも数)をもつ配列aの中身を、小
さいものから大きいものになるよう並びかえた配列
を返す関数の定義seiret2
例: a = [1,2] とすると seiret2(a)は [1,2] を返し、 a =
[20,10] とすると seiret2(a)は [10,20] を返す
def seiret2(a)
参考：２行目は
if (a[0] > a[1])
配列aの１番目の要素が２番目の要素より
a[1], a[0] = a[0], a[1] a = torikae(a,0,1)
とも書ける
大きければ、これらを取りかえるコード！
end # if
return a # 最後に配列を返す
end #def
4月15日の課題(4)
4. 三つの要素(いずれも数)をもつ配列aの中身
を、小さいものから大きいものになるよう並びか
えた配列を返す関数seiret3の定義
例: a = [1,2,3] とすると seiret3(a)は [1,2,3] を返し、
a = [20,10,30] とすると seiret3(a)は [10,20,30] を返し、
a = [33,22,11] とすると seiret3(a)は [11,22,33] を返す
回答
概略は次のようになる（わからない人はいますか？）
4月15日の課題(4)続
4. 三つの要素(いずれも数)をもつ配列aの中身
を、小さいものから大きいものになるよう並びか
えた配列を返す関数seiret3の定義
def seiret3(a)
ここに課題を満たすコード
これはちょっと考えないといけない…
（プログラム）を書く
end # def
4月15日の課題(4)続
4. 三つの要素(いずれも数)をもつ配列aの中身
を、小さいものから大きいものになるよう並びか
えた配列を返す関数seiret3の定義
考え方：３つの要素(仮にx,y,zとする)を小さい
ものから大きいものに並び替えるとすれば６通り
の可能性がある( 3! = 6)
(1) x ≧ y ≧ z
(2) x ≧ z ≧ y
(3) y ≧ x ≧ z
(4) y ≧ z ≧ x
(5) z ≧ x ≧ y
(6) z ≧ y ≧ x
4月15日の課題(4)続
4. 三つの要素(いずれも数)をもつ配列aの中身
を、小さいものから大きいものになるよう並びか
えた配列を返す関数seiret3の定義
考え方：まずxとｙの大きさを比べる…
は x ≧ y の場合の可能性
(1) x ≧ y ≧ z
(2) x ≧ z ≧ y
(3) y ≧ x ≧ z
(4) y ≧ z ≧ x
(5) z ≧ x ≧ y
(6) z ≧ y ≧ x
4月15日の課題(4)続
4. 三つの要素(いずれも数)をもつ配列aの中身
を、小さいものから大きいものになるよう並びか
えた配列を返す関数seiret3の定義
考え方：まずxとｙの大きさを比べる…
次にx と zの大きさを比べる
(1) x ≧ y ≧ z
(2) x ≧ z ≧ y
最後にy と zの大きさを比べて(1)か(2)が決まる
(5) z ≧ x ≧ y
4月15日の課題(4)続
4. 三つの要素(いずれも数)をもつ配列aの中身
を、小さいものから大きいものになるよう並びか
えた配列を返す関数seiret3の定義
if (x >= y)
# xとｙの大きさを比べる…
if ( x >= z)
# 次にx と zの大きさを比べる
if (y >= z)
# 最後にy と zの大きさをる
return [z,y,x] # x>= y>= z
else
return [y,z,x] # x>= z >= y
end #if (y>=z)
これにならって他の場合を書きこむ！
end # if (x>=z)
end # if (x>=y)
4月15日の課題(4)続
４．三つの要素(いずれも数)をもつ配列aの中身
を、小さいものから大きいものになるよう並びか
えた配列を返す関数seiret3の定義
完成させよう！
練習問題（１）
• n個の実数x1, x2, …, xnが与えられて、その中の
最小値を求める
(1)アルゴリズムを書く
(2)プログラムを書く
(3)適当なデータを与えて、プログラムを実行して
みる。そして最小値を返すことを確認する。
44
練習問題（２）
• n個の実数x1, x2, …, xnが与えられて、その中の
２番目に大きな数を求める
(1)アルゴリズムを書く
(2)プログラムを書く
(3)適当なデータを与えて、プログラムを実行して
みる。そして2番目に大きな数を返すことを確認
する。
45
出欠レポート
• ここまでの作業内容を出欠レポートとして書く
• 次は、宿題について
課題（1と２は提出を求める宿題）
• プログラムを書くために、Rubyを復習しよう
• 次の問題にチャレンジしてみよう
(1)最古のアルゴリズム(ユークリッドの互除法）をプロ
グラム化する
(2) ファイルから実数を読み込み、その中の最大値を
答える（つまり、数がファイルに書いてある）
(3) 最大値と最小値からなる配列を返す
(4) 最大値と最小値からなる配列を答えるだけではな
く、それらが何番目の要素であるかも答える
宿題の提出期限は4月21日（木曜日）まで。あて先はウェブページ
参照
47
プログラム課題提出の注意
• （これこれの問題を解く）「プログラムを書け」、もしく
は「アルゴリズムを書け」という課題が多く出される
• この時に求められているのは「プログラム（やアルゴリ
ズム）」だけではないことに注意
• 要求事項がちゃんと満たされていることも示す（検証
する）必要がある
• そのために、プログラムの中身、その実行例（複数個
の例題）、実行結果の吟味（ちゃんと目的を果たして
いるかどうか）を示す
48
ユークリッドの互除法
入力：正整数p, q
出力：pと q の最大公約数
手続き：
1. q > p ならば、 p と q の値を入れ替える
2. r ← （p の q による剰余）
3. r = 0 ならば、q が最大公約数（終了）
さもなくば、 p ← q, q ← r として、１へ。
p = 72, q = 30 として、試してみよう
49
基本的な用語の確認
整数ｘが整数aの約数 ⇔ aがｘで割り切れる
• aとｂの公約数：aもbも正整数であることが前提
aの約数とbの約数で共通する数のこと
例： 30 の約数は 1, 2, 3, 5, 6, 10, 15, 30
72の約数は 1, 2, 3, 4, 6, 8, 9, 12, …, 36, 72
• aとｂの最大公約数(GCD)：aとｂに共通する公約
数のうち最大のもの
30と72の最大公約数(これをGCD(30,72)と書く）
は…
50

Download Report