Problem 155

方針が間違っているので後で直さないといけないが, とりあえずハッシュの方が相当速いことが分かったのでメモ. a2の方が冗長なアルゴリズムだが, それでもa2の方が速い. n=18くらいまでは簡単にいける.

(use gauche.collection)
(define (a1 n)
  (define (f lis)
    (if (null? lis) '(1)
      (append
       (map (lambda (i) (/ i (+ i 1))) lis)
       (map (lambda (i) (+ i 1)) lis))))
  (define (unique! lis)
    (map car (group-collection lis)))
  (let loop ((i 1) (cur '()) (sum '()))
    (if (> i n) (length (unique! sum))
      (let1 g (f cur)
            (loop (+ i 1) g (append g sum))))))

;(time (a1 13))
; real   2.197
; user   2.199
; sys    0.000

(define (a2 n)
  (let1 ht (make-hash-table 'eqv?)
        (let loop ((i 1))
          (if (> i n)
              (hash-table-num-entries ht)
            (let1 hlist (hash-table-keys ht)
                  (if (null? hlist)
                      (begin
                        (hash-table-put! ht 1 1)
                        (loop (+ i 1)))
                    (let loop-in ((hl hlist))
                      (if (null? hl)
                          (loop (+ i 1))
                        (let1 n (car hl)
                              (begin
                                (hash-table-update! ht (/ n (+ n 1)) (cut + 1 <>) 0)
                                (hash-table-update! ht (+ n 1) (cut + 1 <>) 0)
                                (loop-in (cdr hl))))))))))))

;(time (a2 13))
; real   0.034
; user   0.031
; sys    0.000
;8191