スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[Ruby][アルゴリズム入門]ユークリッドの互除法

第一章「ウォーミングアップ」 目次

1-0 アルゴリズムとは
1-1 漸化式
1-2 写像
1-3 順位付け
1-4 ランダムな順列
1-5 モンテカルロ法
1-6 ユークリッドの互除法
1-7 エラトステネスのふるい

ユークリッドの互除法(その1)

2つの整数m、nの最大公約数をユークリッド(Euclid)の互除法を用いて求める。

2つ以上の正の整数に共通な約数(公約数)のうち最大のものを最大公約数といいます. 例 12 と 18 の公約数は,1,2,3,6 で, 6 が最大公約数

最大公約数と最小公倍数
# encoding: cp932

puts "1つ目の整数を入力してください"
m = gets.chomp.to_i
puts "2つ目の整数を入力してください"
n = gets.chomp.to_i

while m != n
  if m > n
    m = m - n
  else
    n = n - m
  end
end

puts "最大公約数=#{m}"


ユークリッドの互除法(その2)

mとnの差が大きいときは減算(m-n)の代わりに剰余(m%n)を用いた方が効率がよい。この方法でmとnの最大公約数を求める。

1:mをnで割った余りをkとする。
2:mにnを、nにkを入れる。
3:kが0でなければ1に戻る。
4:mが求める最大公約数である。
# encoding: cp932

print "一つ目の整数を入力してください:"
m = gets.chomp.to_i
print "二つ目の整数を入力してください"
n = gets.chomp.to_i

begin
  k = m % n
  m = n
  n = k
end while k != 0

print "最大公約数=#{m}"

テーマ : プログラミング - ジャンル : コンピュータ

コメント
コメントの投稿
管理者にだけ表示を許可する

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。