memorizzare sequenze note in c

Question

su cui sto lavorando Project Euler # 14 in C e hanno capito l'algoritmo di base; tuttavia, viene eseguito insopportabilmente lento per grandi numeri, per esempio 2.000.000 come voleva; Presumo perché deve generare la sequenza più e più volte, anche se ci dovrebbe essere un modo per memorizzare sequenze note (ad esempio, una volta che si arriva a un 16, sappiamo per esperienza precedente che i prossimi numeri sono 8, 4, 2 , poi 1).

Non sono esattamente sicuro di come fare questo con array di lunghezza fissa di C, ma ci deve essere un buon modo (che è incredibilmente efficiente, ne sono sicuro). Grazie in anticipo.

Ecco quello che ho attualmente, se aiuta.

#include <stdio.h>
#define UPTO 2000000

int collatzlen(int n);

int main(){
    int i, l=-1, li=-1, c=0;
    for(i=1; i<=UPTO; i++){
        if( (c=collatzlen(i)) > l) l=c, li=i;
    }
    printf("Greatest length:\t\t%7d\nGreatest starting point:\t%7d\n", l, li);
    return 1;
}

/* n != 0 */
int collatzlen(int n){
    int len = 0;
    while(n>1) n = (n%2==0 ? n/2 : 3*n+1), len+=1;
    return len;
}

Answer 1

Il programma originale ha bisogno di 3,5 secondi sulla mia macchina. È insopportabilmente lento per voi?

Il mio sporca e brutta versione ha bisogno di 0,3 secondi. Si utilizza una matrice globale per memorizzare i valori già calcolati. E utilizzarli nei calcoli futuri.

int collatzlen2(unsigned long n);
static unsigned long array[2000000 + 1];//to store those already calculated

int main()
{
    int i, l=-1, li=-1, c=0;
    int x;
    for(x = 0; x < 2000000 + 1; x++) {
        array[x] = -1;//use -1 to denote not-calculated yet
    }

    for(i=1; i<=UPTO; i++){
        if( (c=collatzlen2(i)) > l) l=c, li=i;
    }
    printf("Greatest length:\t\t%7d\nGreatest starting point:\t%7d\n", l, li);

    return 1;
}

int collatzlen2(unsigned long n){
    unsigned long len = 0;
    unsigned long m = n;
    while(n > 1){
        if(n > 2000000 || array[n] == -1){ // outside range or not-calculated yet
            n = (n%2 == 0 ? n/2 : 3*n+1);
            len+=1;
        }
        else{ // if already calculated, use the value
            len += array[n];
            n = 1; // to get out of the while-loop
        }
    }
    array[m] = len;
    return len;
}

Answer 2

Dato che questo è essenzialmente un programma e getta (vale a dire una volta che hai eseguito e ottenuto la risposta, non hai intenzione di essere di supporto per anni :), vi suggerisco di avere una variabile globale per contenere la lunghezze di sequenze già calcolati:

int lengthfrom[UPTO] = {};

Se la dimensione massima è di qualche milione, allora stiamo parlando di megabyte di memoria, che dovrebbe facilmente nella RAM in una sola volta.

Quanto sopra si inizializzare la matrice di zeri all'avvio. Nel programma - per ogni iterazione, controllare se l'array contiene zero. Se lo fa - si dovrà andare avanti con il calcolo. Se no - poi si sa che portare avanti sarebbe andato avanti per che molti più iterazioni, quindi basta aggiungere che per il numero che hai fatto fino ad ora e il gioco è fatto. E quindi memorizzare il nuovo risultato nella matrice, ovviamente.

Non essere tentati di utilizzare una variabile locale per una serie di queste dimensioni:. Che cercherà di allocare in pila, che non sarà abbastanza grande e probabilmente in crash

Inoltre - ricorda che con questa sequenza i valori salgono così come verso il basso, quindi avrai bisogno di far fronte a che nel vostro programma (probabilmente per avere la matrice più lungo di valori FINO, e utilizzando un assert() di guardia contro gli indici maggiore della dimensione della matrice).

Answer 3

Se non ricordo male, il problema non è un algoritmo lento: l'algoritmo che hai ora è abbastanza veloce per quello che PE si chiede di fare. Il problema è di overflow: a volte si finisce per moltiplicare il proprio numero da 3 così tante volte che alla fine superare il valore massimo che può essere memorizzato in un int firmato. Utilizzare unsigned int, e se questo non fa ancora del lavoro (ma sono abbastanza sicuro che lo fa), l'uso a 64 bit interi (long long).

Questo dovrebbe correre molto velocemente, ma se si vuole fare ancora più veloce, le altre risposte già affrontato questo.