rubyで再帰の練習。
ネタはここを参考にさせていただきました
#配列の和
sum.rb
def sum(arr)
return 0 if arr.empty? #配列が空のときは終了
top = arr.shift
top + sum(arr)
end
p sum([1,2,3,4,5]) #=> 15
#配列の長さ
length.rb
def length(arr)
return 0 if arr.empty? #配列が空のときは終了
arr.shift
1 + length(arr)
end
p length([1,2,3,4,5]) #=> 5
#配列内の最大値
max.rb
def max(arr)
return arr[0] if arr.length == 1 #数字が一つときはその一つが最大値
x = arr.shift
y = max(arr)
x > y ? x : y #max()で返されるのは先頭要素以外の中での最大値なので、それと先頭要素を比べて大きい方を返す
end
p max([1,10,3,9,100,5]) #=> 100
#配列内の最少値
min.rb
def min(arr)
return arr[0] if arr.length == 1 #数字が一つとき（一番簡単な場合）はその一つが最少値
x = arr.shift
y = min(arr)
x < y ? x : y #min()で返されるのは先頭要素以外の中での最少値なので、それと先頭要素を比べて少ない方を返せばいい
end
p min([1,10,3,9,100,5]) #=> 1
#すべての要素がブロックの条件を満たすかどうか
forall.rb
def forall?(arr,&b)
return true if arr.empty? #全要素走査し終わった時や要素がない時はtrueを返す。
top = arr.shift
b.call(top) && forall?(arr,&b) #すべて満たすか判定したいので && を使う。
end
odd = lambda{ |n| n % 2 == 0 }
p forall?([2,4,6],&odd) #=> true
p forall?([2,1,6],&odd) #=> false
#配列内に一つでもブロックの条件を満たすものがあるかどうか
exists.rb
def exists?(arr,&b)
return false if arr.empty? #全要素走査し終わった時や要素がない時や要素がない時はfalseを返す。
top = arr.shift
b.call(top) || exists?(arr,&b) #||なので、満たすものがあった時点でtrueが返る
end
even = lambda{ |n| n % 2 != 0 }
p exists?([2,4,6],&even) #=> false
p exists?([2,6,1],&even) #=> true
#条件がtrueとなるはじめの要素を返す
find.rb
def find(arr,&b)
return nil if arr.empty? #要素がない時はnilを返す。
top = arr.shift
b.call(top) ? top : find(arr,&b)
end
string = lambda{ |n| n.kind_of?(String) }
p find([1,2,"b",3,"c"],&string) #=> b
#先頭から n 個捨てて、残った配列を返す。
skip.rb
def skip(arr,n)
return nil if arr.empty? # n個捨てきる前に配列が空になったらはnilを返す。
if n == 0 # n個捨てきったら残りの配列を返す
arr
else
arr.shift
skip(arr,n - 1)
end
end
p skip([1,2,3,4],2) #=> [3,4]
p skip([1,2],3) #=> nil
p skip([],3) #=> nil
#先頭から n 個の要素を取り出す
take.rb
def take(arr,n,result=[])
return result if arr.empty? # n個取り出す前に配列が0になったらその時点での取り出し配列を返す。
if n == 0 # n個取り出しきったら、その取り出しきった配列を返す
result
else
result << arr.shift
take(arr,n - 1,result)
end
end
p take([1,2,3,4,5,6,7],3) #=> [1, 2, 3]
p take([1,2],3) #=> [1, 2]
p take([],3) #=> []
#先頭から n 個の要素を取り出す。ただし取り出す条件の指定つき
take_while.rb
def take_while(arr,n,result=[],&b)
arr_copy ||= Array.new(arr) #元の配列を壊さないようにコピー
return result if arr_copy.length == 0
if n == 0
result
else
top = arr_copy.shift
result << top if b.call(top)
take_while(arr_copy,n - 1,result,&b)
end
end
#先頭から4個までの間で5以上の値を取り出す
five_over = lambda{|n| n > 5}
arr = [1,10,6,4,2,3,6]
p take_while(arr,4,&five_over) #=> [10, 6]
p arr #=> [1, 10, 6, 4, 2, 3, 6]
#map
map.rb
def map(arr,result=[],&b)
return result if arr.empty?
top = arr.shift
result << b.call(top)
map(arr,result,&b)
end
double = lambda{|n| n * 2 }
p map([1,2,3],&double) #=> [2, 4, 6]
#条件を満たす要素のみを残した配列を返す
filter.rb
def filter(arr,result=[],&b)
arr_copy ||= Array.new(arr) #元の配列を壊さないようにコピー
return result if arr_copy.length == 0
top = arr_copy.shift
result << top if b.call(top)
filter(arr_copy,result,&b)
end
arr = [100,2,1,33,50,51]
fifty_over = lambda{|n| n > 50}
p filter(arr,&fifty_over) #=> [100, 51]
p arr #=> [100,2,1,33,50,51]
#map と filter を一度に行う
例えば、「1, 2, 3, 4, 5」という列と「偶数は 2 倍して返す」関数を渡すと、「4, 8」という列が返ります。
choose.rb
def choose(arr,result=[],&b)
return result if arr.empty?
top = arr.shift
result << b.call(top) if b.call(top) #ブロックの結果がtrueな値だったら、その値をresultへ入れる。
choose(arr,result,&b)
end
func = lambda{|n|
return n * 2 if n.even?
}
p choose([1,2,3,4,5],&func) #=> [4, 8]
#条件を満たす要素の列と満たさない要素の列の両方を返す
partition.rb
def partition(arr, satisfy=[],not_satisfy=[], &b)
arr_copy ||= Array.new(arr) #元の配列を壊さないようにコピー
return satisfy,not_satisfy if arr_copy.length == 0 #全部の要素の走査が終わったら結果を返して終了
top = arr_copy.shift
if b.call(top)
satisfy << top #条件満たす場合はsatisfy配列へ入れる
else
not_satisfy << top #条件満たさない場合はnot_satisfy配列へ入れる
end
partition2(arr_copy,satisfy,not_satisfy,&b)
end
#10を超える要素と超えない要素に分ける
ten_over = lambda{|n| n > 10}
arr = [100,2,1,33,50,51]
result = partition(arr,&ten_over)
p result[0] #=> [100, 33, 50, 51]
p result[1] #=> [2, 1]
#階乗
factorical.rb
def factorical(number)
if number.zero?
1
else
number * factorical(number - 1)
end
p factorical(3) #=> 6
#等差数列
arithmetic_seq.rb
def arithmetic_seq(start,interval,n,result=[])
return result if n == 0
result << start
start += interval
arithmetic_seq(start,interval,n - 1,result)
end
p arithmetic_seq(2,2,5) #=> [2, 4, 6, 8, 10]
#素数判定 メモ化
prime.rb
def prime?(n)
@cache ||= {} #計算済みのものをいれておくハッシュ
return @cache[n] if @cache.has_key?(n) #すでに計算済みならそれを返す
def divisible_count(target,n,count=0)
return true if n == 0 && count == 2
return false if n == 0
count += 1 if target % n == 0
divisible_count(target,n-1,count)
end
return false if n < 2 #0と1は素数じゃないので計算するまでもない
@cache[n] = divisible_count(n, n)
end
p prime?(47) #=> true
p prime?(2203) #=> true
p prime?(5000) #=> false
#フィボナッチ メモ化
fibonacci.rb
def fibonacci(n)
@cache ||= [] #計算済みのものをいれておく配列
return n if n <= 1
@cache[n] ||= fibonacci(n-1) + fibonacci(n-2)
return @cache[n]
end
puts fibonacci(10) #=> 55
#バブルソート
配列の先頭から、二つの要素を比較する。順序が不正であれば入れ替える。
最後まで辿り着いたら、再び先頭から。1回のソートで最高点が右へいく。
一度も入れ替えが発生しなければソート完了。
bubble_sort.rb
def bubble_sort(arr,size,idx=0) #arrはソートする配列、sizeは探索範囲で初期値は配列のlength。idxは添え字。
if size > 1 #sizeが 1 になったら終了。要素が一つということはソートするものがもうないということ。
#ここのif内の処理で最高点が右端へ固定していく。
if idx < size - 1
#隣り合う数字を比べて左が大きければ数字を交換する（大きい数字をひとつ右に移動させる）
if arr[idx] > arr[idx + 1]
arr[idx], arr[idx + 1] = arr[idx + 1], arr[idx]
end
#インデックスを1増やして再度隣り合う数字の比較を行っていく。
bubble_sort(arr,size,idx + 1)
end
#添え字が探索範囲より大きい場合はここにくる。
#ここに来るということは、最高点が右端に一つ固定できたということ。
#なので、探索範囲をひとつ狭めて再度ソート。
bubble_sort(arr, size - 1, 0);
end
arr
end
arr = [3,4,6,1,7,2]
p bubble_sort(arr,arr.length) #=> [1, 2, 3, 4, 6, 7]