【アルゴリズム】【Ruby】アルゴリズム と ブロック化 ～素数の洗い出し

ここのサイトを読んでアルゴリズムの勉強をしている。

目指せ！脱エクレア！（違う）

詳しくはこちら

素数を洗い出す　その１

今、一番小さい素数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]

ふーん。

素数を洗い出す　その２

「エラトステネスのふるい」をつかって実装する。
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/5_6b.html

ずれてなさそう。それほどイケてない感じではない、ってことか。。

バイナリサーチ

範囲を半分ずつ狭めていく方法。

練習問題を解いてみる。
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を使って、大きく（＝１番外側まで）ループを抜けるのは
あんまり良くない方法かも。

素数、終わり。。