欧拉项目问题14（Collatz问题）
以下迭代序列是为正整数集定义的：
n – > n / 2（n是偶数）n – > 3n + 1（n是奇数）
使用上面的规则并从13开始，我们生成以下序列：
13 40 20 10 5 16 8 4 2 1可以看出，这个序列（13开始，1结束）包含10个项。 虽然还没有被certificate（Collatz问题），但是所有的起始数字都被认为是1。
哪个起始数字低于一百万，会产生最长的连锁？
注意：一旦链条开始，条款被允许超过一百万。
我尝试使用bruteforce方法在C编码解决scheme。 但是，似乎我的程序在尝试计算113383时停顿。请指教:)
#include <stdio.h> #define LIMIT 1000000 int iteration(int value) { if(value%2==0) return (value/2); else return (3*value+1); } int count_iterations(int value) { int count=1; //printf("%d\n", value); while(value!=1) { value=iteration(value); //printf("%d\n", value); count++; } return count; } int main() { int iteration_count=0, max=0; int i,count; for (i=1; i<LIMIT; i++) { printf("Current iteration : %d\n", i); iteration_count=count_iterations(i); if (iteration_count>max) { max=iteration_count; count=i; } } //iteration_count=count_iterations(113383); printf("Count = %d\ni = %d\n",max,count); } 你拖延的原因是因为你通过了一个大于2^31-1 （又名INT_MAX ）。 尝试使用unsigned long long而不是int 。
我最近在这里发表了博客 注意在C中，朴素的迭代方法已经足够快了。 对于dynamic语言，您可能需要通过logging进行优化，以遵守一分钟规则 （但这不是这种情况）。
哎呀，我又做了一次 （这一次使用C ++进一步审查可能的优化）。
注意你的蛮力解决scheme经常会一遍又一遍地计算相同的子问题。 例如，如果你从10开始，你会得到5 16 8 4 2 1 ; 但如果你从20开始，你会得到20 10 5 16 8 4 2 1 。 如果在计算后将值caching到10 ，则不必再重新计算。
（这就是所谓的dynamic编程 。）
我前段时间解决了这个问题，幸好还有我的代码。 不要阅读代码，如果你不想扰stream ：
#include <stdio.h> int lookup[1000000] = { 0 }; unsigned int NextNumber(unsigned int value) { if ((value % 2) == 0) value >>= 1; else value = (value * 3) + 1; return value; } int main() { int i = 0; int chainlength = 0; int longest = 0; int longestchain = 0; unsigned int value = 0; for (i = 1; i < 1000000; ++i) { chainlength = 0; value = i; while (value != 1) { ++chainlength; value = NextNumber(value); if (value >= 1000000) continue; if (lookup[value] != 0) { chainlength += lookup[value]; break; } } lookup[i] = chainlength; if (longestchain < chainlength) { longest = i; longestchain = chainlength; } } printf("\n%d: %d\n", longest, longestchain); } time ./a.out [don't be lazy, run it yourself]: [same here] real 0m0.106s user 0m0.094s sys 0m0.012s
刚刚在C＃中进行了testing，似乎113383是32位inttypes变得太小而无法存储链中每一步的第一个值。
处理这些大数字时，尝试使用unsigned long ;）
如前所述，最简单的方法是获得一些记忆，以避免重新计算未被计算的事物。 如果你从一百万以下的人数（没有发现任何循环，人们已经探索了更多的数字），你可能有兴趣知道没有循环。
要在代码中进行翻译，您可以考虑Python的方式：
MEMOIZER = dict() def memo(x, func): global MEMOIZER if x in MEMOIZER: return MEMOIZER[x] r = func(x) MEMOIZER[x] = r return r
记忆是一个非常通用的scheme。
对于Collatze猜想，您可能会遇到一些问题，因为数字可能会增长，因此您可能会炸毁可用内存。
这通常是使用caching来处理的，你只caching最后n结果（定制占用一定数量的内存），当你已经有n项目被caching并希望添加一个新项目时，就丢弃较旧的项目。
对于这个猜想，可能会有另外一个策略可用，但实施起来有点困难。 基本的想法是，你只有办法达到一个给定的数字x ：
- 从
2*x - 从
(x-1)/3
因此，如果caching2*x和(x-1)/3 ，则不再需要cachingx否则将不会再调用它（除非您希望在最后打印序列。但是只有一次）。 我把它留给你来利用这个好处，以便你的caching不会增长太多:)
我在C＃中的努力，使用LinqPad运行时间<1秒：
var cache = new Dictionary<long, long>(); long highestcount = 0; long highestvalue = 0; for (long a = 1; a < 1000000; a++) { long count = 0; long i = a; while (i != 1) { long cachedCount = 0; if (cache.TryGetValue(i, out cachedCount)) //See if current value has already had number of steps counted & stored in cache { count += cachedCount; //Current value found, return cached count for this value plus number of steps counted in current loop break; } if (i % 2 == 0) i = i / 2; else i = (3 * i) + 1; count++; } cache.Add(a, count); //Store number of steps counted for current value if (count > highestcount) { highestvalue = a; highestcount = count; } } Console.WriteLine("Starting number:" + highestvalue.ToString() + ", terms:" + highestcount.ToString());
解决原始问题中的unsigned int问题。
新增arrays用于存储预先计算的值。
include <stdio.h> #define LIMIT 1000000 unsigned int dp_array[LIMIT+1]; unsigned int iteration(unsigned int value) { if(value%2==0) return (value/2); else return (3*value+1); } unsigned int count_iterations(unsigned int value) { int count=1; while(value!=1) { if ((value<=LIMIT) && (dp_array[value]!=0)){ count+= (dp_array[value] -1); break; } else { value=iteration(value); count++; } } return count; } int main() { int iteration_count=0, max=0; int i,count; for(i=0;i<=LIMIT;i++){ dp_array[i]=0; } for (i=1; i<LIMIT; i++) { // printf("Current iteration : %d \t", i); iteration_count=count_iterations(i); dp_array[i]=iteration_count; // printf(" %d \t", iteration_count); if (iteration_count>max) { max=iteration_count; count=i; } // printf(" %d \n", max); } printf("Count = %d\ni = %d\n",max,count); }
o / p：Count = 525 i = 837799
哈斯克尔解决scheme，2秒运行时间。
thomashartman@yucca:~/collatz>ghc -O3 -fforce-recomp --make collatz.hs [1 of 1] Compiling Main ( collatz.hs, collatz.o ) Linking collatz ... thomashartman@yucca:~/collatz>time ./collatz SPOILER REDACTED real 0m2.881s
– 也许我可以用一个散列而不是一个地图来获得更快的速度。
import qualified Data.Map as M import Control.Monad.State.Strict import Data.List (maximumBy) import Data.Function (on) nextCollatz :: Integer -> Integer nextCollatz n | even n = n `div` 2 | otherwise = 3 * n + 1 newtype CollatzLength = CollatzLength Integer deriving (Read,Show,Eq,Ord) main = print longestCollatzSequenceUnderAMill longestCollatzSequenceUnderAMill = longestCollatzLength [1..1000000] -- sanity checks tCollatzLengthNaive = CollatzLength 10 == collatzLengthNaive 13 tCollatzLengthMemoized = (CollatzLength 10) == evalState (collatzLengthMemoized 13) M.empty -- theoretically could be nonterminating. Since we're not in Agda, we'll not worry about it. collatzLengthNaive :: Integer -> CollatzLength collatzLengthNaive 1 = CollatzLength 1 collatzLengthNaive n = let CollatzLength nextLength = collatzLengthNaive (nextCollatz n) in CollatzLength $ 1 + nextLength -- maybe it would be better to use hash here? type CollatzLengthDb = M.Map Integer CollatzLength type CollatzLengthState = State CollatzLengthDb -- handy for testing cLM :: Integer -> CollatzLength cLM n = flip evalState M.empty $ (collatzLengthMemoized n) collatzLengthMemoized :: Integer -> CollatzLengthState CollatzLength collatzLengthMemoized 1 = return $ CollatzLength 1 collatzLengthMemoized n = do lengthsdb <- get case M.lookup n lengthsdb of Nothing -> do let n' = nextCollatz n CollatzLength lengthN' <- collatzLengthMemoized n' put $ M.insert n' (CollatzLength lengthN') lengthsdb return $ CollatzLength $ lengthN' + 1 Just lengthN -> return lengthN longestCollatzLength :: [Integer] -> (Integer,CollatzLength) longestCollatzLength xs = flip evalState M.empty $ do foldM f (1,CollatzLength 1) xs where f maxSoFar@(maxN,lengthMaxN) nextN = do lengthNextN <- collatzLengthMemoized nextN let newMaxCandidate = (nextN,lengthNextN) return $ maximumBy (compare `on` snd) [maxSoFar, newMaxCandidate]
================================================== ==============================
这里是另一个haskell解决scheme，使用monad-memo包。 不幸的是，这一个有一个堆栈空间错误，不会影响上面的滚动我自己的记忆。
./collatzMemo + RTS -K83886080 -RTS＃这会产生答案，但更好的办法是消除空间泄漏
{-# Language GADTs, TypeOperators #-} import Control.Monad.Memo import Data.List (maximumBy) import Data.Function (on) nextCollatz :: Integer -> Integer nextCollatz n | even n = n `div` 2 | otherwise = 3 * n + 1 newtype CollatzLength = CollatzLength Integer deriving (Read,Show,Eq,Ord) main = print longestCollatzSequenceUnderAMill longestCollatzSequenceUnderAMill = longestCollatzLength [1..1000000] collatzLengthMemoized :: Integer -> Memo Integer CollatzLength CollatzLength collatzLengthMemoized 1 = return $ CollatzLength 1 collatzLengthMemoized n = do CollatzLength nextLength <- memo collatzLengthMemoized (nextCollatz n) return $ CollatzLength $ 1 + nextLength {- Stack space error ./collatzMemo Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it. Stack error does not effect rolled-my-own memoizer at http://stackoverflow.com/questions/2643260/project-euler-question-14-collatz-problem -} longestCollatzLength :: [Integer] -> (Integer,CollatzLength) longestCollatzLength xs = startEvalMemo $ do foldM f (1,CollatzLength 1) xs where f maxSoFar nextN = do lengthNextN <- collatzLengthMemoized nextN let newMaxCandidate = (nextN,lengthNextN) return $ maximumBy (compare `on` snd) [maxSoFar, newMaxCandidate] {- -- sanity checks tCollatzLengthNaive = CollatzLength 10 == collatzLengthNaive 13 tCollatzLengthMemoized = (CollatzLength 10) ==startEvalMemo (collatzLengthMemoized 13) -- theoretically could be nonterminating. Since we're not in Agda, we'll not worry about it. collatzLengthNaive :: Integer -> CollatzLength collatzLengthNaive 1 = CollatzLength 1 collatzLengthNaive n = let CollatzLength nextLength = collatzLengthNaive (nextCollatz n) in CollatzLength $ 1 + nextLength -}
==================================================
另一个，更好地考虑。 跑得不快，但还不到一分钟
import qualified Data.Map as M import Control.Monad.State import Data.List (maximumBy, nubBy) import Data.Function (on) nextCollatz :: Integer -> Integer nextCollatz n | even n = n `div` 2 | otherwise = 3 * n + 1 newtype CollatzLength = CollatzLength Integer deriving (Read,Show,Eq,Ord) main = print longestCollatzSequenceUnderAMillStreamy -- AllAtOnce collatzes = evalState collatzesM M.empty longestCollatzSequenceUnderAMillAllAtOnce = winners . takeWhile ((<=1000000) .fst) $ collatzes longestCollatzSequenceUnderAMillStreamy = takeWhile ((<=1000000) .fst) . winners $ collatzes -- sanity checks tCollatzLengthNaive = CollatzLength 10 == collatzLengthNaive 13 tCollatzLengthMemoized = (CollatzLength 10) == evalState (collatzLengthMemoized 13) M.empty -- maybe it would be better to use hash here? type CollatzLengthDb = M.Map Integer CollatzLength type CollatzLengthState = State CollatzLengthDb collatzLengthMemoized :: Integer -> CollatzLengthState CollatzLength collatzLengthMemoized 1 = return $ CollatzLength 1 collatzLengthMemoized n = do lengthsdb <- get case M.lookup n lengthsdb of Nothing -> do let n' = nextCollatz n CollatzLength lengthN' <- collatzLengthMemoized n' put $ M.insert n' (CollatzLength lengthN') lengthsdb return $ CollatzLength $ lengthN' + 1 Just lengthN -> return lengthN collatzesM :: CollatzLengthState [(Integer,CollatzLength)] collatzesM = mapM (\x -> do (CollatzLength l) <- collatzLengthMemoized x return (x,(CollatzLength l)) ) [1..] winners :: Ord b => [(a, b)] -> [(a, b)] winners xs = (nubBy ( (==) `on` snd )) $ scanl1 (maxBy snd) xs maxBy :: Ord b => (a -> b) -> a -> a -> a maxBy fxy = if fx > fy then x else y
