« Project Euler : Problem 12 ~ 三角数の約数の数 (2) | トップページ | Project Euler : Problem 13 »

2010年2月 1日 (月)

既約分数クイズ、ファレイ数列、フォードの円

 こちらのブログ「既約分数クイズ」の存在を知りました。

 ちょっと面白そうだったので、Haskell でコードを書いてみました。答えは (分子, 分母) の組がリストの形で出てきます。

irreducibleFraction :: Int -> [(Int, Int)] irreducibleFraction n = [(p, q) | q <- [1 .. n], p <- [0 .. q], gcd p q == 1]
*Main> irreducibleFraction 4 [(0,1),(1,1),(1,2),(1,3),(2,3),(1,4),(3,4)]
 Haskell では条件を書くだけで、何の工夫もせずに答えが出てしまいました。

 「他の解法はないものか?」と調べていたら、既約分数に関連して「ファレイ数列」というものがあることが分かりました。これは既約分数が大きさの順に並んでいるものです。
 そこで、先ほどの関数を使って「ファレイ数列」を作ってみることにしました。ついでにより分数らしく見えるようにしてみました。

import Ratio import Data.List irreducibleFraction :: Int -> [(Int, Int)] irreducibleFraction n = [(p, q) | q <- [1 .. n], p <- [0 .. q], gcd p q == 1] farey :: Int -> [(Int, Int)] farey n = sortBy comp (irreducibleFraction n) where comp (p1, q1) (p2, q2) = compare (p1 % q1) (p2 % q2) fareyToStr :: [(Int, Int)] -> String fareyToStr ns = init $ concat $ map toStr ns where toStr (a, b) = show a ++ "/" ++ show b ++ " "
*Main> fareyToStr $ farey 4 "0/1 1/4 1/3 1/2 2/3 3/4 1/1"
 さらに調べると、「ファレイ数列」には「中関数」を使って求める方法があるようなので、自分でも考えて見ました。
farey2 :: Int -> [(Int, Int)] farey2 n = farey' [(0, 1), (1, 1)] where farey' ((x1, y1) : xs@((x2, y2) : _)) | y1 + y2 > n = (x1, y1) : farey' xs | otherwise = farey' ((x1, y1) : (x1 + x2, y1 + y2) : xs) farey' xs = xs
*Main> fareyToStr $ farey2 4 "0/1 1/4 1/3 1/2 2/3 3/4 1/1"

 

 ところで Wikipedia の「ファレイ数列」の項には「フォードの円」という図が載っています。
 「これって、自作の "Turtle Graphics on Ruby/SDL" で描けるかな?」ということでコードを書いてみました。

# -*- coding: utf-8 -*- require 'turtle_graphics' # # == ファレイ数列 # def farey(n) q_arr = (1 .. n).to_a p_arr = Array.new f_arr = Array.new farey = q_arr.each do |q| p_arr = (0 .. q).to_a f_arr.push(p_arr.map {|p| [p, q]}) end f_arr = f_arr.flatten(1).select{|p, q| p.gcd(q) == 1} return f_arr.sort_by{|p, q| p / q.to_f} return end # # == フォードの円を描く # class Screen def ford_circle(p, q, c) q = q.to_f r = 1 / (2 * q * q) draw_circle(p / q, r, r, c).update # draw_circle(p / q, 1 - r, r, c).update end end sc = Screen.create(600, 600) sc.set_range(0, 1, 0, 1) # 描画範囲 (x_min, x_max, y_min, y_max) farey(10).each do |p, q| sc.ford_circle(p, q, White) end sc.main_loop

Screenshotturtle_graphics_on_rubysd

 Wikipedia には F5 の図が載っていますが、今回のコードでは F10 の図を描いてみました。
 当然、コードを書き換えれば F50 だろうが F100 だろうが表示してくれます(相当時間がかかると思われますが……)
 また、描画範囲を書き換えて拡大表示させれば、小さい円もそれぞれしっかり他の円に接しているのがわかります。
 ただし、あまり大きく拡大表示すると、0/1 の円と 1/1 の円の表示が乱れるようです。これは "turtle_graphics.rb" の "Screen#draw_circle" 内で使用している、"draw_aa_circle" というメソッドの問題のようです。この部分を "draw_circle" に書き換えれば、どんなに拡大しても表示は乱れないと思われます。

« Project Euler : Problem 12 ~ 三角数の約数の数 (2) | トップページ | Project Euler : Problem 13 »

Haskell」カテゴリの記事

Ruby」カテゴリの記事

Turtle Graphics on Ruby/SDL」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/47449861

この記事へのトラックバック一覧です: 既約分数クイズ、ファレイ数列、フォードの円:

« Project Euler : Problem 12 ~ 三角数の約数の数 (2) | トップページ | Project Euler : Problem 13 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ