Projeto Euler Pergunta 14 (Problema de Collatz)
https://stackoverflow.com/questions/2643260
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
A seguinte sequência iterativa é definida para o conjunto de números inteiros positivos:
n -> n/2 (n é par) n -> 3n + 1 (n é ímpar)
Usando a regra acima e começando com 13, geramos a seguinte sequência:
13 40 20 10 5 16 8 4 2 1 Pode -se observar que essa sequência (a partir de 13 e terminando em 1) contém 10 termos. Embora ainda não tenha sido comprovado (problema de Collatz), pensa -se que todos os números iniciais terminam em 1.
Qual número inicial, abaixo de um milhão, produz a cadeia mais longa?
NOTA: Depois que a cadeia iniciar, os termos podem acima de um milhão.
Tentei codificar uma solução para isso em C usando o método Bruteforce. No entanto, parece que o meu programa está parado ao tentar calcular 113383. Aconselhar :)
#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);
}
Solução
A razão pela qual você está paralisando é porque você passa por um número maior que 2^31-1 (também conhecido como INT_MAX); tente usar unsigned long long ao invés de int.
eu recentemente blogou sobre isso; Observe que em C o método iterativo ingênuo é mais do que rápido o suficiente. Para idiomas dinâmicos, você pode precisar otimizar, memórias para obedecer ao regra de um minuto (Mas esse não é o caso aqui).
Opa i Fiz de novo (Desta vez, examinando outras otimizações possíveis usando C ++).
Outras dicas
Observe que sua solução de força bruta geralmente calcula os mesmos subproblemas repetidamente. Por exemplo, se você começar com 10, você entendeu 5 16 8 4 2 1; Mas se você começar com 20, você entendeu 20 10 5 16 8 4 2 1. Se você cache o valor em 10 Uma vez calculado, não precisará calcular tudo de novo.
(Isso é conhecido como programaçao dinamica.)
Eu resolvi o problema há algum tempo e, felizmente, ainda tenho meu código. Não leia o código se você não quiser um spoiler:
#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
Tendo acabado de testar em C#, parece que 113383 é o primeiro valor em que os 32 bits int O tipo se torna pequeno demais para armazenar todas as etapas da corrente.
Tente usar um unsigned long ao lidar com esses grandes números;)
Como já foi dito, a maneira mais simples é obter alguma memórias para evitar recomputar coisas que não foram calculadas. Você pode estar interessado em saber que não há ciclo se você está sendo de um número abaixo de um milhão (nenhum ciclo foi descoberto ainda, e as pessoas exploraram números muito maiores).
Para traduzi -lo em código, você pode pensar da maneira Python:
MEMOIZER = dict()
def memo(x, func):
global MEMOIZER
if x in MEMOIZER: return MEMOIZER[x]
r = func(x)
MEMOIZER[x] = r
return r
A memaçãoização é um esquema muito genérico.
Para a conjectura de Collatze, você pode ser executado um pouco, porque os números podem realmente crescer e, portanto, você pode explodir a memória disponível.
Isso é tradicionalmente tratado usando o cache, você só cache o último n resultados (adaptados para ocupar uma determinada quantidade de memória) e quando você já tem n Os itens em cache e desejam adicionar um mais novo, você descarta o mais antigo.
Para esta conjectura, pode haver outra estratégia disponível, embora um pouco mais difícil de implementar. A idéia básica é que você tem apenas maneiras de alcançar um determinado número x:
- a partir de
2*x - a partir de
(x-1)/3
Portanto, se você cache os resultados de 2*x e (x-1)/3 Não faz sentido em cache x mais >> nunca mais será chamado (exceto se você deseja imprimir a sequência no final ... mas é apenas uma vez). Deixo para você tirar proveito disso para que seu cache não cresça muito :)
Meu esforço em C#, tempo de execução <1 segundo usando Linqpad:
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());
Corrigindo a questão int não assinada na pergunta original.
Array adicionado para armazenar valores pré-computados.
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: contagem = 525 i = 837799
Solução Haskell, tempo de 2 segundos.
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
- Talvez eu pudesse ter conseguido um pouco mais rápido usando um hash em vez de um mapa.
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]
================================================================================
E aqui está outra solução Haskell, usando o pacote Monad-Memo. Infelizmente, este possui um erro de espaço de pilha que não afeta o Memoizer do meu próprio próprio próprio.
./CollatzMemo +RTS -K83886080 -RTS # Isso produz a resposta, mas seria apostar para eliminar o vazamento de espaço
{-# 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
-}
==================================================
Outro, considerando mais bem. não funciona tão rápido, mas ainda bem abaixo de um minuto
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
