Somma di interi

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Somma di interi

Messaggio da rand » 06 feb 2010, 18:33

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 .

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 08 feb 2010, 17:49

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.

fph
Site Admin
Messaggi: 3315
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 08 feb 2010, 18:45

Intendi ottimi a meno di costanti moltiplicative, come spesso fanno in informatica, oppure proprio "che con un'istruzione in meno non si può"?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 08 feb 2010, 19:37

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.

kwehmucdee
Messaggi: 17
Iscritto il: 16 gen 2010, 19:38
Contatta:

Messaggio da kwehmucdee » 08 feb 2010, 20:23

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.

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 08 feb 2010, 22:14

Non ho capito cosa intendi per tralasciando la parte intera, ma
stando al tuo pseudocodice 999 + 001 farebbe 900.

lerks
Messaggi: 10
Iscritto il: 19 nov 2009, 18:22

Messaggio da lerks » 10 mag 2010, 17:32

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

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 14 mag 2010, 11:34

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.

taifu
Messaggi: 10
Iscritto il: 12 mag 2010, 14:09

Messaggio da taifu » 14 mag 2010, 22:19

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:

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite