Somma di interi
Somma di interi
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 .
Problema: dare un algoritmo che metta in una liste le cifre di x+y usando tempo e spazio ottimi .
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.
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.
-
- Messaggi: 17
- Iscritto il: 16 gen 2010, 19:38
- Contatta:
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:
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.
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)
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")
Assunzioni:
X e Y hanno la stessa lunghezza
(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
}
X e Y hanno la stessa lunghezza
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;
}
p.s. scusate per il pessimo codice
