方案 - 斐波那契数列达到一定值
Scheme - List of Fibonacci numbers up to certain value
我正在尝试编写一个函数来创建斐波那契数列列表，但当在列表中找到某个值时停止，然后 return 是该列表（我希望这是有道理的）。
例如，如果我给它 fib-list(55)，函数应该 return：
(1 1 2 3 5 8 13 21 34 55)
所以这不是我想要的第 55 个斐波那契数，它是 UP TO 值 55 的列表。
到目前为止，我用于 returning 列表的代码如下所示：
; 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 还是非常陌生，所以我对这门语言的整体理解不是很好。所以请在告诉我为什么我的代码 sucks/doesn 没有意义时保持温和。
car 函数出了什么问题？
car 函数获取列表的第一个元素，但如果列表为空，则它没有第一个元素。 fs 列表一开始是空的。当您尝试获取空列表的第一个元素时，您会收到此错误消息：
> (car (list))
mcar: contract violation
expected: mpair?
given: ()
如果列表不为空，则它有第一个元素，没问题:
> (car (list 4 5 6))
4
按照您在评论中的意思
但是，您的评论 "Check if n is in list" 让我相信 (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).
为什么列表超过 55？
其中一个问题是 n 被遮蔽了，与此表达式中的方式相同：
> (let ([n 5])
(let ([n 10])
n))
10
正文中的n指的是10而不是5。
结果超过了 55，因为在循环内部 n 被遮蔽了，变成了一个不同的数字。我猜你在关于 "check if n is in list" 的评论中是指 "check if the original n is in list"。为此，您必须重命名 n 之一：
> (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)
反转
这更接近了，但是相反。您有 两个 基本案例，(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)
小数
这对于像 55 这样的大斐波那契数是正确的，但它仍然对小数有一些奇怪的事情：
> (fib-list 2)
(1 1)
> (fib-list 3)
(1 1 2)
如果您只希望它在到达 orig-n 时停止，那么可能不需要递减的 n 参数，实际上它会过早停止。删除它（并删除它的零检查）使 member 检查唯一的停止情况。
这是危险的，因为如果您给它一个非斐波那契数作为输入，它可能会进入无限循环。但是，它修复了少量示例：
; 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 或更高
I should have specified that I need to check if there is a number that is greater than OR equal to orig-n. Can I still use the member function to check for this or will I need to use something different?
您将不得不使用不同的东西。在本例中，文档中 member 的正上方是 memp function (you could also use exists）。 mem是member的缩写，p是"predicate"的缩写。它确定列表的任何成员是否匹配某个谓词。
> (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 or greater"，您必须定义如下函数：
(define (orig-n-or-greater? n)
(>= n orig-n))
作为主函数中的 local 函数，以便它可以引用 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)
(list) 创建一个空列表，并且在第一次迭代时您会到达 (car fs)，它会尝试将 car 应用于空列表，这是一个错误。
您的代码似乎对 n 的性质有点困惑。
你的描述说这是你想要的最大数字，但你正在递归，就像你想要 n:th 斐波那契数一样 - 终止于 (zero? n) 并递归于 (- n 1).
当您递归时，您仍在寻找不超过相同限制的数字。
因此，你不应该减少你的限制并终止于零，你应该不理会限制并在达到更大的数字时终止。
我会这样写：
- 初始列表是
(1 1)
- 每一步：
- 计算下一个斐波那契数
- 如果这大于限制，反转累加器列表并return它
- 否则，
cons它到累加器并用"new"最后两个斐波那契数递归。
在代码中：
(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))))))
这是使用连续传递样式的另一种方法。通过在我们的循环中添加一个延续参数，我们有效地创建了我们自己的 return 机制。此实现的一个独特 属性 是输出列表按正向顺序构建，当 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 作为循环的停止条件，而不是 Nth 项列表。这实际上更容易实现，因为不需要计算生成的术语数。
(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)
我正在尝试编写一个函数来创建斐波那契数列列表，但当在列表中找到某个值时停止，然后 return 是该列表（我希望这是有道理的）。
例如，如果我给它 fib-list(55)，函数应该 return：
(1 1 2 3 5 8 13 21 34 55)
所以这不是我想要的第 55 个斐波那契数，它是 UP TO 值 55 的列表。
到目前为止，我用于 returning 列表的代码如下所示：
; 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 还是非常陌生，所以我对这门语言的整体理解不是很好。所以请在告诉我为什么我的代码 sucks/doesn 没有意义时保持温和。
car 函数出了什么问题？
car 函数获取列表的第一个元素，但如果列表为空，则它没有第一个元素。 fs 列表一开始是空的。当您尝试获取空列表的第一个元素时，您会收到此错误消息：
> (car (list))
mcar: contract violation
expected: mpair?
given: ()
如果列表不为空，则它有第一个元素，没问题:
> (car (list 4 5 6))
4
按照您在评论中的意思
但是，您的评论 "Check if n is in list" 让我相信 (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).
为什么列表超过 55？
其中一个问题是 n 被遮蔽了，与此表达式中的方式相同：
> (let ([n 5])
(let ([n 10])
n))
10
正文中的n指的是10而不是5。
结果超过了 55，因为在循环内部 n 被遮蔽了，变成了一个不同的数字。我猜你在关于 "check if n is in list" 的评论中是指 "check if the original n is in list"。为此，您必须重命名 n 之一：
> (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)
反转
这更接近了，但是相反。您有 两个 基本案例，(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)
小数
这对于像 55 这样的大斐波那契数是正确的，但它仍然对小数有一些奇怪的事情：
> (fib-list 2)
(1 1)
> (fib-list 3)
(1 1 2)
如果您只希望它在到达 orig-n 时停止，那么可能不需要递减的 n 参数，实际上它会过早停止。删除它（并删除它的零检查）使 member 检查唯一的停止情况。
这是危险的，因为如果您给它一个非斐波那契数作为输入，它可能会进入无限循环。但是，它修复了少量示例：
; 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 或更高
I should have specified that I need to check if there is a number that is greater than OR equal to
orig-n. Can I still use thememberfunction to check for this or will I need to use something different?
您将不得不使用不同的东西。在本例中，文档中 member 的正上方是 memp function (you could also use exists）。 mem是member的缩写，p是"predicate"的缩写。它确定列表的任何成员是否匹配某个谓词。
> (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 or greater"，您必须定义如下函数：
(define (orig-n-or-greater? n)
(>= n orig-n))
作为主函数中的 local 函数，以便它可以引用 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)
(list) 创建一个空列表，并且在第一次迭代时您会到达 (car fs)，它会尝试将 car 应用于空列表，这是一个错误。
您的代码似乎对 n 的性质有点困惑。
你的描述说这是你想要的最大数字，但你正在递归，就像你想要 n:th 斐波那契数一样 - 终止于 (zero? n) 并递归于 (- n 1).
当您递归时，您仍在寻找不超过相同限制的数字。
因此，你不应该减少你的限制并终止于零，你应该不理会限制并在达到更大的数字时终止。
我会这样写：
- 初始列表是
(1 1) - 每一步：
- 计算下一个斐波那契数
- 如果这大于限制，反转累加器列表并return它
- 否则，
cons它到累加器并用"new"最后两个斐波那契数递归。
在代码中：
(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))))))
这是使用连续传递样式的另一种方法。通过在我们的循环中添加一个延续参数，我们有效地创建了我们自己的 return 机制。此实现的一个独特 属性 是输出列表按正向顺序构建，当 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 作为循环的停止条件，而不是 Nth 项列表。这实际上更容易实现，因为不需要计算生成的术语数。
(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)