2

私はプロジェクトオイラーの質問136を行っており、与えられた例をテストするために次のことを思いつきました。

module Main where
import Data.List

unsum x y z n = (y > 0) && (z > 0) && (((x*x)  - (y*y)- (z*z)) == n) && ((x - y) == (y - z))
answer = snub $ takeWhile (<100) [n|x<-[1..],d<-[1..x`div`2],n<-[x..100],y<-[x-d],z<-[y-d], unsum x y z n ]
    where 
      snub [] = []
      snub (x:xs) | elem x xs = snub (filter (/=x) xs)
                  | otherwise = x : snub xs

snubリストから重複する番号を削除します。

この例では、すべての数値が正である場合（または、質問から収集した場合）に25の解を与えることになっており、のような等差n数列です。しかし、コードを使用すると、の11のソリューションのリストが返されます。x^2 - y^2 - z^2 == nx-y == y-zn

リスト内包表記で何を間違えたのでしょうか。また、見逃した最適化はありますか？

4

1 に答える 1

2

ポイント1

この質問を試みたところ、これがn私が思いついた一連の s であることがわかりました

[4,3,16,12,7,20,11,48,28,19,80,44,23,52,112,31,68,76,1156,43,176,559...

takeWhile (<100)これは、いつ停止するかを決定するために使用するフィルタリング関数が間違っていることを意味する可能性があります。関連するメモで、これを実行してみました：

answer = snub $ filter (<=100) $ takeWhile (<200) [...listcomprehension...]

でも時間がかかりすぎて断念。これがポイント2につながります。

ポイント2

最適化に関しては、生の出力に関してリスト内包表記が生成するものを見てください。

Main> take 30 [(x,y,z,n) | x<-[1..], d<-[1..x`div`2], n<-[x..100], y<-[x-d], z<-[y-d]]
[(2,1,0,2),(2,1,0,3),(2,1,0,4),(2,1,0,5),(2,1,0,6),(2,1,0,7),(2,1,0,8),(2,1,0,9),
(2,1,0,10),(2,1,0,11),(2,1,0,12),(2,1,0,13),(2,1,0,14),(2,1,0,15),(2,1,0,16),(2,1,0,17),
(2,1,0,18),(2,1,0,19),(2,1,0,20),(2,1,0,21),(2,1,0,22),(2,1,0,23),(2,1,0,24),(2,1,0,25),
(2,1,0,26),(2,1,0,27),(2,1,0,28),(2,1,0,29),(2,1,0,30),(2,1,0,31)]

これは xyz と n の各組み合わせで unsum が呼び出されることを意味し2^2 - 1^2 - 0^2 = 3ます。

また、計算をリスト内包表記 (上記の理由で遅い) から関数に移動し、有効な組み合わせをnリスト内包するだけの方が、はるかに単純で冗長性がはるかに低くなります。(x,y,z)

ns = map nsum [(x, x-d, x-d-d) | x <- [1..], d <- [1..x`div`2]]
nsum (x,y,z) = x^2 - y^2 - z^2

そうすれば、この無限リストから答えを計算することができますが、takewhile の使用には注意してください。

于 2009-11-30T08:59:00.740 に答える