ファレイ数列
30分プログラム、その720。mixiの課題コミュニティからのインスパイアです。
趣旨としては、wikipedia:ファレイ数列を生成せよ、という問題です。Wikipediaのページの中盤に書いてある中間数を利用します。
使い方
gosh> (map frac->string (farey 1)) ("0/1" "1/1") gosh> (map frac->string (farey 2)) ("0/1" "1/2" "1/1") gosh> (map frac->string (farey 3)) ("0/1" "1/3" "1/2" "2/3" "1/1") gosh> (map frac->string (farey 4)) ("0/1" "1/4" "1/3" "1/2" "2/3" "3/4" "1/1")
ソースコード
#! /opt/local/bin/gosh ;; -*- mode:scheme; coding:utf-8 -*- ;; ;; farey.scm - ;; ;; Copyright(C) 2010 by mzp ;; Author: MIZUNO Hiroki / mzpppp at gmail dot com ;; http://howdyworld.org ;; ;; Timestamp: 2010/01/13 20:59:06 ;; ;; This program is free software; you can redistribute it and/or ;; modify it under MIT Lincence. ;; (use srfi-1) (define (gcd a b) (if (= b 0) a (gcd b (modulo a b)))) (define (make-frac a b) (let1 d (gcd a b) (cons (/ a d) (/ b d)))) (define (num x) (car x)) (define (denom x) (cdr x)) (define (frac->string n) (string-append (number->string (car n)) "/" (number->string (cdr n)))) (define (add-frac x y) (make-frac (+ (num x) (num y)) (+ (denom x) (denom y)))) (define (farey n) (if (= n 1) (list (make-frac 0 1) (make-frac 1 1)) (let1 xs (farey (- n 1)) (filter (lambda (x) (<= (denom x) n)) (append (append-map (lambda (x y) (list x (add-frac x y))) xs (cdr xs)) (list (make-frac 1 1)))))))