問題在Haskell檢測循環次數

我在項目歐拉做problem 61，並想出了下面的代碼（以測試他們給的情況下）：問題在Haskell檢測循環次數

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中使用的pX？

PS：如果你認爲我完全錯過了這個問題，我會得到我的最終解決方案與此：

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

來源

2009-11-15 Jonno_FTW

我想它應該是'takeWhile（<9999）'，以免排除數字9999。 – Stephan202 2009-11-15 13:15:24

'sum'的類型是'Num a => [a] - > a'，即它需要一個列表。然而'頭ns'將產生一個六元組。這不會編譯。那麼這個代碼怎麼能給你正確的結果呢？ – Stephan202 2009-11-15 13:16:23

這是一個錯字，我可以讓'ns'的輸出成爲a..f的列表。我不認爲9999會有影響，但我會改變它。問題出在'ns2'函數中，但我不知道它是什麼。 – 2009-11-15 14:41:31

如果我在這裏理解你，你不再要求爲什麼你的代碼不起作用，但如何使它更快。這實際上是歐拉工程尋找解決問題的有效方法的全部樂趣，因此請謹慎行事，並首先嚐試着自己減少搜索空間。我建議你讓Haskell打印出三個列表pX p3，pX p4，pX p5，並且看看你如何去尋找一個循環。

如果你喜歡你的列表理解，你會從每個列表的第一個元素開始，1035,1024,1080。我敢肯定你會在選擇1035和1024之後停下來，而不是測試循環與來自P5的任何值相比，更不用說嘗試涉及這兩個數字的組合的所有排列。

（我沒有實際工作在這個問題上還沒有，所以這是我怎麼會去加快起來。可能有一些數學魔法，在那裏，甚至更快）

首先，開始看你從pX得到的數字。你可以放棄更多。例如，P3包含6105--你不可能在'05'開始的其他集合中找到一個數字。所以你也可以在模數100小於10的地方放棄這些數字。

然後（對於3套的情況），我們有時可以在繪製兩個數字後看到在最後一組中不會有任何數字會給你一個循環，不管你如何置換（例如1035 P4和P3的3136 - 這裏不會有一個循環）。

我可能會嘗試通過從一個列表中的元素開始逐個構建一個鏈，並且爲每個元素找到剩餘列表中的有效後繼元素。對於你找到的那些，繼續嘗試從剩下的列表中找到下一個鏈元素。當你用每個列表中的一個數字構建一個鏈時，你只需要檢查最後一個數字的最後兩位數字是否與第一個數字的前兩位數字匹配。

請注意，在尋找後繼者時，您不必遍歷整個列表。例如，如果您想從P5中尋找3015的繼任者，您可以在遇到1600或更大的數字時停下來。

如果這還太慢，您可以將除第一個以外的列表轉換爲映射，其中映射鍵是前兩位數字，關聯值是以這些數字開頭的數字列表。讓您不必一次又一次從頭開始查看列表。

我希望這會有所幫助。

來源

2009-11-19 18:35:49

感謝一堆幫助，現在就來實施它。 – 2009-11-20 05:58:53

的順序很重要。問題中的循環數爲8128,2882,8281，這些不是P3/127，P4/91，P5/44，而是P3/127，P5/44，P4/91。

您的代碼只是檢查8128,8281,2882，這是不循環。

如果您在列表理解檢查

isCyclic2 (a,c,b)

你會得到的結果。

來源

2009-11-15 13:14:33

那麼我該如何解決我的功能，使其工作？ – 2009-11-15 13:40:36

我可以使用'任何isCyclic（排列[a，b，c]）'，但這是一個非常低效的方法。 – 2009-11-15 14:24:25

順便說一句，我感覺你的代碼中有一些重複。

可以團結的[p3, p4, p5, p6, p7, p8]功能於一體的功能，將採取3從p3作爲參數等

找到該模式是什麼，你可以讓所有的功能在

形式

pX n = ... `div` 2

來源

2009-11-16 11:33:22 yairchu

雖然這不是問題。我看到的問題是'ns2'的解決方案並不是按給定的順序（a，b，c）。 – 2009-11-16 13:12:44

編輯：錯誤的問題！我以爲你說的是循環數問題，對不起！

有像這樣的東西要做到這一點更有效的方式： take (2 * l x -1) . cycle $ show x where l = length . show

試一下，看看那裏得到你。

來源

2010-04-01 21:02:38 Regalia

問題在Haskell檢測循環次數

回答

相關問題