14

为正整数集定义了以下迭代序列：

n ->n/2（n 为偶数） n ->3n + 1（n 为奇数）

使用上面的规则并从 13 开始，我们生成以下序列：

13 40 20 10 5 16 8 4 2 1 可以看出，这个序列（从 13 开始，到 1 结束）包含 10 个术语。尽管尚未证明（科拉茨问题），但人们认为所有起始数字都以 1 结束。

哪个起始数字（低于 100 万）产生最长的链？

注意：一旦链启动，条款允许超过一百万。

我尝试使用蛮力方法在 C 中编写解决方案。但是，我的程序在尝试计算 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);

}
4

8 回答 8

14

您拖延的原因是因为您通过的数字大于2^31-1(aka INT_MAX); 尝试使用unsigned long long而不是int.

我最近写了一篇关于这个的博客；请注意，在 C 中，朴素的迭代方法已经足够快了。对于动态语言，您可能需要通过记忆进行优化以遵守一分钟规则（但这里不是这种情况）。

哎呀，我又做了一次（这次检查了使用 C++ 进一步可能的优化）。

于 2010-04-15T07:54:15.140 回答
9

请注意，您的蛮力解决方案通常会一遍又一遍地计算相同的子问题。例如，如果你从 开始10，你会得到5 16 8 4 2 1; 但如果你开始20，你会得到20 10 5 16 8 4 2 1。如果您10一次缓存该值，它就会被计算出来，然后就不必重新计算它了。

（这称为动态规划。）

于 2010-04-15T06:58:54.867 回答
1

刚刚在 C# 中对其进行了测试，看来 113383 是 32 位int类型变得太小而无法存储链中每个步骤的第一个值。

unsigned long在处理这些大数字时尝试使用;)

于 2010-04-15T07:49:57.583 回答
1

我前段时间解决了这个问题，幸运的是我的代码仍然存在。如果您不想剧透，请不要阅读代码：

#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
于 2010-04-15T07:55:59.897 回答
0

如前所述，最简单的方法是进行一些记忆以避免重新计算尚未计算的事物。如果您来自 100 万以下的数字，您可能有兴趣知道没有周期（尚未发现任何周期，人们已经探索了更大的数字）。

用代码翻译它，你可以想python的方式：

MEMOIZER = dict()

def memo(x, func):
  global MEMOIZER
  if x in MEMOIZER: return MEMOIZER[x]

  r = func(x)

  MEMOIZER[x] = r

  return r

记忆是一个非常通用的方案。

对于 Collat​​ze 猜想，您可能会遇到一些困难，因为数字确实会增长，因此您可能会炸毁可用内存。

这传统上使用缓存来处理，您只缓存最后的n结果（为占用给定的内存量而定制），当您已经n缓存了项目并希望添加新的项目时，您丢弃旧的。

对于这个猜想，可能有另一种策略可用，尽管实施起来有点困难。基本思想是您只有达到给定数字的方法x：

  • 从2*x
  • 从(x-1)/3

因此，如果您缓存 的结果2*x并且不再(x-1)/3缓存x>> 它将永远不会被调用（除非您希望在最后打印序列......但它只是一次）。我把它留给你利用这一点，这样你的缓存就不会增长太多:)

于 2010-04-15T07:35:08.603 回答
0

我在 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());
于 2014-04-24T06:58:27.347 回答
0

修复原始问题中的 unsigned int 问题。

添加了用于存储预计算值的数组。

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：计数 = 525 i = 837799

于 2014-04-25T07:04:20.807 回答
-1

Haskell 解决方案，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]

==================================================== ===============================

这是另一个使用 monad-memo 包的 haskell 解决方案。不幸的是，这个有一个堆栈空间错误，不会影响上面的roll-my-own memoizer。

./collat​​zMemo +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 f x y = if f x > f y then x else y
于 2012-11-04T07:57:59.500 回答