Project Euler Interrogazione 14 (Collatz Problem)
https://stackoverflow.com/questions/2643260
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
è definito il seguente sequenza iterativa per l'insieme degli interi positivi:
n -> n / 2 (n è pari) n -> 3n + 1 (n è dispari)
Utilizzando la regola di cui sopra e partendo da 13, si genera la seguente sequenza:
13 40 20 10 5 16 8 4 2 1 Si può notare che questa sequenza (a partire da 13 e terminando a 1) contiene 10 termini. Anche se non è stato ancora dimostrato (Collatz problema), si ritiene che tutti i numeri che iniziano terminano alle 1.
Quale numero di partenza, sotto un milione, produce la catena più lunga?
. NOTA: Una volta che la catena avvia i termini sono autorizzati ad andare al di sopra di un milione
Ho cercato di codifica una soluzione a questo in C utilizzando il metodo bruteforce. Tuttavia, sembra che il mio programma si arresta quando si cerca di calcolare 113383. Si prega di consiglio:)
#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);
}
Soluzione
Il motivo per cui stai stallo è perché si passa attraverso un numero maggiore di 2^31-1 (aka INT_MAX); provare a utilizzare unsigned long long invece di int.
bloggato su questo ; Si noti che in C il metodo iterativo ingenuo è più che abbastanza veloce. Per i linguaggi dinamici, potrebbe essere necessario ottimizzare per memoizing al fine di obbedire al regola uno minuti (ma questo non è il caso qui).
ha fatto di nuovo (questo tempo esaminando ulteriori ottimizzazioni possibile utilizzando C ++).
Altri suggerimenti
Si noti che la soluzione di forza bruta spesso calcola gli stessi sottoproblemi più e più volte. Ad esempio, se si inizia con 10, si ottiene 5 16 8 4 2 1; ma se si inizia con 20, si ottiene 20 10 5 16 8 4 2 1. Se in cache il valore a 10 una volta che è calcolato, e quindi non dovrà calcolare tutto da capo.
(Questo è noto come programmazione dinamica .)
ho risolto il problema qualche tempo fa e hanno per fortuna ancora il mio codice. Non leggere il codice, se non si vuole uno 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
Dopo aver appena testato in C #, sembra che 113383 è il primo valore in cui il tipo int a 32 bit diventa troppo piccolo per memorizzare ogni fase della catena.
Prova ad utilizzare un unsigned long durante la manipolazione di questi grandi numeri;)
Come è stato detto, il modo più semplice è quello di ottenere un po 'Memoizzazione per evitare ricalcolare le cose che non sono state calcolate. Potreste essere interessati a sapere che non c'è ciclo se voi di essere da un numero sotto di un milione (nessun ciclo è stato ancora scoperto, e la gente ha esplorato i numeri molto più grandi).
Per tradurre in codice, si può pensare il modo in python:
MEMOIZER = dict()
def memo(x, func):
global MEMOIZER
if x in MEMOIZER: return MEMOIZER[x]
r = func(x)
MEMOIZER[x] = r
return r
Memoizzazione è uno schema molto generico.
Per la congettura Collatze, si potrebbe incorrere in un po 'di un pizzico perché i numeri possono davvero crescere e di conseguenza si potrebbe far saltare la memoria disponibile.
Questa è tradizionalmente gestita utilizzando la cache, di mettere in cache solo gli ultimi risultati n (su misura per occupare una data quantità di memoria) e quando si dispone già di articoli n memorizzati nella cache e desidera aggiungere una più recente, è eliminare il più vecchio.
Per questa congettura ci potrebbe essere un'altra strategia a disposizione, anche se un po 'più difficile da implementare. L'idea di base è che si deve solo modi per raggiungere un dato numero x:
- da
2*x - da
(x-1)/3
Quindi se in cache i risultati di 2*x e (x-1)/3 non v'è alcun punto in caching x più >> si otterrà mai più chiamato (a meno che non si desidera stampare la sequenza alla fine ... ma è solo una volta ). Lascio a voi di approfittare di questo in modo che la cache non cresce troppo:)
Il mio sforzo in C #, tempo di esecuzione <1 secondo con 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());
Risoluzione del problema unsigned int nella domanda iniziale.
array aggiunto per memorizzare valori pre-calcolati.
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 = 837.799
soluzione Haskell, due secondi tempo di esecuzione.
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
-. Forse avrei potuto ottenere un po 'più veloce utilizzando un hash invece di una mappa
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 qui è un'altra soluzione Haskell, utilizzando il pacchetto monade-memo. Purtroppo, questo ha un errore di spazio di stack che non pregiudica il memoizer laminati-my-own sopra.
./ collatzMemo + RTS -K83886080 -RTS # questo produce la risposta, ma sarebbe bettter per eliminare lo spazio di fuga
{-# 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
-}
=============================================== ===
un altro, scomposto più bene. non correre più veloce, ma ancora ben al di sotto di un 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
