haskell - ProjectEuler 问题需要提示

Question

能被 1 到 20 的所有数整除的最小正数是多少？

---

我可以很容易地用带有循环的命令式编程语言暴力破解解决方案。但我想在 Haskell 中做到这一点，并且没有循环会使它变得更加困难。我正在考虑做这样的事情：

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

但我知道这行不通，因为“d”将使条件在 d = 1 处等于 True。我需要提示如何制作它，以便mod为 [1..20] 计算 n d 并且可以验证所有 20 个数字。

再次，请不要给我解决方案。谢谢。

Answer 1

与许多欧拉计划问题一样，这至少与数学和编程一样多。

您正在寻找的是一组数字的最小公倍数，它们恰好在从 1 开始的序列中。

函数式语言中一种可能的策略是尝试使其递归，基于找出可被所有 整除的[1..n]最小数和可被所有 整除的最小数之间的关系[1..n+1]。玩一些小于 20 的数字，尝试理解数学关系或辨别模式。

Answer 2

在找到这样一个数字之前，不要进行搜索，而是考虑一种建设性算法，其中，给定一组数字，您构造可以被整除的最小（或最小）正数（又名“是”的公倍数）所有这些数字。查看那里的算法，并考虑欧几里得算法（他们提到的）如何应用。

您能根据最大公约数和最小公倍数来考虑两个数字之间的任何关系吗？在一组数字中怎么样？

Answer 3

仔细看，好像是列表过滤操作。无限数列表，根据数字是否可被 1 到 20 的所有数字整除的情况进行过滤。

所以我们得到的是我们需要一个函数，它接受一个整数和一个整数列表，并判断它是否可以被列表中的所有数字整除

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

然后在列表过滤器中使用它作为

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

现在，由于 Haskell 是一种惰性语言，您只需要从上述过滤器结果中获取所需数量的项目（在您的情况下，您只需要一个因此 List.head 方法听起来不错）。

我希望这可以帮助你。这是一个简单的解决方案，并且还会有许多其他单行解决方案：)

Answer 4

替代答案：您可以利用Prelude 中提供的lcm功能。

Answer 5

为了有效地解决这个问题，请使用 Don Roby 的答案。如果您只是想对蛮力方法有一点提示，请将您写的内容翻译回英文，看看它与问题描述有何不同。

您写了类似“过滤正自然值和正自然值的乘积，从 1 到 20”

你想要的更像是“通过从 1 到 20 的正自然值的某些函数过滤正自然值”

Answer 6

在这种情况下，你必须得到 Mathy。你会做一个foldl通过[1..20]，从一个累加器开始n = 1。对于该列表的每个数字，只有当它是素数p时才继续。p现在对于前一个素数p，你想找到最大的整数q，使得p^q <= 20。相乘n *= (p^q)。一旦foldl完成，n就是你想要的数字。

Answer 7

一个可能的蛮力实施将是

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

但在这种情况下，它会花费太长时间。该all函数测试谓词是否适用于列表的所有元素。lambda 是 的缩写(\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 的所有数字整除。这并不奇怪。例如，它可以被 15 整除，因为它“包含”因子 3 和 5，并且它可以被 16 整除，因为它“包含”因子 2^4。但它是可能的最小数字吗？想一想...