第3回複雑な制御構文と再帰関数

先週の復習

配列

配列は複数の変数が連なったもので、似たようなデータを効率的に管理したりすることが可能。

例えば、温度センサーから取得した一週間分のデータを管理したい場合に変数で全部記録すると

data_sun = 13.0
data_mon = 15.0
data_tue = 12.3
data_wed = 42.0
data_thu = 32.0
data_fri = 13.0
data_sat = 21.0

配列に変換すると、

temp_week = [13.0, 15.0, 12.3, 42.0, 32.0, 13.0, 21.0]

配列では左から順番に番地が決められている。 Rubyでは変数名[]で値を囲むことで配列を定義でき、変数名[n]のようにすると[n]番目の要素にアクセス可能。

temp_week[0] => 13.0

番地	0	1	2	3	4	5	6
要素	13.0	15.0	12.3	42.0	32.0	13.0	21.0

配列の番地のカウントは0から始るのに注意

配列では、

stations = ["千歳烏山", "仙川", "つつじヶ丘", "調布"]
matrix = [[1,2,3],[4,5,6],[7,8,9]]
matrix[0] => [1,2,3]
matrix[0][1] => 1

のように文字列を配列に入れたり、配列の配列の入れ子をすることも可能。

ただし、

data = [1, 2, 3]

のような配列でdata[3]で存在しない値にアクセスしようとすると data[3] => nilのようになってしまい、nilが処理に含まれることで何かしらのエラーが発生する場合もあるので注意が必要。

制御構文

制御構文はプログラミングの基礎であり、分岐、繰り返しといった手続きの実行順序を制御することが可能。

条件分岐

Rubyではif文と呼ばれる構文で条件に応じた分岐が可能。

def isPlus(num)
  if num > 0
    return true
  else
    return false
  end
end

この関数を実際に動かしてみると、

isPlus(3) => true
isPlus(-4) => false

のように、正の数ならばtrueでそれ以外ならばfalseと表示される。

また、

if 条件式 then
  処理
elsif 条件式 then
  処理
else
  処理
end

のようにelseやelsifを組み合わせ可能。

関係演算子

条件式は次の関係演算子によって作られる。

演算子	意味	用例
==	等しい	a = b
!=	等しくない	a != b
>	より大きい	a > b
<	より小さい	a < b
>=	以上	a >= b
<=	以下	a <= b

論理演算子

論理演算子を使って条件同士を繋げることが可能。

演算子	意味	用例
&&	かつ	(a > 0) && (b > 0)
\|\|	または	(a > 0) \|\| (b > 0)
!	否定	!(a > 0)

繰り返し

繰り返しは先程の配列を処理する際にとても便利。

シンプルな繰り返しにはfor文がある。

for i in 1..5 do
  puts(i)
end

このコードを実行すると、

と1から5まで打ち出されます。

さきほどの配列における1週間の平均気温を求める場合には、

temp_week = [13.0, 15.0, 12.3, 42.0, 32.0, 13.0, 21.0]
temp_sum = 0.0
for temp in temp_week do
  temp_sum += temp
end
temp_avg = temp_sum / temp_week.size
puts(temp_avg) => 21.185714285714287

のようにすると、1つづつ要素が取り出されてtempに代入されるので合計を簡単に求めることが可能。

復習問題(3rev)

せっかくなので少しだけ複雑な配列で練習してみる。

n人のクラスでそれぞれ100点満点の線形代数と微分積分テストを実施しました。その結果が配列として与えられた時、相関係数を求める関数cor(scores)を作成する。

なお、配列は

[[線形代数の得点, 微分積分の得点],[線形代数の得点, 微分積分の得点],...]

のようにデータが格納されている。

なお相関係数\(r\)は各データの値を\(x_i\)・\(y_i\)、データの総数を\(n\)、平均を\(\overline{x}\)・\(\overline{y}\)としたとき次式で求められる。

\[r = \frac{\sum_{i=1}^n (x_i-\overline{x})(y_i-\overline{y})}{ \sqrt{\sum_{i=1}^n (x_i-\overline{x})^2}\,\sqrt{\sum_{i=1}^n (y_i-\overline{y})^2} }\]

入出力例

cor([[50,40], [60,70], [70,90], [80, 60], [90, 100]]).round(2) => 0.73

制約
すべての値は0以上100以下の整数で与えられる
5<=n<=20である。
nは与えられる配列の要素数と一致しているため、
配列をscoresとしたときn=scores.sizeとして取得できる

サンプルコード(押して開く)

数式に従って実装するだけだが、

なるべく同じ計算を減らす
整数同士の割り算の誤差に注意する

特に前回は私自身も、

sum_x = 0
~~~
avg_x = sum_x / n

としてしまったため、整数同士の割り算となり誤差が生じてしまった。

def cor(scores)
  sum_x = 0.0
  sum_y = 0.0
  n = scores.size
  for score in scores
    sum_x += score[0]
    sum_y += score[1]
  end
  avg_x = sum_x / n
  avg_y = sum_y / n
  temp_x = 0.0
  temp_y = 0.0
  temp_xy = 0.0
  for score in scores
    temp_xy += (score[0] - avg_x) * (score[1] - avg_y)
    temp_x += (score[0] - avg_x) ** 2
    temp_y += (score[1] - avg_y) ** 2
  end
  return temp_xy / (Math.sqrt(temp_x) * Math.sqrt(temp_y))
end

今回の内容

今回の大きな2つのテーマは

複雑な制御構文
再帰関数

です。

今回の再帰関数は少しむずかしい内容にはなっていますが、効率の良いプログラミングをする上で重要なのでついてきてください。

複雑な制御構文

Rubyには前回紹介したif-elseやfor意外にも多くの便利な命令が用意されています。

この講習ではその中でも実用的なものを取り扱って、実際に演習を通して使ってみます。

条件分岐

おまけ unless

if文の逆であるunlessという構文もあります。

unless 条件式はif !(条件式)と同じです。英語なので直感的に分かりやすくなるかもしれません。

case文

条件によって複数の処理に分けるときにはcase文が便利です。

例えば、変数ageによって分岐する場合は

def getClass(age)
  case age
  when 0..2
    "幼児"
  when 3..6
    "小児"
  when 7..12
    "子供"
  when 13..18
    "若者"
  else
    "大人"
  end
end

のように書くことができ、case AとしたときAとwhenで指定された部分が一致する処理を行いってくれます。elseはどの条件にも当てはまらないときに呼ばれます。

def getClass(age)
  if 0..2
    "幼児"
  when 3..6
    "小児"
  when 7..12
    "子供"
  when 13..18
    "若者"
  else
    "大人"
  end
end

これは範囲イテレーター（1..3は[1, 2, 3]）を使ってるので少し特殊ですが、elsifに置き換えることができます。

繰り返し

while文

while文は条件を満たす間は処理を行う処理です。例えば、簡単な例として

def countdown(n)
  while n > 0 do
    puts n
    n = n -1
  end
end

のような処理をすると、n > 0を満たす間はn = n - 1をするので、nから順にカウントダウンされていきます。

each文

for文と似たような文としてeach文と呼ばれるものがあります。

data = [1, 2, 3]
sumA = 0.0
sumB = 0.0
for num in data do
  sumA += num
end
data.each do |num|
  sumB += num
end

このようにどちらも同じ処理をしますが、each文を使うとよりシンプルかもしれません。

break, nextとは？

count = 0

("aa".."az").each do |str|
  count += 1
  if count % 3 != 0 then
    next
  end
  puts(str)
end

until

while文の逆で、条件を満たしていないああいだは繰り返すと行ったuntil文もあります。

さっきのコードを全く同じに書き直すと、

def countdown(n)
  while n <= 0 do
    puts n
    n = n -1
  end
end

修飾子

例えばxが負ならばxに-1を掛けるといったような処理を普通にif文で書くと、

if x < 0 then
  x *= -1
end

といったような感じになります。しかし、これだけの処理に3行も使うのはちょっとナンセンスですよね。

そこで、if修飾子を使うことで

x *= -1 if x < 0

のように1行で書くことができます。

これは、処理 if 条件式のようにifの右側に条件式を書くと、その条件式を満たす場合に左側の処理を実行するということを1行で書けます。

同様にして、whileやuntilなども対応しておりこれらは修飾子と呼ばれます。

Rubyには同じような書き方でも多くの書き方があります。 一番は読みやすいコードが大切なのでそこらへんは、次回のソフトウェア設計で少しお話します。

再帰関数

突然ですが次のコードはどのように動作するでしょうか?

def fac(n)
  return 1 if n == 0
  return n * fac(n-1)
end

これはnの階乗を返す関数です。例えば、n=3を入れた時の動作を見てましょう。

fac(3) => 3 * fac(2)
fac(2) => 2 * fac(1)
fac(1) => 1

順番に代入してみると、

fac(3) => 3 * 2 * 1 = 6

となります。

もちろんこれは、

def fac(n)
  ans = 1
  (1..n).each do |i|
    ans *= i
  end
  return ans
end

のように繰り返しを用いて書くこともできます。

その他に例えば次のような数列を求める関数を作ってみます。

\[\begin{align*} a_n &= a_{n-1} + a{n-2}\\ a_0 &= a_1 = 1 \end{align*}\]

これをそのまま再帰関数を使って実装してあげると、

def f(n)
  return 1 if n == 0 || n == 1
  return f(n-1) + f(n-2)
end

のように簡単に式をそのままの実装することが可能です。

ただし、この関数には無駄があります。

f(5) => f(4)+f(3)
     => (f(3)+f(2))+(f(2)+f(1))
     => ((f(2)+f(1))+(f(1)+f(0)))+((f(1)+f(0))+f(1))
     => (((f(1)+f(0))+f(1))+(f(1)+f(0)))+((f(1)+f(0))+f(1))
     => 3+2+2+1
     => 8

あれ、同じような値を何回か計算してますね。

def f_memo(n, dp)
  return dp[n] if dp[n] != nil
  return 1 if n == 0 || n == 1
  return dp[n] = f(n - 1, dp) + f(n - 2, dp)
end
f(n, Array.new(n))

こうすることで、結果をメモすることができるので効率よく計算することができます。

実際に実験してみましょう。

time f(30) => 224ms
f_new(30) => 103ms

のように明らかに実行時間が変わってます。

ちなみに時間計算量と呼ばれる、コンピュータが特定の手順に従って与えられた問題を解く際に必要とする手順の回数を元にすると、もともとの場合は\(O(N^2)\)ですが、メモ化するとそれぞれ1回ずづ計算されるだけなので\(O(1) \times N = O(N)\)にまで抑えられます。

このように結果をメモしながら再帰関数を呼び出す手法を、メモ化再帰や動的計画法(DP)といいます。

また、もしメモ化しないで行うとn=50とかだと全然終わらないと思います。

再帰関数の問題点と使い所

再帰関数はプログラミングにおいてはとても重要ですが、なんでも再帰関数にすれば良いというわけでありません。

試しにnに大きい数を代入してみます。

f(1000000)を実行してみると stack level too deepというエラーが出力され正常に計算することができません。

Stackは関数の戻るところを保存しておく領域です。例えば、再帰的に計算していき最後に戻っていきますが、その時の戻る関数を示します。

そのため、再帰関数を使うときは関数の呼び出しが深くなりすぎないように注意する必要があります。そなる場合は、そもそものアルゴリズムの効率が悪い場合が大半かも。

また、先程のフィボナッチ数列の例ではそもそも繰り返しを使って実装しても\(O(N)\)の計算量で行えるため、わざわざ再帰関数を使う必要はありません。

ポイントとして、再帰関数を使うべき理由があるならば使ったほうが良いですが、無意味に再帰関数を使うのはあまりおすすめできません。

では、一体どのような場合に再帰関数を使えば良いのでしょうか。一概には言い切れませんが、探索をする場合には有用だったりします。

特に動的計画法を使う際には有用ですが、ここでは少しむずかしいので省略します。

再帰関数は漸化式と相性が良いです

DPを使うことこのように実装できます。

演習

演習問題3a

1, 2, 5セントのコインがそれぞれn枚あります。その中から何枚か選んで合計金額がちょうどxセントになる方法が何通り有るか求める関数getWay(n,x)を作成する。

制約
5 <= A,B,C <= 30
50 <= X <= 300

入出力例

getWay(12, 76) => 23

演習問題3b

NxNの正方行列matが与えられた時、その転置行列を求める関数trans(mat)を作成せよ。

制約
2 <= N <= 10
要素xは10以下の整数として与えられる

入出力例

trans([[1,2,3],[4,5,6],[7,8,9]]) => [[1, 4, 7], [2, 5, 8], [3, 6, 9]]

演習問題3c

nとrが与えられた時、n個の要素からr個を選ぶ時何通りあるか求める関数comb(n,r)を作成せよ。

ヒント数学な性質を利用すると簡単に実装できます。

\[nC_r = \left\{ \begin{array}{ll} 1 & r=0 , r=n \\ _{n-1}C_r + _{n-1}C_{r-1} & othersize \end{array} \right.\]

制約
0 <= n, r<=30
ただし、 r <= n

入出力例

comb(19, 17) => 171

以下上級者向け問題

演習問題3d

動的計画法を用いた探索と演習(少し難しめ)

N個の足場があります。足場には 1,2,…,N と番号が振られています。足場の高さが配列として与えられます。足場 i にいるとき、足場 i+1 または i+2 へジャンプする。このとき、ジャンプ先の足場を j とすると、コスト ∣h_i−h_j∣ を支払う。カエルが足場Nに辿り着くまでに支払うコストの総和の最小値を求める関数、getMinCost(h)を作成する。

AtCorder改題

制約
高さは1以上100以下の整数
Nはsizeで取得

入出力例

getMinCost([10, 30, 40, 20]) => 30

第3回 複雑な制御構文と再帰関数

目次

先週の復習

配列

制御構文

条件分岐

関係演算子

論理演算子

繰り返し

復習問題(3rev)

今回の内容

複雑な制御構文

条件分岐

おまけ unless

case文

繰り返し

while文

each文

break, nextとは？

until

修飾子

再帰関数

再帰関数の問題点と使い所

演習

演習問題3a

演習問題3b

演習問題3c

以下上級者向け問題

演習問題3d

動的計画法を用いた探索と演習(少し難しめ)

第3回複雑な制御構文と再帰関数