0

我刚开始学习 common lisp，所以我一直在研究项目 euler 问题。这是我的解决方案（在https://github.com/qlkzy/project-euler-cl的帮助下）。你们对风格的改变有什么建议吗？

; A palindromic number reads the same both ways. The largest palindrome made 
; from the product of two 2-digit numbers is 9009 = 91 99.
; Find the largest palindrome made from the product of two 3-digit numbers.

(defun num-to-list (num)
    (let ((result nil))
        (do ((x num (truncate x 10)))
            ((= x 0 ) result)
            (setq result (cons (mod x 10) result)))))

(defun palindrome? (num) 
    (let ((x (num-to-list num)))
        (equal x (reverse x))))

(defun all-n-digit-nums (n)
    (loop for i from (expt 10 (1- n)) to (1- (expt 10 n)) collect i))

(defun all-products-of-n-digit-nums (n)
    (let ((nums (all-n-digit-nums n)))
        (loop for x in nums
            appending (loop for y in nums collecting (* x y)))))

(defun all-palindromes (n)
    (let ((nums (all-products-of-n-digit-nums n)))
        (loop for x in nums
            when (palindrome? x) collecting x)))

(defun largest-palindrome (n)
    (apply 'max (all-palindromes 3)))

(print (largest-palindrome 3))
4

3 回答 3

1

Barnar 的解决方案很棒，但是只有一个小错字，返回结果应该是：

(defun largest-palindrome (n)
  (loop with start = (expt 10 (1- n))
        and end = (1- (expt 10 n))
        for i from start to end
        maximize (loop for j from i to end
                       for num = (* i j)
                       when (palindrome? num)
                       maximize num)))
于 2012-12-23T23:36:49.117 回答
0 
(setq list (cons thing list))

可以简化为：

(push thing list)

我对您的代码的其他评论与其说是关于 Lisp 风格，不如说是关于算法。创建所有这些中间数字列表似乎是一种糟糕的方法，只需编写嵌套循环来计算和测试数字。

(defun all-palindromes (n)
  (loop for i from (expt 10 (1- n)) to (1- (expt 10 n))
    do (loop for j from (expt 10 (1- n)) to (1- (expt 10 n))
             for num = (* i j)
         when (palindrome? num)
           collect num)))

但是LOOP有一个功能可以使用：MAXIMIZE. 因此COLLECT，您可以：

(defun largest-palindrome (n)
  (loop with start = (expt 10 (1- n))
        and end = (1- (expt 10 n))
        for i from start to end
    do (loop for j from start to end
             for num = (* i j)
         when (palindrome? num)
           maximize num)))

这是另一个优化：

(defun largest-palindrome (n)
  (loop with start = (expt 10 (1- n))
        and end = (1- (expt 10 n))
        for i from start to end
    do (loop for j from i to end
             for num = (* i j)
         when (palindrome? num)
           maximize num)))

使内部循环从开始i而不是避免检查和start检查的冗余。M*NN*M

于 2012-12-22T22:42:19.523 回答
0

下面的例子有点做作，但它发现回文的迭代次数比原来的方法少得多：

(defun number-to-list (n)
  (loop with i = n
     with result = nil
     while (> i 0) do
       (multiple-value-bind (a b)
           (floor i 10)
         (setf i a result (cons b result)))
     finally (return result)))

(defun palindrome-p (n)
  (loop with source = (coerce n 'vector)
       for i from 0 below (floor (length source) 2) do
       (when (/= (aref source i) (aref source (- (length source) i 1)))
         (return))
       finally (return t)))

(defun suficiently-large-palindrome-of-3 ()
  ;; This is a fast way to find some sufficiently large palindrome
  ;; that fits our requirement, but may not be the largest
  (loop with left = 999
     with right = 999
     for maybe-palindrome = (number-to-list (* left right)) do
       (cond
         ((palindrome-p maybe-palindrome)
          (return (values left right)))
         ((> left 99)
          (decf left))
         ((> right 99)
          (setf left 999 right (1- right)))
         (t                             ; unrealistic situation
                                        ; we didn't find any palindromes
                                        ; which are multiples of two 3-digit
                                        ; numbers
          (return)))))

(defun largest-palindrome-of-3 ()
  (multiple-value-bind (left right)
      (suficiently-large-palindrome-of-3)
    (loop with largest = (* left right)
       for i from right downto left do
         (loop for j from 100 to 999
            for maybe-larger = (* i j) do
              (when (and (> maybe-larger largest)
                         (palindrome-p (number-to-list maybe-larger)))
                (setf largest maybe-larger)))
       finally (return largest))))      ; 906609

它还尝试优化检查数字是否为回文的方式，但会增加内存成本。它还使用稍长的代码将数字拆分为一个列表，但减少了划分（这在计算上有点昂贵）。

整个想法是基于这样一个概念，即最大的回文将在某个地方更接近......最大的乘数，因此，从 99 * 99 开始，您将有很多糟糕的匹配。相反，它尝试从 999 * 999 开始，首先找到一些看起来不错的回文，以“草率”的方式进行。然后它会努力改进最初的发现。

于 2012-12-23T09:47:50.297 回答