giochno: Tecniche inplace di swap

[3nigma666]

A lezione di Algoritmi e strutture dati ,il professore ci ha dato alcuni giorni fa un giochino interessante da risolvere,su come copiare il valore di due variabili con la "tecnica inplace" ovverosia senza l'utilizzo di variabili temporanee.
Io l ho risolto in questa maniera ma serebbe divertente trovare altre idee,magari anke piu funzionali:

void swap (int& a, int& b) {

// A B
a = b + a; // (a+b) b
b = a - b; // (a+b) (a+b)-b
a = a - b; // (a+b)-a a
// RISULTATO B A
};

chi ne trova altri...?

[Ziosilvio]

Vediamo: il tuo algoritmo si basa sul fatto che tra gli interi si può fare la somma.
Ora, la somma è una permutazione parametrizzata in ciascuno dei suoi argomenti: ossia, per ogni valore fissato di a, la funzione che manda b in a+b è invertibile, e per ogni valore fissato di b, la funzione che manda a in a+b è invertibile.
Perciò: supponiamo di avere delle variabili a, b di un tipo T, e una mappa f : TxT --> T per la quale esistono una g tale che g(x,f(x,t))=t e f(x,g(x,t))=t per ogni x fissato, e una h tale che h(f(t,x),x)=t ed f(h(t,x),x)=t per ogni x fissato. Vogliamo trasformare la coppia (a,b) nella coppia (b,a).
PASSO 1: scriviamo f(b,a) in a. Otteniamo la coppia (f(b,a),b).
PASSO 2: scriviamo g(b,a) in b. Otteniamo la coppia (f(b,a),g(b,f(b,a)))=(f(b,a),a).
PASSO 3: scriviamo h(a,b) in a. Otteniamo la coppia (h(f(b,a),a),a)=(b,a).
Questo generalizza il tuo algoritmo, perché nel tuo caso f(a,b)=a+b, g(a,b)=b-a, h(a,b)=a-b.
Il problema è che, per risparmiare una variabile, si usano tre funzioni, e queste richiedono sicuramente più spazio in memoria!

[VICIUS]

Io conoscevo questo:

int a = 1;
int b = 9;

a ^= b ^= a ^= b;

ciao

[ghiotto86]

edit

[Ziosilvio]

Originariamente inviato da VICIUS

int a = 1;
int b = 9;

a ^= b ^= a ^= b;

GRANDE!!!
Infatti l'OR esclusivo bit-a-bit è una permutazione parametrizzata involutoria, cioè applicata due volte dà l'identità.
Tra l'altro è velocissimo.

[end.is.forever]

Originariamente inviato da VICIUS
Io conoscevo questo:

int a = 1;
int b = 9;

a ^= b ^= a ^= b;

ciao

C'è da dire che però questo fa uso di risultati parziali, che in un certo senso è un po come avere una variabile in più; anche se a livello di linguaggio la soluzione con variabile temp sembra usare più risorse bisogna vedere in che modo vengono tradotte le due soluzioni dal compilatore usato.

[Blackat]

esiste anche come istruzione in assembler....se non sbaglio
dovrebbe essere XCHG registro,registro

[3nigma666]

grandissimi ragazzi..sto forum è megagalattico :d