正整数のゲーデル数化？ in Common Lisp DouKaku?

正整数のゲーデル数化？

正の整数 n を引数としてとり， 2^d1 * 3^d2 * 5^d3 ... * pk^dk を返す関数
goedel を定義してください．

ただし，n を10進表現で k 桁の数としたときの各桁の数が数列 [d1,d2,d3,...,dk]
をなすとし，dk が 1 の位，d1 が 10^(k-1) の位です．また，pk は k番目の素数です．

goedel   9  ⇒ 2^9             ⇒  512
goedel  81  ⇒ 2^8 * 3^1       ⇒  768
goedel 230  ⇒ 2^2 * 3^3 * 5^0 ⇒  108

see: ゲーデル数

post comment

Posted feedbacks - Common Lisp

普通に書くとイマイチ面白くないかと思ってひねり出したコード。牛刀割鶏な感はありますが、ジェネレータを使って繰り返しを行うマクロを定義して、これに素数ジェネレータを渡しています。これくらいだと Lisp マクロの入門用としていい題材だったかもしれません。

(defun make-prime-generator ()
  (let ((primes ()))
    (lambda ()
      (if (null primes)
          (setf primes (list 2))
        (do ((x (1+ (car primes)) (1+ x)))
            ((notany (lambda (p) (= (rem x p) 0)) primes)
             (push x primes))))
      (car primes))))

(defmacro loop-with-generator ((var generator)
                               (end-test &rest result) &body body)
  (let ((gvar (gensym)))
    `(do ((,gvar ,generator))
         (,end-test ,@result)
       (let ((,var (funcall ,gvar))) ,@body))))

(defun goedel (n)
  (let ((digits (do ((m n (floor m 10)) (ds ()))
                    ((= m 0) ds)
                  (push (rem m 10) ds)))
        (code 1))
    (loop-with-generator (p (make-prime-generator))
                         ((null digits) code)
      (setf code (* (expt p (pop digits)) code)))))

DouKaku?

正整数のゲーデル数化？

Posted feedbacks - Common Lisp

Index

Feed

Other

Link

Pathtraq