4

1 から 20 までのすべての数で割り切れる最小の正の数は?

ループを使用した命令型プログラミング言語で、ソリューションを簡単にブルート フォースすることができました。しかし、私は Haskell でこれを行いたいのですが、ループがないと非常に難しくなります。私はこのようなことを考えていました：

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

しかし、「d」は d = 1 で条件を True にするため、それが機能しないことはわかっています。n modd が [1..20] に対して計算され、検証できるようにする方法についてのヒントが必要です。数字は全部で20。

繰り返しますが、私に解決策を教えないでください。ありがとう。

4

7 に答える 7

8

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

あなたが探しているのは、たまたま 1 から始まる一連の数値の最小公倍数です。

[1..n]関数型言語で考えられる戦術は、 のすべてで割り切れる最小の数と のすべてで割り切れる最小の数との間の関係を理解することに基づいて、再帰的にしようとすることです[1..n+1]。20 より小さい数でこれを試して、数学的関係を理解し​​たり、パターンを識別したりしてみてください。

于 2011-07-08T03:41:27.913 に答える
5

そのような数が見つかるまで検索する代わりに、代わりに建設的なアルゴリズムを検討してください。このアルゴリズムでは、一連の数が与えられたときに、で割り切れる最小の (または最小の) 正の数 (別名「の公倍数」) を作成します。それらすべての数字。そこにあるアルゴリズムを見て、ユークリッドのアルゴリズム(彼らが言及している) がどのように適用されるかを検討してください。

2 つの数値の最大公約数と最小公倍数の関係を考えてみてください。数の中でどうですか？

于 2011-07-08T04:18:42.113 に答える
4

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

つまり、整数と整数のリストを受け取り、リスト内のすべての数値で割り切れるかどうかを判断する関数が必要です。

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

次に、これをリストフィルターで次のように使用します

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

Haskellは怠惰な言語なので、上記のフィルター結果から必要な数のアイテムを取得する必要があります（この場合、必要なアイテムは1つだけなので、List.headメソッドが適切です）。

これがお役に立てば幸いです。これは単純な解決策であり、これには他にも多くの単一行の解決策があります:)

于 2011-07-08T04:41:42.760 に答える
1

別の答え: Prelude で提供されているlcm関数を利用できます。

于 2011-07-08T04:57:34.317 に答える
0

これを効率的に解決するには、DonRobyの答えを参考にしてください。総当たり攻撃のアプローチについて少しヒントが必要な場合は、書き戻した内容を英語に翻訳して、問題の説明との違いを確認してください。

あなたは「ポジティブナチュラルとポジティブナチュラルの積を1から20までフィルタリングする」のようなものを書きました

必要なのは、「正のナチュラルを1から20までの関数でフィルタリングする」のようなものです。

于 2011-07-08T04:10:58.830 に答える
0

この場合、Mathy を取得する必要があります。accumulator から始めてfoldlthrough を実行します。そのリストの各数値について、 が素数の場合にのみ続行します。前の素数 について、 のような最大の整数を見つけたいとします。乗算します。終わったら、あなたが望む数です。[1..20]n = 1pppqp^q <= 20n *= (p^q)foldln

于 2011-07-08T04:51:31.317 に答える
0

可能性のあるブルート フォースの実装は次のようになります。

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 で割り切れます。しかし、それは可能な限り最小の数ですか？考えてみてください...

于 2011-07-08T10:06:18.077 に答える