Pagina 1 di 1

Somma di interi

Inviato: 06 feb 2010, 18:33
da rand
Le cifre decimali di due interi x e y (arbitrariamente grandi) sono rappresentate tramite due liste di interi tra 0 e 9 singolarmente linkate. Vale a dire ogni nodo di ciascuna lista contiene una cifra e un puntatore alla cifra successiva (ma non alla precedente).

Problema: dare un algoritmo che metta in una liste le cifre di x+y usando tempo e spazio ottimi .

Inviato: 08 feb 2010, 17:49
da rand
Notate che non è una banale trasposizione della somma di interi, perchè l'algoritmo da scuola materna richiede alla meglio spazio aggiuntivo lineare, data la particolare rappresentazione dell'input.
Infatti, facendo la somma con riporto nel modo banale, dobbiamo elaborare le cifre nell'ordine dalla meno significativa alla più significativa. Il punto è che le cifre dell'input ci sono presentate in una lista
nell' ordine esattamente inverso, ossia con un puntatore da ogni cifra a quella che la precede immediatamente in ordine di significatività.
Di conseguenza, se vogliamo scandire la lista in senso contrario non abbiamo altra strada che costruire esplicitamente la lista riversata, il che però richiede spazio aggiuntivo lineare.
Questa non è la soluzione ottima. Infatti c'è modo di sommare in spazio costante e tempo lineare.

Inviato: 08 feb 2010, 18:45
da fph
Intendi ottimi a meno di costanti moltiplicative, come spesso fanno in informatica, oppure proprio "che con un'istruzione in meno non si può"?

Inviato: 08 feb 2010, 19:37
da rand
Chiaramente ottimi in senso asintotico. In altre parole la soluzione ottima deve usare spazio (=numero di celle di memoria) aggiuntivo costante e indipendente dalla dimensione dell'input, e tempo proporzionale alla dimensione dell'input.

Inviato: 08 feb 2010, 20:23
da kwehmucdee
Ma come fa ad utilizzare spazio indipendente dalla dimensione dell'input se hai detto che la somma va in un'altra lista? Se parli di spazio aggiuntivo, oltre alla lista per la somma ok, oppure volendo si può mettere il risultato in una delle liste contenente gli addendi.

Assumendo che il numero di decimali sia lo stesso, e tralasciando la parte intera:
pseudocodice:

Codice: Seleziona tutto

cifra_x = x.first
cifra_y = y.first
cifra_z = z.first
prec = null
do
{
    cifra_z.valore = (cifra_x.valore + cifra_y.valore) % 10
    if (cifra_x.valore + cifra_y.valore > 9 && prec != null)
    {
        prec.valore++;
    }
    prec = cifra_z
    cifra_x = cifra_x.next
    cifra_y = cifra_y.next
    cifra_z = cifra_z.next
}
while (cifra_x.next != null)
basandosi sul fatto che le due cifre in posizione i possono influenzare nel peggiore dei casi solo la somma delle cifre in posizione i-1.

Inviato: 08 feb 2010, 22:14
da rand
Non ho capito cosa intendi per tralasciando la parte intera, ma
stando al tuo pseudocodice 999 + 001 farebbe 900.

Inviato: 10 mag 2010, 17:32
da lerks
Tecnicamente non sarebbe spazio costante, dato che viene allocata della memoria nello stack ad ogni chiamata della funzione ricorsiva, ma almeno non alloco niente in modo esplicito (nel senso che non creo altre strutture dati a parte quelle per l'input e per l'output)

(codice in C++, senza gli "#include")

Codice: Seleziona tutto

struct cifra {
    int valore;
    cifra *successiva;
};

int somma (cifra *uno, cifra *due, cifra* risultato) {
    risultato->valore = uno->valore + due->valore;
    if (uno->successiva != NULL) {
        risultato->successiva = new cifra;
        risultato->valore += somma (uno->successiva, due->successiva, risultato->successiva);
    }
    int riporto = risultato->valore / 10;
    risultato->valore %= 10;
    return riporto;
}

int main () {
    // Date due liste X e Y, di tipo cifra*

    cifra *parziale = new cifra;
    cifra *risultato;
    int riporto = somma (X, Y, parziale);
    if (riporto != 0) {
        risultato = new cifra;
        risultato->valore = riporto;
        risultato->successiva = parziale;
    }
    else
        risultato = parziale;

    // Utilizza la lista risultato
}
Assunzioni:
X e Y hanno la stessa lunghezza

Inviato: 14 mag 2010, 11:34
da rand
E' ovvio, così usi lo stack per tenere i riporti, e quindi usi spazio aggiuntivo lineare. Si può fare senza ricorsione e in spazio costante.

Inviato: 14 mag 2010, 22:19
da taifu

Codice: Seleziona tutto

#include "stdlib.h"
#include "stdio.h"

typedef struct digit {
    int v;
    struct digit *next;
} digit;

int main () {

	// assumiamo le due liste X,Y della stessa lunghezza (positiva)
	digit *result = (digit *)(malloc(sizeof(digit))); //lista contente il risultato della somma
	digit *elmX = X; //primo elemento della lista X
	digit *elmY = Y; //primo elemento della lista Y
	digit *c = NULL;
	int k = 0;
	int sum1, sum2;	
	int n = length(X); //lunghezza delle liste

	// aggiungo uno 0 in testa al risultato, se non serve viene rimosso alla fine
	elmR->v = 0;
	elmR->next = (digit *)(malloc(sizeof(digit)));

	for(int i=0; i<n; i++){
    
		sum1 = elmX->v + elmY->v;
		sum2 = (i != n-1) ? elmX->next->v + elmY->next->v : 0;

		if(sum2 > 9) sum1++;

		if(sum2 != 9){
			if(sum1 > 9 && c!=NULL) { // modifica le cifre subito precedenti(se necessario) trasferendo il riporto
			                          // se sono presenti dei 9, la cifra precedente a questi 9 è c e il numero 
			                          // di cifre da modificare è indicato da k
				for(int j=0; j<k; j++){
					c->v = (c->v+1) % 10;
					c = c->next;
				}
			}
			c = NULL;
		}
		else { 
			if (c != NULL) { k++; }
			else {
				k = 1;
				c = elmR;
				if(i==0) { if(sum1 == 9) k=2; else c=elmR->next;}
			}
		}
	
		if(i == 0) {
			if(sum1 > 9) elmR->v=1;
			elmR = elmR->next;
		}
	
		elmR->v = sum1 % 10;

		if(i != n-1){
			elmR->next = (struct digit *)(malloc(sizeof(digit)));
		}
		
		elmR = elmR->next;
		elmX = elmX->next;
		elmY = elmY->next;
	}

	if(result->v == 0) result = result->next;
}
è lineare in quanto ogni elemento della lista viene visitato al più 2 volte

p.s. scusate per il pessimo codice :oops: