【アルゴリズム】【Ruby】アルゴリズム と ブロック化 ~素数の洗い出し
ここのサイトを読んでアルゴリズムの勉強をしている。
目指せ!脱エクレア!(違う)
詳しくはこちら
素数を洗い出す その1
今、一番小さい素数2がs(0)に入っている。
3はそれより小さい素数s(0)=2で割り切れないので、素数でありこれをs(1)に代入する。
4はそれより小さい素数s(0)=2で割り切れるので、素数ではない。
5はそれより小さい素数s(0)=2、s(1)=3でも割り切れないので素数であり、s(2)に代入する。
6はそれより小さい素数s(0)=2で割り切れるので、素数ではない。
ある数nは、それより小さい素数s(0),s(1),s(2),・・・,s(i)で割り切れなければ素数であり、s(i+1)に代入する。偶数は素数でないことを利用して、3から5,7,9,・・・と奇数のみを考えていく。
http://www5c.biglobe.ne.jp/~ecb/algorithm/5_5.html
なるほど。実装してみよう。
arr = (2..100).to_a s =[2] arr.each do |a| next if a%2 == 0 is_sosu = true s.each do |b| if a % b == 0 is_sosu = false end end s << a if is_sosu end p s
■実行結果
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
ふーん。
素数を洗い出す その2
「エラトステネスのふるい」をつかって実装する。
http://www5c.biglobe.ne.jp/~ecb/algorithm/5_6.html
int = 930 a =[190, 240, 290, 320, 450, 600, 630, 930] left = 0 right = a.size-1 while left <= right pivot = a[(left + right)/2] if int == pivot p (left + right)/2 exit elsif int < pivot then right = (left + right)/2 -1 else left = (left + right)/2 +1 end end p "arimasen"
■実行結果
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
バイナリサーチ
範囲を半分ずつ狭めていく方法。
練習問題を解いてみる。
http://www5c.biglobe.ne.jp/~ecb/algorithm/6_4b.html
int = 930 a =[190, 240, 290, 320, 450, 600, 630, 930] left = 0 right = a.size-1 while left <= right pivot = a[(left + right)/2] if int == pivot p (left + right)/2 exit elsif int < pivot then right = (left + right)/2 -1 else left = (left + right)/2 +1 end end p "arimasen"
■実行結果
7
なるほど。
whileって、うまく使ったら再帰がスマートに表現できる。
苦手意識があったけど、ちゃんと使おう。
テストデータを増やしてみよう。
せっかくRubyを使ってるんだからブロックを活用しよう。
def hoge i = 0 while i <2 int = (0..10).to_a.sample p int yield int ←ブロックの実行 i += 1 end end hoge do |int| result = -1 ←フラグ追加 a =[1, 3, 5, 7, 9] left = 0 right = a.size-1 while left <= right pivot = a[(left + right)/2] if int == pivot result = (left + right)/2 break ←ポイント elsif int < pivot then right = (left + right)/2 -1 else left = (left + right)/2 +1 end end if result == -1 p "arimasen" else p "index : " + result.to_s end end
■実行結果
8 "arimasen" 5 "index : 2"
ブロック化のポイント
ブロックで渡た処理をループさせている。
def hoge i = 0 while i <2 yield int ←ブロック実行 をループさせている i += 1 end end
今まではループ処理をexitで抜けていたけど、
ブロック化して処理自体を繰り返しているので、exitは使えなくなる。
フラグを追加して対応した。
メソッド切り出しが難しくなることを考えると、
exitやreturnを使って、大きく(=1番外側まで)ループを抜けるのは
あんまり良くない方法かも。
素数、終わり。。