如何在Lisp中将所有可被3或5整除的数字加起来？

Question

我昨天开始在Common Lisp中编程.现在我想找到1000或以下3或5的所有倍数的总和.我提出了:

(loop for n from 1 to 1000 when 
     (or 
      (eq (mod n 5) 0)
      (eq (mod n 3) 0))
     (sum n)))

我知道循环部分是有效的(loop for n from 1 to 1000 sum n)总结前1000个数字.我知道这些((eq (mod n 5) 0) (mod n 3) 0))部分是有效的.我知道它(or (eq (mod n 5) 0) (eq (mod n 3) 0))有用.所以它对我来说看起来像一个强大的程序,但是当我运行它时我得到错误:

1 =(SUM N)找到关键字期望在当前LOOP上下文之后得到LOOP子句:WHEN(OR(EQ(MOD 1000 5)0)(EQ(MOD 1000 3)0))1#.[SB-INT型的条件:SIMPLE-PROGRAM-ERROR]

我怀疑(sum n)or-statement之后出现了问题.但我不知道为什么会这样或者我如何解决它.有人可以帮助我,让我的第一个Lisp程序工作吗？

Answer 1

sum n不是 (sum n)

不要放在sum n括号内.该loop宏有自己的语法自己的领域特定语言.有了它,你会(loop for ... sum n).在此生产中,循环中的HyperSpec条目中给出了语法:

numeric-accumulation::= {count | counting | sum | summing | } 
                         maximize | maximizing | minimize | minimizing {form | it} 
                        [into simple-var] [type-spec] 

如果它听起来更好,你也可以写(loop for … summing n).这可能更像是一个自然的英语句子.

=,eql或者zerop,但不eq

在HyperSpec中查找函数,宏等是一种很好的做法.正如Rainer Joswig指出的那样,你不应该用它eq来比较数字.为什么？让我们在HyperSpec中查找它.例子包括:

(eq 3 3)
=>  true
OR=>  false
 (eq 3 3.0) =>  false
 (eq 3.0 3.0)
=>  true
OR=>  false
 (eq #c(3 -4) #c(3 -4))
=>  true
OR=>  false

和Notes部分说(重点补充):

打印时看起来相同的对象不一定彼此相等.由于使用了实习功能,打印相同的符号通常彼此相等.但是,具有相同值的数字不必是eq,并且两个相似的列表通常不相同.

允许实现随时制作字符和数字的"副本".结果是Common Lisp不能保证eq是真的,即使它的两个参数都是"同一个东西",如果那个东西是一个字符或数字.

对于数字,你需要别的东西. =是一个很好的通用数字比较,虽然它在这里比你需要的更多工作,因为它可以比较不同类型的数字.例如,(= 5 5.0)是真的.既然你只关心0,你可以使用zerop,但这仍然会比你需要做更多的工作,因为它也会检查其他数字类型.例如,(zerop #c(0.0 0.0))是真的.在这种情况下,既然(mod n …)会给你一个整数,你可以使用eql:

在以下情况中,eql的值对于两个对象x和y都是正确的:

1. 如果x和y是eq.
2. 如果x和y都是相同类型和相同值的数字.
3. 如果它们都是代表相同字符的字符.

因此,你可以使用(or (eql (mod n 3) 0) (eql (mod n 5) 0)).

其他方式这样做

现在,你的问题是关于一个特定的循环语法,并且有一些关于相等运算符的要点.然而,由于一些其他的答案已经看过其他的方法可以做到这一点,我认为这是值得指出的是,有很多更有效的方式来做到这一点.首先,让我们看一下总结给定限制下所有数字的倍数的方法.例如,对于数字3和包含限制26,我们有总和

？
= 3 + 6 + 9 + 12 + 15 + 18 + 21 + 24
=(3 + 24)+(6 + 21)+(9 + 18)+(12 + 15)
= 27 + 27 + 27 + 27

一般来说,如果你尝试使用几个不同的数字,你可以计算出一个包含限制l和一个数字n,你将加上一对数字,如果有一个奇数个倍数,你可以加一个可选的半数n小于l.我不打算完成整个推导,但你可以最终得到

(defun sum-of-multiples-below-inclusive (limit divisor)
  (multiple-value-bind (quotient remainder) 
      (floor limit divisor)
    (let ((pair (+ (- limit remainder) divisor)))
      (multiple-value-bind (npairs half-pair)
          (floor quotient 2)
        (+ (* npairs pair)
           (if (oddp half-pair)
               (floor pair 2)
               0))))))

然后,要找出小于给定数字的倍数的总和,您可以从限制中减去一个:

(defun sum-of-multiples-below (limit divisor)
  (sum-of-multiples-below (1- limit) divisor))

然后,为了扩展到你的情况,有多个除数,你需要添加一些这些数字,然后减去那些被计算两次的数字.例如,在你的情况下:

(+ (sum-of-multiples-below 1000 3)
   (sum-of-multiples-below 1000 5)
   (- (sum-of-multiples-below 1000 15)))
;=> 233168


(loop for i from 1 below 1000 
   when (or (eql 0 (mod i 3))
            (eql 0 (mod i 5)))
   sum i)
;=> 233168

现在,使用time天真可能导致误导性的结果,但SBCL在评估形式之前编译形式,所以这并不太可怕.这是一个非常非常小的微基准测试,但是要看一下每种形式中使用的周期数:

(time (+ (sum-of-multiples-below 1000 3)
         (sum-of-multiples-below 1000 5)
         (- (sum-of-multiples-below 1000 15))))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  11,327 processor cycles
  0 bytes consed

(time (loop for i from 1 below 1000 
         when (or (eql 0 (mod i 3))
                  (eql 0 (mod i 5)))
         sum i))

Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  183,843 processor cycles
  0 bytes consed

使用封闭形式要快得多.如果我们使用更高的限制,则不同的更明显.我们来看看100,000:

(time (+ (sum-of-multiples-below 100000 3)
         (sum-of-multiples-below 100000 5)
         (- (sum-of-multiples-below 100000 15))))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  13,378 processor cycles
  0 bytes consed

(time (loop for i from 1 below 100000
         when (or (eql 0 (mod i 3))
                  (eql 0 (mod i 5)))
         sum i))

Evaluation took:
  0.007 seconds of real time
  0.004000 seconds of total run time (0.004000 user, 0.000000 system)
  57.14% CPU
  18,641,205 processor cycles
  0 bytes consed

对于10,000,000,这些数字甚至更加惊人:

(time (+ (sum-of-multiples-below 10000000 3)
         (sum-of-multiples-below 10000000 5)
         (- (sum-of-multiples-below 10000000 15))))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  13,797 processor cycles
  0 bytes consed

(time (loop for i from 1 below 10000000
         when (or (eql 0 (mod i 3))
                  (eql 0 (mod i 5)))
         sum i))

Evaluation took:
  0.712 seconds of real time
  0.712044 seconds of total run time (0.712044 user, 0.000000 system)
  100.00% CPU
  1,916,513,379 processor cycles
  0 bytes consed

其中一些Project Euler问题非常有趣.他们中的一些人有一些非常直接的天真解决方案,适用于小投入,但根本不能很好地扩展.

Answer 2

我会像这样格式化代码:

(loop for n from 1 below 1000
      when (or (zerop (mod n 3))
               (zerop (mod n 5)))
      sum n))

• 少一行
• when 在一行的开头
• 没有必要or独自一人
• 条款中LOOP没有括号
• 使用 below

这种Loop宏可以追溯到70年代早期的Interlisp,早在Common Lisp存在之前.