Intereting Posts

Проект Эйлера Вопрос 14 (проблема Collatz)

Для множества положительных целых чисел определена следующая итеративная последовательность:

n -> n / 2 (n четно) n -> 3n + 1 (n нечетно)

Используя правило выше и начиная с 13, мы создаем следующую последовательность:

13 40 20 10 5 16 8 4 2 1 Можно видеть, что эта последовательность (начиная с 13 и заканчивая 1) содержит 10 терминов. Хотя это еще не доказано (проблема Collatz), считается, что все начальные числа заканчиваются на 1.

Какой стартовый номер, менее одного миллиона, производит самую длинную цепь?

ПРИМЕЧАНИЕ. Как только цепочка начинается, условия могут превышать один миллион.

Я пробовал кодировать решение для этого в C, используя метод bruteforce. Тем не менее, похоже, что моя программа ложится при попытке рассчитать 113383. Пожалуйста, посоветуйте 🙂

#include  #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; imax) { max=iteration_count; count=i; } } //iteration_count=count_iterations(113383); printf("Count = %d\ni = %d\n",max,count); } 

Причина, по которой вы застопориваетесь, состоит в том, что вы проходите через число больше 2^31-1 (aka INT_MAX ); попробуйте использовать unsigned long long вместо int .

Я недавно писал об этом в блоге ; обратите внимание, что в C наивный итерационный метод более чем достаточно быстрый. Для динамических языков вам может потребоваться оптимизировать с помощью memoizing, чтобы подчиняться правилу за одну минуту (но здесь это не так).


К сожалению, я сделал это снова (на этот раз изучая дальнейшие возможные оптимизации с использованием C ++).

Обратите внимание, что ваше решение грубой силы часто снова и снова вычисляет одни и те же подзадачи. Например, если вы начинаете с 10 , вы получаете 5 16 8 4 2 1 ; но если вы начинаете с 20 , вы получаете 20 10 5 16 8 4 2 1 . Если вы забудете значение в 10 раз, как только оно будет вычислено, и тогда ему не придется вычислять его снова и снова.

(Это называется динамическим программированием ).

Я решил проблему некоторое время назад и, к счастью, все еще имею мой код. Не читайте код, если вы не хотите спойлера :

 #include  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 #, похоже, что 113383 – это первое значение, когда 32-битный тип int становится слишком маленьким, чтобы хранить каждый шаг в цепочке.

Попытайтесь использовать 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 

Воспоминание – очень общая схема.

Для гипотезы Collatze вы можете столкнуться с небольшим разрывом, потому что цифры могут действительно расти, и поэтому вы можете взорвать доступную память.

Это традиционно обрабатывается с помощью кеширования, вы кэшируете только последние n результатов (с учетом занимаемого объема памяти), и когда у вас уже есть n элементов, кешированных и желающих добавить более новый, вы отбрасываете более старый.

Для этой гипотезы может быть и другая страtagsя, хотя ее немного сложнее реализовать. Основная идея заключается в том, что у вас есть только способы достижения заданного числа x :

  • от 2*x
  • из (x-1)/3

Поэтому, если вы кешируете результаты 2*x и (x-1)/3 больше нет кеширования x он больше не будет вызываться (за исключением того, что вы хотите напечатать последовательность в конце. но это только один раз). Я оставляю это для вас, чтобы воспользоваться этим, чтобы ваш кеш не увеличивался слишком много 🙂

Мое усилие в C #, время выполнения <1 секунда с использованием LinqPad:

 var cache = new Dictionary(); 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()); 

Исправление неподписанной проблемы int в исходном вопросе.

Добавлен массив для хранения предварительно вычисленных значений.

 include  #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; imax) { max=iteration_count; count=i; } // printf(" %d \n", max); } printf("Count = %d\ni = %d\n",max,count); } в include  #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; imax) { max=iteration_count; count=i; } // printf(" %d \n", max); } printf("Count = %d\ni = %d\n",max,count); } 

o / p: Count = 525 i = 837799

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] 

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

И вот еще одно решение haskell, использующее пакет monad-memo. К сожалению, у этого есть ошибка пространства стека, которая не влияет на вышеперечисленный memoizer.

./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