『関数プログラミング入門』(IFPH)手習い中
ユニコードで遊んだ結果を書き続けようかと思っていた。
しかし、文字化けがとても発生しやすいので、本に戻ろう。
第4章リストの中に、あの有名なピタゴラス数を求めるというのがある。
> x*x+y*y==z*z を満たす整数の３つ組(x,y,z)を求めよとりあえず、本の通りにやってみた。
triads :: Int -> [(Int,Int,Int)]
triads n = [(x,y,z) | (x,y,z) <- triples n, pyth(x,y,z)]
triples :: Int -> [(Int,Int,Int)]
triples n = [(x,y,z) | x <- [1..n], y <- [1..n], z <- [1..n]]
pyth :: (Int,Int,Int) -> Bool
pyth (x,y,z) = (x*x + y*y == z*z)どう見ても効率が悪そうだ。triples n で、 (x,y,z) の組み合わせを全部求めている。
それから、 (x,y,z) がピタゴラス数かどうかの判定をするのだ。
さて、何も考えずに動かしてみた。
*Main Data.List> triads 10
[(3,4,5),(4,3,5),(6,8,10),(8,6,10)]互いに素な場合だけにし、順序が違うだけのも捨てないと話にならない。
ということで、ちょっとだけ勝手に改造。
triads :: Int -> [(Int,Int,Int)]
triads n = [(x,y,z) | (x,y,z) <- triples n, pyth(x,y,z)]
triples :: Int -> [(Int,Int,Int)]
triples n = [(x,y,z) | x <- [1..n], y <- [x+1..n], z <- [y+1..n]]
pyth :: (Int,Int,Int) -> Bool
pyth (x,y,z) = (x*x + y*y == z*z) && (gcd x y == 1)
*Main Data.List> triads 20
[(3,4,5),(5,12,13),(8,15,17)]さて、100まで、1000まで、10000までのピタゴラス数の個数を調べてみよう。
*Main Data.List> length (triads 100)
16
*Main Data.List> length (triads 1000)
C-c C-cInterrupted.
*Main Data.List> たった1000だというのに、全然帰って来なくなったので殺した。
これではダメだ。
もっと高速なやり方を次までに考えてみよう。
＃人気の記事
＃タグ
