TIM Labs

ピタゴラス数を求める(本のやり方)

| コメント(0) | トラックバック(0)

Haskells.jpgのサムネール画像

『関数プログラミング入門』(IFPH)手習い中

ユニコードで遊んだ結果を書き続けようかと思っていた。 しかし、文字化けがとても発生しやすいので、本に戻ろう。

第4章リストの中に、あの有名なピタゴラス数を求めるというのがある。

xx+yy==z*z を満たす整数の3つ組(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) &amp;&amp; (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だというのに、全然帰って来なくなったので殺した。

これではダメだ。 もっと高速なやり方を次までに考えてみよう。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/327

コメントする

このブログ記事について

このページは、fujiが2012年11月14日 10:00に書いたブログ記事です。

ひとつ前のブログ記事は「ユニコード全20902字」です。

次のブログ記事は「Vim で素数を最小の手数で列挙する」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。