Problem 53 - 組み合わせ

40問達成！！

There are exactly ten ways of selecting three from five, 12345:
123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
In combinatorics, we use the notation, 5C3 = 10.
In general,nCr = n!/r!(n−r)!,where r ≤ n, n! = n×(n−1)×...×3×2×1, and 0! = 1.
It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.
How many values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?

1から100のなかでnCrが100万を超えるものを答えよ。という問題。

途中で飽きたので、あんまり早くないかも。

(define (problem53 m n)
  (letrec ((combi-counter
             (lambda (n r)
               (letrec ((iter (lambda (count acc i)
                                (if (> i r)
                                      count
                                      (iter (if (>= acc m)
                                                  (+ count 1)
                                                  count)
                                          (/ (* (+ (- n i) 1) acc) i)
                                              (+ i 1))))))
                       (iter 0 1 1))))
           (iter (lambda (n)
                   (if (zero? n)
                       0
                       (+ (combi-counter n n)
                          (iter (- n 1)))))))
           (iter n)))

(problem53 1000000 100) ; 4075

対象性があるので100万を越えた時点で中断して計算すればいいんだけど、微妙に面倒なので、パス。

nC1 = 1
nCr = (n - r + 1) * nC(r-1) / r

の意味がわかったのでまぁいいかな。