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

Gender: Male
Posts: 398



« on: 06-11-2011, 19:12:37 »

Ragazzi ho un problema con la ricorsione.Sul sito del prof ho provato a svolgere il seguente esercizio :

Code:
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[b];
5. A[b] = 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, 9), dove A corrisponde al seguente array:
[6, 3, 5, 3, 7, 10, 7, 1, 1]

SOLUZIONE:
3 5 7 1 3 7 6 10 1

Quello che penso io ( è che forse è sbagliato) è che l'istruzione 7 non verrà mai eseguita ,cioè il flusso del programma appena arriva all'istruzione 6 ritorna a eseguire l'istruzione 1 fino a che l'istruzione 1 sia vera e quindi finisce il programma !

Ma in base a quello che ho detto io ottengo il seguente output : 3 5 7 3 1 10 7 1 6 che è sbagliato !!! perchè dovrei ottenere 3 5 7 1 3 7 6 10 1.

Vorrei capire dov'è che sbaglio ?? Evidentemente l'istruzione 7 viene eseguita no ? Ma quando ?
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #1 on: 06-11-2011, 23:46:39 »

Certo che viene eseguita. Ora per capirlo devi disegnare sul foglio le varie chiamate ricorsive, ora non ho tempo e voglia di farlo, ma:

6 3 5 3 7 10 7 1 1

Il primo c che viene memorizzato dovrebbe essere il quarto numero (il numero 3). vengono scambiati a e b e poi l' algoritmo viene ripetuto ricorsivamente sulla prima metà dell' array:

1 3 5 3

Sempre facendo la stessa cosa, praticamente termina quando ti riduci a lavorare a sinistra su un sottoarray costituito da un solo elemento, quello dovrebbe essere il caso in cui si arresta.

Dopo aver fatto tutto questo c' è l' istruzione sette, che farà ricorsivamente la stessa cosa sull' altra metà del sottoarray: cioè:

7 10 7 1 6

P.S non ti devi lasciare ingannare dalle lettere, non è che siccome l' istruzione 7 ha la lettera c+1, b siccome nelle chiamate precedenti hai raggiunto la condizione a=b non viene eseguito. Devi considerare che a e b hanno un valore e anche c, alla riga  6 si fa la prima chiamata ricorsiva con tante altre chiamate ricorsive con i relativi indici, poi la chiamata 7 si riferirà ancora agli indici c+1 e b dell' array della prima situazione iniziale e farà ricorsivamente sul sottoarray a destra le chiamate con i relativi indici.

Spero di non aver sbagliato, ma temo di averti terribilmente confuso di più. 
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Jack&Daxter
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 398



« Reply #2 on: 07-11-2011, 02:39:02 »

  Aspetta ! Mi rendo conto che parlare di algoritmi ricorsivi in questo forum non sia molto facile per via del fatto che non si può disegnare bene . Cerco di semplificare le cose in maniera naturale-logica

Propongo la soluzione che penso io :


Si eseguono le istruzioni :

1
2
3
4
5
6

1
2
3
4
5
6

.
.
. (Si continua così con 123456 fino a quando non viene eseguito  if (a==b) then return )
.
.

Dopo ke si esegue il caso base e si lascia  BinarySwap(A, a, c) viene eseguita l'istruzione BinarySwap(A, c+1, b) ovvero l'istruzione 7, quindi :

7
1
2
3
4
5
6 QUI INCONTRA  BinarySwap(A, a, c)

E poi si ritorna all'inizio e si ricomincia con :

1
2
3
4
5
6

Il tutto viene ripetuto fino a quando anche l'istruzione 7 esegue il caso base !


Che ne dici/te può andare ?  testate  testate
« Last Edit: 07-11-2011, 02:50:11 by Jack&Daxter » Logged
Akallabet
Apprendista Forumista
**
Offline Offline

Posts: 211



« Reply #3 on: 07-11-2011, 12:57:25 »

Vorrei capire dov'è che sbaglio ?? Evidentemente l'istruzione 7 viene eseguita no ? Ma quando ?

Viene eseguita perchè ad un certo punto verrà eseguita l'istruzione
Code:
1. if (a==b) then return;

Quello che succede dopo è che, risalendo l'albero delle chiamate ricorsive, si ritorna alla chiamata della funzione
Code:
6. BinarySwap(A, a, c);
a questo punto si passa all'istruzione successiva e il gioco è fatto  ciao
Logged

Quando uccidere diventa facile come respirare è meglio fare qualche cosa per l'alito!!
Jack&Daxter
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 398



« Reply #4 on: 07-11-2011, 20:40:21 »

Risolto !!! Grazie cmq a tutti !  yoh
Logged
Nessuno
Apprendista Forumista
**
Offline Offline

Posts: 204



« Reply #5 on: 09-11-2011, 09:29:46 »

Risolto !!! Grazie cmq a tutti !  yoh

...allora posso chiederti una cosa?
la funzione floor( (a+b)/2 ) calcola il floor di un numero ovvero alla prima passata assegna a c il valore floor(5)...che sarebbe??

per def. la funzione floor(x) so' che restituisce il numero più grande che sia minore o uguale a "x"...ma in questo caso?

Logged

Sorridi anche se il tuo sorriso è triste, perchè più triste di un sorriso triste c'è la tristezza di non saper sorridere.

::Jim Morrison::
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #6 on: 09-11-2011, 09:57:55 »

In questo caso dovrebbe prendere il centro dell' array, perchè fai la somma di a+b, quindi degli indici dell' array(che in questo caso il professore se non ricordo male fa partire da 1) e divide per 2. Quindi credo che il mio intervento iniziale sia sbagliato perchè forse qui nell' esempio l' elemento c è quello in posizione 5.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Akallabet
Apprendista Forumista
**
Offline Offline

Posts: 211



« Reply #7 on: 09-11-2011, 15:04:28 »

la funzione floor( (a+b)/2 ) calcola il floor di un numero ovvero alla prima passata assegna a c il valore floor(5)...che sarebbe??
per def. la funzione floor(x) so' che restituisce il numero più grande che sia minore o uguale a "x"...ma in questo caso?

Non è questa la definizione di floor....
Il floor di un numero è la sua parte intera calcolata per difetto, per esempio: floor(2,9)=2.
Quindi il floor di un numero intero restituisce lo stesso numero, perché corrisponde con la sua parte intera: floor(5)=5.
Logged

Quando uccidere diventa facile come respirare è meglio fare qualche cosa per l'alito!!
Nessuno
Apprendista Forumista
**
Offline Offline

Posts: 204



« Reply #8 on: 09-11-2011, 16:32:48 »

grazie.
Logged

Sorridi anche se il tuo sorriso è triste, perchè più triste di un sorriso triste c'è la tristezza di non saper sorridere.

::Jim Morrison::
Pages: [1]   Go Up
Print
Jump to: