はじめに
PaizaやAOJを通して競技プログラミングに多少親しんでいる文系僕にとって、他の言語と違い、まるで英語で書いているかのように直感的にコードが記述出来るRubyはまさに神器。
便利なメソッドを用いてやや複雑な命題を解いていくことは楽しい一方で、for文ループやクラスを必要とする複雑な問題に出会うと一体どのようにして解法を導きだせば良いのか・・？と途方に暮れることもしばしば。（例えばこのDice設問シリーズはⅡから全く手が出せません..)
以前掲載した素数列挙でも引っ掛かっていた、メソッドが行なっている作業を自前で実装出来るのだろうか？、ということを前提にRubyに用意されているいくつかのメソッドを基本的なアルゴリズムを通して、どういった作りになっているのかを明らかにして行きたいと思います。
※ベンチマークを取ってはおりませんので厳密にメソッド内で処理されている内容の記述とは異なりますが、凡その動きを表しているに止まりますのでご了承ください。
※ループ処理は他言語の方でも馴染みのあるwhile``forを主に使用し、ruby独特のmap``eachメソッドの使用は控えています。
簡単な繰り返し処理
number = [1,2,3,4,5]
number.sum #-> 15
number.inject(:+) #-> 15
1~5までの数字の合計値を求める場合、rubyではsumあるいはinjectメソッドを用いて簡単に記述することが出来ます。
N = 5 #value範囲1~5を表す為に便宜的に用意
sum = 0 #合計値を代入する変数を用意
value = 1 #合計値に加算する値を持つ変数を用意
while value <= N
sum += value
value += 1
end
puts sum #-> 15
同じくrubyでの記述になりますが、1~5までの各要素をsumにそれぞれ足しながら代入していく流れになっています。もう少し簡素な形で記述すれば以下のようになります。
sum = 0
for i in 1..5
sum += i
end
puts sum #-> 15
フィボナッチ数列
N = 8; i = 2
array = Array.new(8,0) #array = [0]*8でも同じ
array[1] = 1 #2番目の要素を１
while i < N
array[i] = array[i-2] + array[i-1] #3番目以降の要素は前２つの要素の和
i += 1
end
p array #->[0, 1, 1, 2, 3, 5, 8, 13]
メソッドとは異なりますが、８番目のフィボナッチ数列を求める場合はこのような形になります。
複数の処理方法が考えられますが、先ほどの例と同じfor文を利用した形は以下になります。
array = [0]*8; array[1]=1
for i in 2..7
array[i] = array[i-2] + array[i-1]
end
p array #->[0, 1, 1, 2, 3, 5, 8, 13]
配列の合計を求める[sumメソッド]
cart = [100,200,400,300]
p cart.sum #-> 1000
# p cart.inject(:+) #-> 1000
連続した数字の合計とは異なり、ばらばらな数値が配列の要素としてあってもsumメソッドは純粋に合計値を導き出します。
cart = [100,200,400,300]
sum = 0 #合計値を代入する変数を用意
N = cart.length; i = 0 #便宜的に要素の数をN、カウンタ変数の初期値を０に設定
while i < N
sum += cart[i]
i += 1
end
p sum #-> 1000
繰り返し処理との変更点は、カウンタ変数が配列の要素を順番に回している所です。
cart = [100,200,400,300]
sum = 0
for i in cart
sum += i
end
p sum #-> 1000
while文ではどうも見栄えが気になるので、こちらもfor文を利用した場合の形を記述。
配列の要素数を求める[length・countメソッド]
array = [1,2,3,4,5]
p array.length #-> 5
# p array.count #-> 5
sum(合計)メソッドと同じく、要素数にはlength(長さ)あるいはcount(カウント)メソッドを用いることで、直感的に求めることがrubyでは可能です。
array = [1,2,3,4,5]
count = 0 #要素数を代入する変数の初期値を０に
i = 0 #カウンタ変数の初期値を０に
while array[i] != nil #rubyでは要素が見つからない場合nilを返す為
count += 1
i +=1
end
p count #-> 5
要素が見つからなくなるまで、配列の個々の要素があり次第count変数に１を代入することで要素数を求めています。
array = [1,2,3,4,5]
count = 0
i = 0
loop do
if array[i] != nil
count +=1
else
break
end
i += 1
end
p array #-> 5
whileではなくloopを用いた場合ではやや処理の流れが見やすくなり
array = [1,2,3,4,5]
count = 0
for i in array
count += 1 if i != nil
end
forループでは変数iが配列の個別要素を指すので、より簡潔に記述することができます。
平均値を求める[sum/length]
array = [30,40,20,50]
p array.sum.quo(array.length).to_f #-> 35.0
# p array.sum/array.length #-> 35 /を用いた除算では小数点以下を考慮していない為、よろしくない。
合計÷個数=平均なので、先ほど紹介したsum``lengthメソッドを使えば一発ですね
小数点以下(Float)に対応させる為にto_fメソッドを使用しています。
to_fを省くと(35/1)として返ってくる為。
array = [30,40,20,50]
count = 0; sum = 0; i = 0 #個数・合計・カウンタ変数の初期値を０に
while array[i] != nil #arrayの要素がnilになるまでをループ条件
count += 1
sum += array[i]
i += 1
end
p sum.quo(count).to_f #-> 35.0
大切なことですがwhile文ではカウンタ変数をi+=1と明示する必要があるので、うっかり忘れてしまうこともあったりします・・。
array = [30,40,20,50]
count = 0; sum = 0
for i in array
sum += i #iはarrayの要素を指すため
count += 1 # if i != nil if説は有無に関わらず同じ結果になります
end
p sum.quo(count) #-> 35.0
for文は少し反則な気もしますが、ここで用いているカウンタ変数iはarray配列の個別の要素を指す為、while文にて配列の要素がnilになるまで〜としていた条件部分を省いて、count += 1とするだけで要素の数を求めることができます。
除算について
p 255/12 #-> 21 21という数字だけでは割り切れたのか、余りの有無など別途求める必要がある
p 255.div(12) #-> 21 divでは整数の商を返すので / を用いた場合と同じ結果となる
p 255/12.to_f #-> 21.25 to_fでfloatに変換することで、割り切った結果を表示出来る。
p 255.quo(12).to_f #-> 21.25 quoメソッドはfloatを含む結果を返す。
@scivolaさんよりコメントで頂きました、安易に/を用いた場合で見落としてしまう、小数点についての注意書きになります。
平均値を求めるのに、整数の商を用いたのではご指摘の通り元も子もありません・・。
p (0.1r*3.0r).to_f #-> 0.3 そのままでは(1/3)が返ってくるため、to_fでfloatに変換
p 0.1 * 3.0 #->0.30000000000000004
p 0.1 * 3 #->0.30000000000000004
プロを目指す人のためのRuby入門よりの引用になりますが、丸め誤差と呼ばれるものの紹介です。
小数点を含む乗算の結果が、期待した結果 ~~0.1*3がなぜ0.300004？~~にならない現象です。
Rationalクラスrメソッドを使い、有理数に変換して処理することで解決することが可能となります。
最大値を求める[max]
array = [5,2,6,9,4]
p array.max #-> 9
配列における最大値を求める場合でも、rubyではmaxと添えるだけで簡単に求めることが出来ます。
array = [5,2,6,9,4] #扱う値の範囲はここでは自然数
i = 0; max = 0 #カウンタ変数・最大値を格納する変数を用意
while array[i] != nil #配列の長さを求める場合と同じく、配列の次の要素が無くなるまで
max = array[i] if array[i] > max
i += 1
end
p max #-> 9
例えばテストの点数や商品の値段は０より大きい(=自然数）為、最大値を格納する変数の初期値をそれらより低い数にすれば求めることが出来るというものになります。
配列に格納する数値の範囲さえ分かっていれば、それに応じてmaxを変更するだけで済むのでシンプルかと思います。
array = [5,2,6,9,4]
max = 0
for i in array
max = i if i > max
end
p max #-> 9
for文では配列の長さを気にする必要がないことに加え、記述もwhile文と比べてシンプルになるので良いですね。
最小値を求める[min]
array = [5,2,6,9,4]
p array.min #->2
最大値を求めるmaxと同じく、ここではminメソッドを用いることで簡単に求めることが出来ます。
array = [5,2,6,9,4]
i = 0; min = 99
while array[i] != nil
min = array[i] if array[i] < min
i += 1
end
p min #-> 2
最大値を求める場合の真逆になります。
最小値を格納する変数の初期値を、配列に入れる要素の範囲より大きい数に設定することで、配列の要素と比較して求めることが出来ます。
array = [5,2,6,9,4]
min = 99
for i in array
min = i if i < min
end
p min
最大値の逆パターンですので説明を割愛します。
時刻の差を求める
time1 = "8:10:45"
time2 = "16:20:35"
# 時・分・秒に分割
h1,m1,s1 = time1.split(":").map(&:to_i)
h2,m2,s2 = time2.split(":").map(&:to_i)
# 時差が負の数になった場合の為にabsメソッドで絶対値に
diff = ((h1*3600+m1*60+s1)-(h2*3600+m2*60+s2)).abs
# 文字列に変換することで後に連結出来るように
H = (diff/3600).to_s; R = diff%3600; M = (R/60).to_s ; S = (R%60).to_s
diff = H+":"+M+":"+S
p diff #->"8:9:50"
メソッドとは異なりますが、秒単位に変換して差を求めた後、時分秒に再び戻すことで解いています。
より綺麗で簡素なコードで書ければよかったのですが、実力不足で申し訳ありません・・。
参考文献
杉浦 賢著「アルゴリズムのキホン」を参考にアルゴリズムの考え方などをまとめて作成しました。
並び替えと探索については次回以降、余裕があれば挑戦してみたいと思います。