Pages: [1]   Go Down
Print
Author Topic: Ricorsione..  (Read 906 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Grillo
Apprendista Forumista
**
Offline Offline

Posts: 219


« on: 21-09-2010, 15:05:44 »

Non riesco a risolverlo, fino al punto 4 ci arrivo, e dopo il 5 e il 6 si fanno assieme?
cioè il nuovo (A, a, b) quale diventa, per a si prende a o c+1; e per b quale si prende c o b. help please!!
o qualcuno potrebbe descrivermi la procedura passo passo se vi viene complicato?

Si consideri il seguente algoritmo ricorsivo BinaryChange:
BinaryChange(A, a, b)

1. if (a==b) then return;
2. c = floor ((a+b)/2);
3. scambia A[a] con A[c];
4. scambia A[c+1] con A;
5. BinaryChange(A, a, c);
6. BinaryChange(A, c+1, b);

Descrivere il corretto output ritornato dall'algoritmo se eseguito sui parametri (A, 1, 9), dove A corrisponde al seguente array:
[4, 2, 10, 7, 5, 5, 6, 6, 5]
Logged
dani89
Apprendista Forumista
**
Offline Offline

Posts: 254



« Reply #1 on: 21-09-2010, 19:35:58 »

Descrivere il corretto output ritornato dall'algoritmo se eseguito sui parametri (A, 1, 9), dove A corrisponde al seguente array:
[4, 2, 10, 7, 5, 5, 6, 6, 5]
il binary change al primo passo scambia il primo elemento con l'ultimo.
poi devi dividere in 2 l'array(in questo caso i primi 5 e gli ultimi 4).
quindi l'array diventa: 4 2 10 7 5          5 6 6 5
scambi primo e ultimo elemento dei 2 sottoarray
5 2 10 7 4    5 6 6 5
dividi ancora
5 2 10    74   5 6   6 5
e scambi in ogni sottoarray
10 2 5   4 7   6 5   5 6
gli ultimi 3 sottoarray sono già ordinati(sono rimasti solo 2 elementi) quindi rimane solo il primo che ha 3 elementi.
10 2   5   4 7   6 5   5 6
e scambi nel primo sottoarray
2 10 5 4 7 6 5 5 6    dovrebbe essere questa la soluzione corretta ok
Logged
Grillo
Apprendista Forumista
**
Offline Offline

Posts: 219


« Reply #2 on: 22-09-2010, 12:07:34 »

Grazie 1000.. perfetto adesso l'ho capito.
ma il binarySwap è la stessa cosa?
Si consideri il seguente algoritmo ricorsivo BinarySwap:
BinarySwap(A, a, b)
1. if (a==b) then return;
2. c = floor ((a+b)/2);
3. tmp = A[a];
4. A[a] = A;
5. A = tmp;
6. BinarySwap(A, a, c);
7. BinarySwap(A, c+1, b);

Descrivere il corretto output ritornato dall'algoritmo se eseguito sui parametri (A, 1, Cool, dove A corrisponde al seguente array:
[5, 9, 4, 2, 3, 1, 7, 5]


e invece questo?
BinarySelect(A, a, b)
1. if (a==b) then return A[a];
2. c = floor ((a+b)/2);
3. S1 = S2 = 0;
4. for i=a to c do S1 = S1 + A;
5. for i=c+1 to b do S2 = S2 + A;
6. if (S1 > S2) then return BinarySelect(A, a, c);
7. else return BinarySelect(A, c+1, b);

Descrivere il corretto output ritornato dall'algoritmo se eseguito sui parametri (A, 1, 12), dove A corrisponde al seguente array:
[4, 5, 5, 8, 10, 2, 3, 8, 9, 1, 10, 7]

Grazie della tua disponibilità, così completo le tre procedure della ricorsione che ci sono negli esercizi.
Logged
dani89
Apprendista Forumista
**
Offline Offline

Posts: 254



« Reply #3 on: 22-09-2010, 12:41:59 »

il binary swap cambia solo il primo passaggio, in cui al posto di invertire primo e ultimo devi dividere l'array in 2 e cambiare gli estremi, per il resto è uguale
Logged
Grillo
Apprendista Forumista
**
Offline Offline

Posts: 219


« Reply #4 on: 22-09-2010, 13:45:54 »

Perfetto riuscito..
e il BinarySelect invece? un consiglio?
Logged
Grillo
Apprendista Forumista
**
Offline Offline

Posts: 219


« Reply #5 on: 22-09-2010, 14:30:38 »

ho risolto pure il binarySelect.. grazie!!
Logged
Pages: [1]   Go Up
Print
Jump to: