正整数のゲーデル数化？ in Scheme 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: ゲーデル数

なんとなくstreamを使ってみた。 sieveとprimesはSICPのやつ。

(use util.stream)
(use gauche.collection)

(define (integers-starting-from n)
  (stream-cons n (integers-starting-from (+ n 1))))

(define (sieve stream)
  (define (divisible? x y) (= (remainder x y) 0))
  (stream-cons
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x) (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

(define (number->digit-stream n)
  (stream-map
   (lambda (c) (- (char->integer c) (char->integer #\0)))
   (string->stream (number->string n))))

(define (goedel n)
  (apply * (stream->list
            (stream-map (lambda (pk nk) (expt pk nk))
                        primes (number->digit-stream n)))))

ストリームの練習も兼ねて。

(use srfi-1)
(use util.stream)

(define (goedel n)
  (let* ((ds (map digit->integer (string->list (number->string n))))
         (ps (stream->list (stream-take prime-stream (length ds)))))
    (fold * 1 (map expt ps ds))))

(define prime-stream
  (letrec ((sieve
            (lambda (strm)
              (let ((n (stream-car strm)))
                (stream-cons n
                             (sieve
                              (stream-remove (lambda (m)
                                               (zero? (remainder m n)))
                                             (stream-cdr strm))))))))
    (sieve (stream-iota -1 2))))

(define (main args)
  (print (goedel (string->number (cadr args))))
  0)

DouKaku?

正整数のゲーデル数化？

Posted feedbacks - Scheme

Index

Feed

Other

Link

Pathtraq