[Project Euler] Problem 15 「格子経路」

2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.
では, 20×20 のマス目ではいくつのルートがあるか.

よくある数え上げの問題で, 経路の数は₄₀C₂₀となります. 組合せの数を求める手続きがあると答えは求まります.

1. 分母と分子に現れる数のリストを作る.
2. それぞれの数を素因数分解する.
3. 分母に現れる数から分子に現れる数を取り除く.
4. 分母に残った数の積を求める.

組合せの数を求める手続きの定義は次のようになります.

(require srfi/1)

(define (square n) (* n n))

(define (divides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime-factorization n)
  (let ((a (smallest-divisor n)))
    (if (= a n)
        (list n)
        (cons a (prime-factorization (/ n a))))))

(define (comb i j)
  (define (pf items)
    (sort (apply append (map prime-factorization items))
          <))
  (define (remove-one lst obj)
    (cond ((null? lst) ())
          ((equal? (car lst) obj) (cdr lst))
          (else (cons (car lst) (remove-one (cdr lst) obj)))))
  (define (diff a b)
    (cond ((null? b) a)
          ((member (car b) a) (diff (remove-one a (car b)) (cdr b)))
          (else (error "diff"))))
  (apply * (diff (pf (iota j i -1))
                 (pf (iota (- j 1) 2)))))

計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (comb 40 20)
137846528820
>