ProjectEulerのヒントが必要です

Question

1から20までのすべての数値で均等に割り切れる最小の正の数値は何ですか？

---

私は簡単にループを使って命令型プログラミング言語で解決策を強制することができます。しかし、私はハスケルでこれをやりたいと思っています。私はそれがそのようにする方法のヒントを必要とする

[n | n <- [1..], d <- [1..20], n `mod` d == 0] !! 0 

しかし、私は「d」は、D = 1で条件が等しい真になりますので、それが動作しません知っている：私はこのような何かをやって考えていましたn mod dが[1..20]について計算され、20個すべての数値について検証できます。

もう一度解決策を教えてください。ありがとう。

Answer 1

これを見ると、リストフィルタリング操作のようです。 1から20までのすべての数値で割り切れるかどうかに基づいてフィルタリングされる無限の数のリスト

したがって、整数と整数のリストを取る関数が必要ですHaskellは怠惰な言語であるよう

isDivisible :: [Int] -> Int -> Bool 

、その後は今

filter (isDivisible [1..20]) [1..] 

としてリストフィルタでこれを使用して、リスト内のすべてのそれらの数字で割り切れるされて、あなただけのアイテムの必要数を（取る必要がありますあなたの場合は、List.headメソッドだけが必要なので、g ood）をフィルタ結果から除外します。

私はこれがあなたを助けてくれることを願っています。これはシンプルなソリューションであり、このための他の多くの単一ラインソリューションもあります:)

Answer 2

Project Eulerの多くの問題と同様、これはプログラミングに関する数学と同じくらいです。

関数型言語ではおそらく戦術はそれを再帰的なベースにしようとしている1

から始まる順序であることが起こるあなたが探していることは一連の数値の最小公倍数である

、 [1..n]で割り切れる最小の数と、[1..n+1]で割り切れる最小の数との間の関係を計算します。 20より小さな数字でこれを試し、数学的な関係を理解し​​たり、パターンを判別したりしてみてください。

Answer 3

これを効率的に解決するには、Don Robyの答えに進んでください。あなたがブルートフォースのアプローチにちょっとしたヒントを求めたいのであれば、あなたが書き留めたものを英語に翻訳し、それが問題の説明とどのように違うのかを見てください。

何をしたい

を「1から20までの正ナチュラルと正ナチュラルズの製品をフィルタリングする」「1からの正ナチュラルズのいくつかの機能によって正ナチュラルをフィルタリングし、より似ているようにあなたが何かを書きました20" の代わりに、検索の

Answer 4

あなたは、このような番号を見つけるまで、あなたがsmallest (or least) positive number that is evenly divisible by (aka "is a common multiple of")すべてのこれらの数字を構築し、代わりに数字のセットを与えられ、建設的アルゴリズムを考えます。そこのアルゴリズムを見て、どのようにEuclid's algorithm（それらが言及する）が適用されるかもしれないか考えてみてください。

最大公約数と最小公倍数の2つの数字の間の関係は考えられますか？どのように数字のセットの間で？

Answer 5

この場合、Mathyを取得する必要があります。 foldlから[1..20]までは、アキュムレータn = 1から始まります。そのリストの各番号pについては、pが素数の場合にのみ処理を進めます。今度は前の素数pの場合、qのような最大の整数がp^q <= 20となります。掛け算n *= (p^q)。 foldlが終了すると、nが必要な番号になります。

Answer 6

代替回答：Preludeで提供されているlcm機能を利用できます。

Answer 7

可能ブルートフォース実装は

head [n|n <- [1..], all ((==0).(n `mod`)) [1..20]] 

だろうが、この場合には、それはあまりにも時間がかかります。 all関数は、述部がリストのすべての要素に対して保持されているかどうかをテストします。ラムダは(\d -> mod n d == 0)の略です。

どのように計算をスピードアップできますか？我々が持っているこの番号の使用

2 = 2 
3 =  3 
4 = 2^2 
5 =   5 
6 = 2 * 3 
7 =   7 
8 = 2^3 
9 =  3^2 
10 = 2  * 5 
11 =    11 
12 = 2^2*3 
13 =    13 
14 = 2  *7 
15 =  3 * 5 
16 = 2^4 
17 =     17 
18 = 2 * 3^2 
19 =      19 
20 = 2^2 * 5 
-------------------------------- 
max= 2^4*3^2*5*7*11*13*17*19  

：：さんは素因数で私たちの約数を因数分解し、すべての素因数の最高の電力を検索してみましょう

all ((==0).(2^4*3^2*5*7*11*13*17*19 `mod`)) [1..20] 
--True 

ねえが、それはからのすべての数字で割り切れます1から20です。あまり驚くべきことではありません。例えば。因子3と5を「含む」ため15で割り切れ、因子2^4を「含む」ため16で割り切れる。しかし、できるだけ小さい数字ですか？それについて考えてみてください...