算額あれこれ

算額問題をコンピュータで解きます

ユークリッドの互除法

良くあるパターンであるが,引数を入れ替える必要はない

Taglibro de H
http://ito-hi.blog.so-net.ne.jp/2009-11-05

  ## 最大公約数
  gcd <- function(a, b) {
    if (a < b) {
      t <- a
      a <- b
      b <- t
    }
    r <- a %% b
    return(ifelse(r == 0, b, gcd(b, r)))
  }


a が b より小さい場合でも,一回余分に関数呼び出しがあるだけで,ちゃんと解が求まる。

  gcd2 <- function(a, b) { # これでいいのだ
    r <- a %% b
    return(ifelse(r == 0, b, gcd2(b, r)))
  }


> gcd(168, 48)
[1] 24
> gcd(48, 168)
[1] 24

> gcd2(168, 48)
[1] 24
> gcd2(48, 168)
[1] 24