Scheme - 斐波纳契数列表，达到一定值

Question

我正在尝试编写一个创建斐波纳契序列列表的函数，但在列表中找到某个值时停止，然后返回该列表（我希望这是有意义的）。

所以例如，如果我给它fib-list（55），函数应该返回：(1 1 2 3 5 8 13 21 34 55)

所以它不是我想要的第55个斐波那契数字，它的列表值为55。

到目前为止我返回列表的代码如下所示：

; Create a list of the fibonacci sequence up to n.
(define (fib-list n)
  ; n = n, f2 = 1, f1 = 1, fs = a list.
  (let loop ((n n) (f2 1) (f1 1) (fs (list)))
    (cond
      ; If n = 0, return reversed list.
      ((zero? n) (reverse fs))
      ; Check if n is in list. If so, return list.
      ((equal? n (car fs)) fs)
      ;Else, find the next fibonacci number and add it to the list.
      (else (loop (- n 1) f1 (+ f2 f1) (cons f2 fs))))))

(display (fib-list 55))

我的主要问题是找到一个元素是否在列表中，因为目前我只是在我尝试编写((equal?语句的行上出错。

错误说：

mcar: contract violation
  expected: mpair?
  given: '()

我对Scheme还是非常新的，所以我对整个语言的理解并不是很好。因此，请告诉我为什么我的代码糟透/没有意义。

Answer 1

(list)创建一个空列表，在第一次迭代中你会到达(car fs)，它试图将car应用于空列表，这是一个错误。

您的代码似乎对n的性质有点困惑。 你的描述说它是你想要的最大数字，但你正在递归，就像你想要n:th斐波那契数字一样 - 终止于(zero? n)并递归(- n 1)。

当您递归时，您仍然在寻找达到相同限制的数字。 因此，您不应该减少限制并终止于零，您应该单独保留限制并在达到更大数字时终止。

这是我写它的方式：

• 最初的名单是(1 1)
• 在每一步： 计算下一个斐波纳契数 如果这大于限制，则反转累加器列表并将其返回 否则，cons它到累加器并递归“新”最后两个斐波纳契数。

在代码中：

(define (fib-list n)
  (let loop ((f2 1) (f1 1) (fs '(1 1)))
    (let ((next (+ f1 f2)))
      (if (> next n) 
          (reverse fs)
          (loop f1 next (cons next fs))))))

Answer 2

这是另一种使用延续传递方式的方法。通过在循环中添加continuation参数，我们有效地创建了自己的返回机制。此实现的一个独特属性是输出列表以正向顺序构建，当n达到零时不需要反转。

(define (fib-list n)
  (let loop ((n n) (a 0) (b 1) (return identity))
    (if (zero? n)
        (return empty)
        (loop (sub1 n)
              b
              (+ a b)
              (lambda (rest) (return (cons a rest)))))))

(fib-list 10)
;; '(0 1 1 2 3 5 8 13 21 34)

仔细阅读你的问题，在fib-list(N)你需要N作为循环的停止条件，而不是列表中的第N个术语。这实际上更容易实现，因为不需要计算生成的术语数量。

(define (fib-list max)
  (let loop ((a 0) (b 1) (return identity))
    (if (> a max)
        (return empty)
        (loop b
              (+ a b)
              (lambda (rest) (return (cons a rest)))))))

(fib-list 55)
;; '(0 1 1 2 3 5 8 13 21 34 55)

(fib-list 1000)
;; '(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987)

Answer 3

What's going wrong with the car function?

car函数接受列表的第一个元素，但如果列表为空，则它没有第一个元素。 fs列表开头是空的。当您尝试获取空列表的第一个元素时，您会收到以下错误消息：

> (car (list))
mcar: contract violation
  expected: mpair?
  given: ()

如果列表不为空，那么它有第一个元素，并且没关系：

> (car (list 4 5 6))
4

Following what you meant in the comment

但是，你的评论“检查n是否在列表中”让我相信(equal? n (car fs))不是你想要的。用于确定元素是否在列表中的函数称为member。

#!r6rs
(import (rnrs base)
        (rnrs lists))

> (if (member 4 (list 1 2 4 8))
      "it's in the list"
      "go fish")
"it's in the list"
> (if (member 5 (list 1 2 4 8))
      "it's in the list"
      "go fish")
"go fish"

因此，用(equal? n (car fs))替换(member n fs)测试，您的代码如下所示：

; Create a list of the fibonacci sequence up to n.
(define (fib-list n)
  ; n = n, f2 = 1, f1 = 1, fs = a list.
  (let loop ((n n) (f2 1) (f1 1) (fs (list)))
    (cond
      ; If n = 0, return reversed list.
      ((zero? n) (reverse fs))
      ; Check if n is in list. If so, return list.
      ((member n fs) fs)
      ;Else, find the next fibonacci number and add it to the list.
      (else (loop (- n 1) f1 (+ f2 f1) (cons f2 fs))))))

> (fib-list 55)
(10946 6765 4181 2584 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1)

这不是你想要的答案;你想要(1 1 2 3 5 8 13 21 34 55)。

Why is the list going past 55?

其中一个问题是n被遮蔽，就像在这个表达式中一样：

> (let ([n 5])
    (let ([n 10])
      n))
10

身体中的n指的是10而不是5。

结果是超过55因为在循环内部n被遮蔽并且变成了不同的数字。我猜你的评论“检查n是否在列表中”，你的意思是“检查原始n是否在列表中”。要做到这一点，你必须重命名其中一个ns：

> (let ([orig-n 5])
    (let ([n 10])
      orig-n))
5

在您的代码的上下文中：

; Create a list of the fibonacci sequence up to n.
(define (fib-list orig-n)
  ; n = n, f2 = 1, f1 = 1, fs = a list.
  (let loop ((n orig-n) (f2 1) (f1 1) (fs (list)))
    (cond
      ; If n = 0, return reversed list.
      ((zero? n) (reverse fs))
      ; Check if orig-n is in list. If so, return list.
      ((member orig-n fs) fs)
      ;Else, find the next fibonacci number and add it to the list.
      (else (loop (- n 1) f1 (+ f2 f1) (cons f2 fs))))))

> (fib-list 55)
(55 34 21 13 8 5 3 2 1 1)

Reversing

这是更接近的，但它是相反的。你有两个基本案例，(zero? n)案例和(member orig-n fs)案例。其中一个是逆转的，其中一个不是。更改它们以调用反向修复它：

; Create a list of the fibonacci sequence up to n.
(define (fib-list orig-n)
  ; n = n, f2 = 1, f1 = 1, fs = a list.
  (let loop ((n orig-n) (f2 1) (f1 1) (fs (list)))
    (cond
      ; If n = 0, return reversed list.
      ((zero? n) (reverse fs))
      ; Check if orig-n is in list. If so, return reversed list.
      ((member orig-n fs) (reverse fs))
      ;Else, find the next fibonacci number and add it to the list.
      (else (loop (- n 1) f1 (+ f2 f1) (cons f2 fs))))))

> (fib-list 55)
(1 1 2 3 5 8 13 21 34 55)

Small numbers

这对于像55这样的大型斐波那契数字是正确的，但它对小数字仍然有些奇怪：

> (fib-list 2)
(1 1)
> (fib-list 3)
(1 1 2)

如果你只想让它在到达orig-n时停止，那么也许不需要减少n参数，实际上是让它太早停止。删除它（并删除零检查）使member检查唯一的停止案例。

这很危险，因为如果你给它一个非Fibonacci数作为输入它可能会进入一个无限循环。但是，它修复了一些小数例：

; Create a list of the fibonacci sequence up to n.
; The `orig-n` MUST be a fibonacci number to begin with,
; otherwise this loops forever.
(define (fib-list orig-n)
  ; f2 = 1, f1 = 1, fs = a list.
  (let loop ((f2 1) (f1 1) (fs (list)))
    (cond
      ; Check if orig-n is in list. If so, return reversed list.
      ((member orig-n fs) (reverse fs))
      ;Else, find the next fibonacci number and add it to the list.
      (else (loop f1 (+ f2 f1) (cons f2 fs))))))

> (fib-list 55)
(1 1 2 3 5 8 13 21 34 55)
> (fib-list 2)
(1 1 2)
> (fib-list 3)
(1 1 2 3)

最后，考虑如果你给它一个像56这样的数字会发生什么。

> (fib-list 56)
;infinite loop

这是一个你尚未在你的问题中指定的设计决定，但有办法解决它。

更新：orig-n或更高

我应该指定我需要检查是否有一个大于OR的数字等于orig-n。我仍然可以使用member函数来检查这个或者我需要使用不同的东西吗？

你将不得不使用不同的东西。在文档中的member上方是memp函数（在这种情况下你也可以使用exists）。 mem是成员的缩写，而p是“谓词”的缩写。它确定列表的任何成员是否与某个谓词匹配。

> (if (memp positive? (list -4 -2 -3 5 -1))
      "one of them is positive"
      "go fish")
"one of them is positive"
> (if (memp positive? (list -4 -2 -3 -5 -1))
      "one of them is positive"
      "go fish")
"go fish"
> (define (five-or-greater? n)
    (>= n 5))
> (if (memp five-or-greater? (list -4 -2 -3 6 -1))
      "one of them is equal to 5 or greater"
      "go fish")
"one of them is equal to 5 or greater"
> (if (memp five-or-greater? (list -4 -2 -3 4 -1))
      "one of them is equal to 5 or greater"
      "go fish")
"go fish"

要将它用于“orig-n或更高”，您必须定义一个函数，如：

(define (orig-n-or-greater? n)
  (>= n orig-n))

作为主函数内部的局部函数，以便它可以引用orig-n。然后你可以像(memp orig-n-or-greater? fs)一样使用它。

; Create a list of the fibonacci sequence up to n.
(define (fib-list orig-n)
  (define (orig-n-or-greater? n)
    (>= n orig-n))
  ; f2 = 1, f1 = 1, fs = a list.
  (let loop ((f2 1) (f1 1) (fs (list)))
    (cond
      ; Check if orig-n or greater is in list. If so, return reversed list.
      ((memp orig-n-or-greater? fs) (reverse fs))
      ;Else, find the next fibonacci number and add it to the list.
      (else (loop f1 (+ f2 f1) (cons f2 fs))))))

> (fib-list 3)
(1 1 2 3)
> (fib-list 55)
(1 1 2 3 5 8 13 21 34 55)
> (fib-list 56)
(1 1 2 3 5 8 13 21 34 55 89)