Hatena::ブログ(Diary)

みずぴー日記 Twitter

2010-01-18(月)

既約分数クイズ

| 既約分数クイズを含むブックマーク

30分プログラム、その722。既約分数クイズにチャレンジしました。

今回は力技で解きましたが、クイズと言うからにはきっとクールな解法があるんでしょう。

使い方

*Main> irreducibleFracs 4
[(0,1),(1,1),(1,2),(1,3),(2,3),(1,4),(3,4)]

ソースコード

type Frac a = (a,a)
canReduce :: Integral a => Frac a -> Bool
fracs :: Integral a => a -> [Frac a]
irreducibleFracs :: Integral a => a -> [Frac a]

canReduce (a,b)= gcd a b /= 1
fracs n = [(p,q) |  q <- [1..n], p <- [0..q]]
irreducibleFracs n = [f | f <- fracs n, not $ canReduce f]

参考

nobsunnobsun 2010/01/19 07:15 つhttp://www.sampou.org/cgi-bin/haskell.cgi?Programming%3a%b6%cc%bc%ea%c8%a2%3a%c0%b0%bf%f4%cf%c0#H-6202f3

nobsunnobsun 2010/01/19 07:19 つ http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3a%e6%95%b0%e9%81%8a%e3%81%b3%3a%e6%97%a2%e7%b4%84%e5%88%86%e6%95%b0

ツムジツムジ 2010/01/24 13:45 力技でよければ……

lowestTerm :: Int -> [(Int, Int)]
lowestTerm n = [(p, q) | q <- [1 .. n], p <- [0 .. q], gcd p q == 1]