如何在方案中编写程序来查找整数列表的因子？如何将其扩展为任意大的输入？

Question

这是单个整数的代码，如何通过将列表作为参数传递到任意大的输入？

(define (factors n)
  (define (*factors d)
    (cond ((> d n) (list))
          ((= (modulo n d) 0) (cons d (*factors (+ d 1))))
          (else (*factors (+ d 1)))))
  (*factors 1))
            
(display (factors 1111111))
(newline)

Answer 1

如果您有一个针对一个值执行某些操作的过程，您可以使用 map 对列表的所有元素执行此操作。

(map factors '(50 256 1911))
; ==> ((1 2 5 10 25 50)
;      (1 2 4 8 16 32 64 128 256)
;      (1 3 7 13 21 39 49 91 147 273 637 1911))

Answer 2

"...如何通过将列表作为参数传递来扩展到任意大的输入？"

已发布的 *factors 过程描述的过程不是迭代的，即不是尾递归的，并且它将为大输入增加堆栈 space。我认为 OP 有兴趣找到此代码的尾递归版本以提高 space 效率。

您可以通过向辅助过程添加累加器将其转换为迭代过程。这允许将结果存储在累加器中并通过递归调用传递，而不需要在这些调用时进行任何进一步的操作return，即尾递归。

(define (factors-iter n)
  (define (iter d result)
    (cond ((> d n) (reverse result))
          ((zero? (modulo n d))
           (iter (+ d 1) (cons d result)))
          (else
           (iter (+ d 1) result))))
  (iter 1 '()))

以下是跟踪这些过程执行的结果：

> (factors-trace 8)
|(%factors 1 8)
| (%factors 2 8)
| |(%factors 3 8)
| |(%factors 4 8)
| | (%factors 5 8)
| | (%factors 6 8)
| | (%factors 7 8)
| | (%factors 8 8)
| | |(%factors 9 8)
| | |()
| | (8)
| |(4 8)
| (2 4 8)
|(1 2 4 8)
(1 2 4 8)

> (factors-iter-trace 8)
|(iter 1 8 ())
|(iter 2 8 (1))
|(iter 3 8 (2 1))
|(iter 4 8 (2 1))
|(iter 5 8 (4 2 1))
|(iter 6 8 (4 2 1))
|(iter 7 8 (4 2 1))
|(iter 8 8 (4 2 1))
|(iter 9 8 (8 4 2 1))
|(1 2 4 8)
(1 2 4 8)

此处factors-trace和factors-iter-trace是factors和factors-iter定义的略微修改版本，允许跟踪。您可以看到 %factors 进程的堆栈大小随着计算的进行而增加，但 iter 保持恒定的堆栈大小。

正如其他人已经回答的那样，将 factors-iter 与输入列表一起使用的最简单方法是使用 map:

> (map factors-iter '(4 42 314 2998))
((1 2 4) (1 2 3 6 7 14 21 42) (1 2 157 314) (1 2 1499 2998))

如何在方案中编写程序来查找整数列表的因子？如何将其扩展为任意大的输入？

How can write a program in scheme to find factors of a list of integer? how can extend it into arbitrarily large input?

scheme

integer

list

factors

cdr