Scheme:数遊び:既約分数

Scheme:数遊び:既約分数

既約分数

結城浩さんの既約分数パズル。

問題:正の整数Nが与えられているとき、以下の条件を満たす既約分数p/qを「すべて」求めるアルゴリズムを示してください。条件は:

Haskellによるエレガントな解法(本質的に、エラトステネスの篩と同質の方法だと 思う)はnobsunが示している。

gcdを使うのは素直すぎるので、ここではFarey seriesというのを 使った解法を。これも割算が登場しない。

(define (farey n)
  (define (rec series n)
    (cond ((null? (cdr series)) series)
          ((= (+ (cdar series) (cdadr series)) n)
           (list* (car series)
                  (cons (+ (caar series) (caadr series))
                        (+ (cdar series) (cdadr series)))
                  (rec (cdr series) n)))
          (else (cons (car series) (rec (cdr series) n)))))
  (if (= n 1)
    '((0 . 1) (1 . 1))
    (rec (farey (- n 1)) n)))
gosh> (farey 6)
((0 . 1) (1 . 6) (1 . 5) (1 . 4) (1 . 3) (2 . 5) (1 . 2) (3 . 5) (2 . 3) (3 . 4) (4 . 5) (5 . 6) (1 . 1))

参考文献: John Conway and Richard Guy, The Book of Numbers, Springer-Verlag, 1996. 数の不思議な性質が易しく語られてて面白い本です。

(define (f n)
  (let loop ((x 1) (y 1) (r '((0 1))))
    (cond ((> x n) r)
          ((= y 0) (loop (+ x 1) x r))
          ((member (if (> (* y 2) x) (list (- x y) y) (list y (- x y))) r)
           (loop x (- y 1) (cons (list y x) r)))
          (else (loop x (- y 1) r)))))

Tag: Puzzle


Last modified : 2013/04/26 03:58:37 UTC