ユークリッドの互除法とは？
⇨最大公約数を求める方法
最大公約数とは？
⇨2つ以上の整数に共通する公約数のうち、最も大きい数のことを指します.
例 12と18の最大公約数
公約数: 1, 2, 3, 6 この中で最大の公約数は6なので６が最大公約数になります
- 公約数とは12と18の両方の数字を割り切ることができる数字=余りが０になる数字. この時1, 2, 3, 6は12と18を割り切ることができる。
ユークリッドの互除法の考え方
①数字1 ÷ 数字２ = 商と余りを求める ②数字2を数字１に代入する ③余りを数字２に代入する ④,①~③までを余りが０になるまで繰り返す ⑤,余りが０になった時の数字2が最大公約数になる
ユークリッドの互除法を用いてrubyで最大公約数を求める
#1~10までのランダムな整数を3個作成し配列に格納する 。例numbers= [7,9,10]
numbers = Array.new(3){rand(1..10)}
#numbersの最初の要素(7)をcurrent_gcd に格納。この時numbers_arrayは[9,10]になる
current_gcd = numbers.shift
#gcdとはgreatest common divisor（最大公約数)という意味
def gcd(divider,remainder )
return divider if remainder == 0
gcd(remainder ,divider % remainder )
end
numbers.each do |number|
current_gcd = gcd(current_gcd,number) #最初は7と9の最大公約数を求める
end
puts current_gcd #出力結果1
個人的に勉強になった部分
- メソッドの実引数に数式を渡すと計算結果が仮引数に代入される
# 合計金額を計算して表示するメソッド
def calc_price(total_price) #total_priceに1500が代入される
puts "商品の合計金額は #{total_price} 円です"
end
# 実引数で商品数と単価を掛け算して合計金額を計算して渡す
calc_price(3 * 500) # 3個の商品がそれぞれ500円
- メソッドの中で同名のメソッドを実行すると無限ループになる
def calc_price(total_price)
puts "商品の合計金額は #{total_price} 円です"
calc_price(3 * 500)
end
calc_price(3 * 500)
#出力結果a.rb:9:in `puts': stack level too deep (SystemStackError)このようなエラーが吐かれる.
無限ループに入ってメモリがいっぱいになったから中断されたようです
余談
2つの数の最小公約数を求めるには↓の公式を使う
num1 * num2 / gcd(num1,num2)
