星期六, 八月 25, 2012

笨办法学R编程(5)


随着教程推进,基本的语法都接触得差不多了。当要解决某个具体问题时,只需要考虑用什么样的算法来整合运用这些函数和表达式。今天来解决Project Euler的第五个问题,该问题可以用很笨的暴力搜索法子来作,但是更聪明的作法是采用质因子分解的思路。即任何一个合数都可以分解为质数的乘积。为了完成这个题目,还需要学习一点点矩阵,以及和sapply函数相似的另一个函数apply。
# 预备练习
mat <- matrix(1:12,ncol=4)
print(mat)
t(mat)
colnames(mat) <- c('one','two','three','four')
rownames(mat) <- c('a','b','c')
print(mat)
apply(mat,1,sum)
apply(mat,2,sum)
sum(apply(mat,2,sum))
prod(apply(mat,2,sum)) 
# 之前建立的判断是否为质数的函数
findprime  <- function(x) {
  if (x %in% c(2,3,5,7)) return(TRUE)
  if (x%%2 == 0 | x==1) return(FALSE)
  xsqrt <- round(sqrt(x))
  xseq <- seq(from=3,to=xsqrt,by=2)
  if (all(x %% xseq !=0)) return(TRUE)
  else return(FALSE)
}
x = 1:20
prime <- x[sapply(x,findprime)]
 
#  欧拉问题五,寻找最小的能被1到20所整除的数。
# 建立分解质因子的函数
primefactor <- function(x,prime) {
  m <- length(prime)
  fac.count <- numeric(m)
  names(fac.count) <- prime
  for (i in 1:m) {
    prime.num <- prime[i]
    while (x %% prime.num == 0 & x !=1 ) {
      fac.count[i] <- fac.count[i] + 1
      x = x / prime.num
    }  
  }
  return(fac.count)
}
 
# 上面的函数负责对一个20以下的数分解为多个质数之积
# 返回每个质因子对应的自乘次数
primefactor(18,prime)
 
# 对1到20每个数进行质因子分解,形成一个表格
result <- t(sapply(1:20,primefactor,prime))
# 求每列的极大值
prime.power <- apply(result,2,max)
prod(prime^prime.power)

最终结果是232792560

4 条评论:

  1. 非常喜欢您写的这个系列,感谢您的分享,让我受益良多 :)

    回复删除
  2. 我是用辗转相除做的:

    gcd = function(a, b){
    if (b == 0) return (a)
    else return (gcd(b, a%%b))
    }

    a = 1
    b = 2
    while (b < 20){
    x = gcd(a, b)
    a = a * b / gcd(a, b)
    b = b + 1
    }
    print(a)

    回复删除