减轻斐波那契 while 循环

Question

这个问题让我很头疼，想不通。问题是编写 R 函数，它将 return 每个斐波那契数等于或小于 n。

到目前为止，我已经尝试制作 while 循环。

vast <- function(n) {
 if (n==1) return(1)
 x <- c(1,1)
 while (length(x)-1 < n) {
  pos <- length(x)
  new <- x[pos-1] + x[pos]
  x <- c(x,new)
  }
 x<-x[x <= n]
 return(x)
 }

除了当我尝试 return 作品时，它就像魅力一样。那时 R 程序开始无限计算，课程包卡住了。

解决方案也可以写成假设 n 是斐波那契数。有没有办法减轻这个循环，例如使用 break 或 next 语句还是从不同角度处理问题会更容易？

Answer 1

代码按原样提供了正确的输出，但是对于大数字来说它非常慢。例如，在我的机器上，vast(100000)（结果中只有 25 个元素）需要 10 多秒才能达到运行，然后以指数方式减慢。

速度慢的原因是您的 while 条件正在测试向量是否具有 n-1 个元素，而不是最后一个/最大向量为 [=14= 的向量的基本要求].对于 vast(100000) 的情况，您正在创建一个包含 100,000 个元素的向量，而答案最终只需要前 25 个元素。

此代码在 n = 10^5000 之后立即运行，而原始函数在我的机器上运行了 100k。唯一的变化是它现在检查向量中的最后一个数字是否大于 n，而不是检查向量是否有 n 个元素。

vast2 <- function(n) {
 if (n==1) return(1)
 x <- c(1,1)
 # while (length(x)-1 < n) {  # OLD
 while (max(x) < n) {        # NEW
  pos <- length(x)
  new <- x[pos-1] + x[pos]
  x <- c(x,new)
  }
 x<-x[x <= n]
 return(x)
 }

减轻斐波那契 while 循环

Lighten a fibonacci while loop

r

fibonacci