資料 - 中山英樹研究室

アルゴリズム入門
第5回
~文字列・配列~
情報理工学系研究科
創造情報学専攻
中山 英樹
1
条件式
 色々な比較演算子が使える
 >= や <= や != などに注意
(p.36)
x = y は代入！
 条件式の組合せ
よく詰まるポイント
 整数同士の割り算は答えも整数になる
 小数で計算して欲しい時は、”*1.0” などを挟むとよい
 演算子は省略できない
 2ri は間違い。2 * r * i とかけ算を書く。
 全角空白に注意
 半角空白と同じとは認識されないのでエラーになる
 ファイルを書き換えた時
 ちゃんとsaveして、irbでloadするのを忘れずに
 違うファイルを読まないように！（pathに注意）
3
Tips
 関数のテスト
 いきなり全体を実行せず、関数一つずつテストする。
>> load("make2d.rb")
==> true
>> make1d(3)
==> [0, 0, 0]
 エラーメッセージ
 落ち着いてちゃんと読むことが原因究明の近道
4
前回の課題３
def b(x, y)
n=0
r = 0.0
i = 0.0
while r**2 + i**2 < 4 && n <= 50 do
n=n+1
oldR = r
r=r*r–i*i+x
i = 2 * oldR * i + y
end
if n >= 50 then 0 else 1 end
end
n=3 のときの変数 r の値は r3 の値
5
変数の古い値と新しい値
 変数の値が変わるとき注意
× r = r ** 2
i=2*r*i
# r は古い値を二乗した新しい値
○古い値を退避しておく
oldR = r
r = r ** 2
i = oldR * i
 Ruby の多重代入を使えば退避不要
○ r, i = r ** 2, r * i
6
文章を扱う （3.3章）
 文字列
 二重引用符 "で囲んだ文字の列
 変数に代入したり、関数の値にできる
• 整数だけでなく配列（ベクトル）を変数に代入できたように
 文字列の足し算などが可能
例
a = "Ruby"
b = " language"
# 空白を含めることも可能
a+b
=> "Ruby language"
7
文字列の演算
a = “Ruby”
a.length()
=> 4
b = “ruby”
a == b
=> false
c = b.capitalize()
a == c
=> true
a[1..2]
=> “ub”
a[1..1]
=> "u"
a[0..2] + "Y"
=> "RubY"
# 文字列の長さ（文字数）
# 文字列の比較（一致するか？）
# 先頭を大文字に
# 単にa[1]と書いてもよい
8
言葉探し (4.3.3章)
 例: 配列sの中で配列pと一致する部分は何番目?
match("balalaika", "alai") → 3
balalaika
alai
2重の繰り返し
9
繰り返しによる文字列の検索
 例: 配列sの中で配列pと一致する部分は何番目?
match("balalaika", "alai")
0
balalaika
alai
10
文字列の検索
 例: 配列sの中で配列pと一致する部分は何番目?
match("balalaika", "alai")
1
balalaika
alai
11
文字列の検索
 例: 配列sの中で配列pと一致する部分は何番目?
match("balalaika", "alai")
2
balalaika
alai
12
文字列の検索
 例: 配列sの中で配列pと一致する部分は何番目?
match("balalaika", "alai")
→3
3
balalaika
alai
13
文字列検索のプログラム
文字列sのi番目からｗ文字だけ
文字列pと比較したときに
一致する文字数
def match(s,p)
i=0
w=p.length()
while submatch(s,i,p,w) < w
i=i+1
end
i
end
s:
p:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
a
i
submatch(s, 0, p, 4) => 0
s:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
a
i
p:
submatch(s, 1, p, 4) => 3
s:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
a
i
p:
submatch(s, 2, p, 4) => 0
s:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
a
i
p:
submatch(s, 3, p, 4) => 4
i==3 のときに、submatch(s, i, p, w) < w が false になる
def submatch (s,i,p,w)
j=0
while j < w && s[(i+j)..(i+j)] == p[j..j]
j=j+1
end
j
end
s:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
a
i
p:
submatch(s, 3, p, 4)
i==3 w==4
j==0
j < w && s[(i+j)..(i+j)] == p[j..j]
=> "a"
=> "a"
=> true
s:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
a
i
p:
submatch(s, 3, p, 4)
i==3 w==4
j==1
j < w && s[(i+j)..(i+j)] == p[j..j]
=> true
s:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
a
i
p:
submatch(s, 3, p, 4)
i==3 w==4
j==2
j < w && s[(i+j)..(i+j)] == p[j..j]
=> true
s:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
a
i
p:
submatch(s, 3, p, 4)
i==3 w==4
j==3
j < w && s[(i+j)..(i+j)] == p[j..j]
=> true
s:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
a
i
p:
j < w が false なので
s[(i+j)..(i+j)] == p[j..j] は
検査されない
submatch(s, 3, p, 4)
i==3 w==4
j==4
j < w && s[(i+j)..(i+j)] == p[j..j]
=> false
マッチしない場合は…
s:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
b
b
p:
submatch(s, 3, p, 4)
i==3 w==4
j==0
j < w && s[(i+j)..(i+j)] == p[j..j]
=> "a"
=> "a"
=> true
s:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
b
b
p:
submatch(s, 3, p, 4)
i==3 w==4
j==1
j < w && s[(i+j)..(i+j)] == p[j..j]
=> true
s:
0
1
2
3
4
5
6
7
8
b
a
l
a
l
a
i
k
a
0
1
2
3
a
l
b
b
p:
s[(i+j)..(i+j)] == p[j..j] が
submatch(s, 3, p, 4)
false なのでwhileを抜ける
i==3 w==4
j==2
j < w && s[(i+j)..(i+j)] == p[j..j] => false
文字列検索のプログラム（まとめ）
 文字列sの中で文字列pと一致する部分は何番目?
sのi番目からとpの一致数
def submatch(s,i,p,w)
j=0
while j < w && s[(i+j)..(i+j)] == p[j..j]
j=j+1
end
j
end
pはsの何文字目
def match(s,p)
から出現するか?
i=0
w=p.length()
while submatch(s,i,p,w) < w
i=i+1
end
i
end
match("balalaika","alai")
28
ちなみに…
def submatch (s,i,p,w)
j=0
while j < w && s[(i+j)..(i+j)] == p[j..j]
j=j+1
end
s[i+j] == p[j] でもOK
j
end
29
本日の課題（問題１）
 文字列を逆順にする関数 reverse を書いてコードを提出せよ。
reverse("Ruby language")などとして、正しく動作することを
確認しておくこと。
 while を使うこと
 s.reverse() や s.split("").reverse().join() などは不可
 ヒント
?? を埋めよ
def reverse(s)
result = ""
# 空文字列（長さ０）
i = ??
while i >= 0 do
??
i=i–1
end
result
# 逆順になった文字列
end
30
本日の課題（問題 2）
 match の定義では s 中に p が必ず現われることを仮定し
ていた。p が現われない場合に -1 と答える
match_safe(s,p) を定義し、コードを提出せよ。
31
(+α) 本日の課題（問題 3）
 問題２の match_safe をさらに改良し、pが見つかったす
べての場所を列挙した配列を返す関数 match_all(s,p) を
定義し、コードを提出せよ。
 ヒント： 配列のpushメソッドを使うと便利
irb(main):001:0> a = []
=> []
irb(main):002:0> a.push("foo")
=> ["foo"]
irb(main):003:0> a.push("bar")
=> ["foo", "bar"]
32
次回（11月4日）について
 第Ⅰ部の復習と練習
 今までの授業で、よく分からなかったところや、もう
一度説明してほしいところを今日のアンケートに書い
てください
 少しボリュームのある演習課題を用意します。
• 授業中にどんどん解いてもらってOK
• 締め切りは12月2日(金)の講義開始まで
 お絵かき自由課題(課題2問題3)の投票をします。
33