ハスケルのProject Euler＃12に対する私の解決策の問題を見つけるのを助けてください。

Question

私はHaskellのプログラミング初心者で一般的なプログラミングですが、問題解決が好きなのでProject Eulerの問題を解決しようとしています。しかし、私はproblem #12に問題があります。

私はうまくいくと思っていた解決方法を考案しましたが、悲しいかな、それはありません。

私のコードで問題に私の目を開けて、 と私を助けることができますそれを修正するための正しい方向にプッシュ？ありがとうございました。ここで

はコードです：

triangleNumber = scanl1 (+) [1..] 

factors n = [x | x <- [1..n], n `mod` x == 0] 

numFactors = length . factors 

eulerTwelve = find ((>500) . numFactors) triangleNumber 

はどうもありがとうございました！ :)

Answer 1

私はそれをコピーし、私が投げたものは見つからないというエラーでした。これは、findが入っているモジュールListをインポートする必要があるからです。

import Data.List 

ちなみに、ファクタ機能を最適化する必要があります。

Answer 2

あなたが言いたい問題は、eulerTwelveが終了するには時間がかかりすぎるということです。あなたのコードは正しいです、それはちょうど非効率です。ボトルネックはfactors関数です。これは1からnの間のすべての数値を、除算値がnかどうかを調べることです。ここでefficient prime factorizationとa nifty implementation of the power setを使用して、数の約数を見つけるためのより高速な方法があります：

import Data.Numbers.Primes (primeFactors) 

powerSet = filterM (const [True, False]) 

factors = map product . nub . powerSet . primeFactors 

これでもかなり非効率的です。あなたの代わりにそのようなprimeFactorsから直接numFactorsを計算することができます。

numFactors = product . map ((+1) . length) . group . primeFactors 

私はこの1つを使用してnumFactorsを交換するとき、私は即座に結果を得ます。

Answer 3

IIRCの場合、1からnまでのすべての整数をテストする必要はありません.1からn^0.5までの数（nの平方根）のみが必要です。利用可能です。

Answer 4

Project Eulerの質問は、明快な検索をプログラミングして実行するだけで解決するのは悪い考えです。 （以前の質問のいくつかはそのように解決することができますが、それを悪用するのではなく、それらを練習として使用することをお勧めします）。代わりに、コンピュータの検索を行うために質問の数学的な内容について考える必要があります扱いやすい。

私が離れすぎを与えたいと思うが、ここではいくつかのヒントですありません。三角数番目のnための式があります

• 。それを見つけるので、合計で計算する必要はありません。

• nの三角形の数式では、どのような数がその除数になる可能性がありますか？

• これらの約数について知っているとすれば、そこに何人がいるのか把握する簡単な方法は何ですか？（それらを列挙することなしに）