「ランダムにビット列を作っていったら、[0,0,1] が最初に登場するのは、いつ頃でしょう？」

• 初Bitsの出 - d.y.d.

ランダムにビット列を作っていったら、[0,0,1] が最初に登場するのは、いつ頃でしょう？

自分でも試してみました。リストでも良いですよね。

(use math.mt-random)
(use srfi-1)

(define rand
  (let1 m (make <mersenne-twister>)
    (^ ()
       (mt-random-integer m 2))))

(define (first-occurrence pat)
  (let rec ((ls '()))
    (let ((plen (length pat))
          (llen (length ls)))
      (if (and (<= plen llen)
               (equal? (split-at ls plen) pat))
          llen
          (rec (cons (rand) ls))))))


(define (times i expr)
  (let rec ((i i)(acc '()))
    (if (or (negative? i)(zero? i))
        acc
        (let1 r (expr i)
          (rec (- i 1)(cons r acc))))))

(define (average ls)
  (round->exact (/ (apply + ls)(length ls))))

;; ;(time (average (times 10000 (^ _ (first-occurrence '(0 0 1))))))
;; ; real   0.313
;; ; user   0.313
;; ; sys    0.000
;; 8

;; ;(time (average (times 10000 (^ _ (first-occurrence '(0 0 0))))))
;; ; real   0.563
;; ; user   0.562
;; ; sys    0.000
;; 14

ほんまや。

• 初Bitsの出：解答編 - d.y.d