アルゴリズムを学ぼう Ruby版

リスト1-0何も考えないpowmod関数.rb

def powmod(a,k,m)
  return a ** k % m
end

p powmod(3,2,7)
p powmod(3,2,6)
p powmod(3,2,5)
p powmod(3,2,4)

p powmod(3,(2**22),4)
# k＞22

# 23以上だとエラー
# warning: in a**b, b may be too big

#リファクタリング
def powmod(a,k,m)
  a ** k % m
end

リスト1-1.rb

def powmod(a,k,m)
	i = 0
	t = 1
	for i in 0..k
		t = (t*a)% m
	end
	return t
end

p powmod(3,2,7)
p powmod(3,2,6)
p powmod(3,2,5)

p powmod(3,(2**27),4)
# k＞27
# 27乗で20秒ほど

リスト1-2.rb

def powmod(a,k,m)
	return 1 if k == 0
	t = powmod(a, k / 2, m)
	t = t * t % m
	t = t * a % m if k % 2 == 1
	return t
end

# この行は指数を半分にしていって、二分探索のように計算。
# t = powmod(a, k / 2, m)

# この行は２で割って余るとき追加で計算
# t = t * a % m if k % 2 == 1

p powmod(3,2,7)
p powmod(3,2,6)
p powmod(3,2,5)

p powmod(3,(2**1000),4)
# k＞1000
# 1000乗でも1秒

# k＞10000
# SystemStackError

リスト1-3.rb

def boolf(v,vs)
	i = 0
	for i in 0..vs.length-1
		return true if vs[i] == v
	end
	return false
end

p boolf(3,[1,3,4,6,8])
p boolf(5,[1,3,4,6,8])
p boolf(-1,[1,3,4,6,8])
p boolf(15,[1,3,4,6,8])

#リファクタリング
def boolf(v,vs)
	vs.each do |i|
		return true if vs[i] == v
	end
	return false
end

p boolf(3,[1,3,4,6,8])
p boolf(5,[1,3,4,6,8])
p boolf(-1,[1,3,4,6,8])
p boolf(15,[1,3,4,6,8])

リスト1-4.rb

def boolf2(v, vs)
	return false if vs.length == 0

	left = 0
	right = vs.length
	while left + 1 < right do
		mid = left + (right - left) / 2

		if ( v < vs[mid])
			right = mid
		else
			left = mid
		end
	end
	return v == vs[left]
end

p boolf2(8,[0,1,2,3,4,5,6,7,8])
p boolf2(7,[0,1,2,3,4,5,6,7,8])
p boolf2(4,[0,1,2,3,4,5,6,7,8])
p boolf2(0,[0,1,2,3,4,5,6,7,8])
p boolf2(-3,[0,1,2,3,4,5,6,7,8])

リスト2-1.rb

#Rubyでの配列の作り方、5通り。
a = []
#a = Array.new
#a = %w(Ruby Python Haskell)
#.to_a #他のオブジェクトを配列に変換
#.split() #文字列を配列に変換
p a
p a[0]
p a[1]

リスト2-2ArrayListの定義.rb

#Rubyでリスト構造の実装 - バリケンのRuby日記 - Rubyist
#http://rubyist.g.hatena.ne.jp/muscovyduck/20060603/p1

#あとで

登場人物.txt

伯方涼子（はかた りょうこ）
明日木大学 2 年生
校内でも有名なトラブルメーカー。

日比野萌来（ひびの めぐる）
明日木大学 2 年生
落ち着いた性格の優等生。

澤戸うい（さわど うい）
明日木大学に入学してきた大学 1 年生。
喋る際に末尾に、「～っす」

倉科莉紗（くらしな りさ）
明日木大学技術育成部顧問
大学では、高度情報処理の授業を担当している。