0

私は一般的なlispを学び始めたばかりなので、プロジェクトオイラーの問題に取り組んできました。これが私の解決策です（https://github.com/qlkzy/project-euler-clの助けを借りて）。文体の変更とそれをよりLisp-yにするためのソートについて何か提案はありますか？

; 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 に答える