代码之家 › 专栏 › 技术社区 › Jonno_FTW

haskell中循环数的检测问题

haskell

1

Jonno_FTW · 技术社区 · 16 年前

我正在做 problem 61 在Project Euler上,提出了以下代码(以测试他们给出的案例):

p3 n = n*(n+1) `div` 2
p4 n = n*n
p5 n = n*(3*n -1) `div` 2
p6 n = n*(2*n -1)
p7 n = n*(5*n -3) `div` 2
p8 n = n*(3*n -2)

x n = take 2 $ show n
x2 n = reverse $ take 2 $ reverse $ show n
pX p =  dropWhile (< 999) $ takeWhile (< 10000) [p n|n<-[1..]]

isCyclic2 (a,b,c)      = x2 b == x c && x2 c == x a && x2 a == x b
ns2 = [(a,b,c)|a <- pX p3 , b <- pX p4 , c <- pX p5 , isCyclic2 (a,b,c)]

以及所有 ns2 是否返回空列表 cyclic2 以问题中给出的参数为例,然而这个系列并没有在解决方案中出现。问题必须在清单的理解上。 NS2 但我不知道我在哪里做错了什么?

另外,我怎样才能做到 pX 只得到 pX (n) 到上一个中使用的px 二甲苯 ?

附言:如果你认为我完全错过了这个问题,我会得到最终的解决方案:

isCyclic (a,b,c,d,e,f) = x2 a == x b && x2 b == x c && x2 c == x d && x2 d == x e && x2 e == x f && x2 f == x a
ns = [[a,b,c,d,e,f]|a <- pX p3 , b <- pX p4 , c <- pX p5 , d <- pX p6 , e <- pX p7 , f <- pX p8 ,isCyclic (a,b,c,d,e,f)]
answer = sum $ head ns

4 回复 | 直到 11 年前

1

Rüdiger Hanke shraddha hattimare 16 年前

如果我在这里理解你,你就不会再问了 为什么? 您的代码不起作用,但如何使其更快。这实际上是ProjectEuler寻找解决问题的有效方法的全部乐趣,因此请小心行事,首先尝试自己减少搜索空间。我建议你让haskell打印出三个列表:px p3,px p4,px p5,看看你会如何寻找一个循环。

如果你想继续理解你的列表,你可以从每个列表的第一个元素103510241080开始。我很肯定你会在选择1035和1024之后立即停止,而不是测试p5中的任何值的循环,更不用说尝试涉及这两个数字的所有组合排列。

(我还没有真正解决这个问题,所以这就是我要加快速度的方法。可能有一些数学奇才,甚至更快)

首先,看看从px得到的数字。你可以放下更多。例如,p3包含6105个-你不可能在其他集合中找到以“05”开头的数字。所以你也可以去掉那些模100小于10的数。

然后(对于3个集合的情况),我们有时会看到,在画出两个数字后,在最后一个集合中不会有任何数字会给你一个循环,不管你如何排列(例如,1035从p3和3136从p4-这里不能有一个循环)。

我可能会尝试从一个列表中的元素开始,一个接一个地构建一个链,对于每个元素,从其余的列表中找到有效继承者的元素。对于那些您已经找到的,继续尝试从剩余的列表中找到下一个链元素。当你用每个列表中的一个数字构建了一个链时,你只需要检查最后一个数字的最后两位数是否与第一个数字的前两位数匹配。

注意,在查找后续任务时,您不必遍历整个列表。例如,如果您正在寻找p5中3015的继承者,您可以在达到1600或更大的数字时停止。

如果速度太慢,可以将第一个列表以外的列表转换为映射,其中映射键是前两位数字,关联值是以这些数字开头的数字列表。避免您一次又一次地浏览列表。

我希望这能有所帮助。

2

Rüdiger Hanke shraddha hattimare 16 年前

顺序很重要。问题中的循环数是8128、2882、8281,它们不是P3/127、P4/91、P5/44,而是P3/127、P5/44、P4/91。

您的代码只检查顺序812882812882,这不是循环的。

如果你检查的话你会得到结果的

isCyclic2 (a,c,b)

在你的清单理解。

3

2

Regalia 16 年前

编辑:错误问题! 我以为你说的是循环数问题,对不起!

有一种更有效的方法可以这样做: take (2 * l x -1) . cycle $ show x where l = length . show

试试看它能把你带到哪里。

4

0

yairchu 16 年前

顺便说一句,我感觉到你的代码有些重复。

你可以团结你的 [p3, p4, p5, p6, p7, p8] 函数转换为一个函数, 3 从 p3 作为参数等。

要找到模式是什么,可以将所有函数的形式设置为

pX n = ... `div` 2