Pages: [1] 2   Go Down
Print
Author Topic: Esercizio 1 (Metodo ricorsivo)  (Read 2881 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
TheSpecialOne
Apprendista Forumista
**
Offline Offline

Posts: 232



« on: 10-04-2009, 14:16:24 »

Code:
Scrivere un metodo ricorsivo che data una lista di interi riordini L in modo che tutti
gli elementi dispari precedano, nello stesso ordine in cui comparivano inizialmente
tutti gli elementi pari (es.L=3,7,8,1,4  si ottiene L = 3,7,1,8,4)

Ho un grosso problema, nonostante a livello teorico abbia capito la ricorsione!

Ho provato ad individuare il caso base, che nello specifico dovrebbe essere quando la lista
è stata esaminata per intero, oppure quando gli elementi sono tutti pari, quindi non c'è
bisogno di effetturare nessuno scambio.
Però poi non sò andare avanti, non sò con quali parametri richiamare il metodo all'interno del
suo corpo, in quanto questo deve avvenire solo se l'elemento è dispari.

Qualcuno di voi saprebbe darmi una mano???
Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #1 on: 10-04-2009, 14:58:00 »

Ciao, io sono riuscito a trovare la soluzione al problema univ.
Il codice è commentato in modo che si possa capire quello che viene fatto.
Eccola: *mi sono accorto che c'è un prob.

Code:
import javax.swing.*;
public class ordina
{
public static Lista rewind(Lista L)
{
Nodo aux=L.getHead(); //salvo in una variabile Nodo il valore della testa

//CASO BASE
if(aux.getNext()==null)
return L; //la ricerca termina quando la lista si esaurisce
//PASSO INDUTTIVO
else
{
if( aux.getInfo()%2==0 && (aux.getNext()).getInfo()%2==1 ) //controllo che il primo valore sia pari e il successivo dispari
{
//------------SWAP-----------//
int tmp=aux.getInfo();
aux.setInfo( (aux.getNext()).getInfo() );
(aux.getNext()).setInfo(tmp);
//------------FINE-----------//

//collego ricorsivamente il puntatore della testa che risulta essere "aux", con il metodo rewind che prende la stessa lista la cui testa parte però dal nodo successivo alla testa
aux.setNext( rewind(new Lista(aux.getNext())).getHead() );
return new Lista(aux);
}
else
{
//idem sopra
aux.setNext( rewind(new Lista(aux.getNext())).getHead() );
return new Lista(aux);
}
}
}

//------------------------------------MAIN--------------------------------------//
public static void main (String args[])
{
Nodo head=new Nodo(Integer.parseInt(JOptionPane.showInputDialog("Inserisci il valore della testa")));
Lista y=new Lista(head);
Nodo aux = head;
for(int i=0; i<4 ; i++)
{
aux.setNext( new Nodo(Integer.parseInt(JOptionPane.showInputDialog("Inserisci il valore del "+(i+1)+"° nodo"))));
aux = aux.getNext();
}
rewind(y).Stampa();
}

Al solito, se qualcuno si accorge che nel codice vi sono imperfezioni (utili a tutti) , può segnalarlo.
Grazie.
« Last Edit: 10-04-2009, 15:09:02 by gam » Logged
TheSpecialOne
Apprendista Forumista
**
Offline Offline

Posts: 232



« Reply #2 on: 10-04-2009, 15:18:40 »

Ciao, io sono riuscito a trovare la soluzione al problema univ.
Il codice è commentato in modo che si possa capire quello che viene fatto.
Eccola: *mi sono accorto che c'è un prob.

Code:
import javax.swing.*;
public class ordina
{
public static Lista rewind(Lista L)
{
Nodo aux=L.getHead(); //salvo in una variabile Nodo il valore della testa

//CASO BASE
if(aux.getNext()==null)
return L; //la ricerca termina quando la lista si esaurisce
//PASSO INDUTTIVO
else
{
if( aux.getInfo()%2==0 && (aux.getNext()).getInfo()%2==1 ) //controllo che il primo valore sia pari e il successivo dispari
{
//------------SWAP-----------//
int tmp=aux.getInfo();
aux.setInfo( (aux.getNext()).getInfo() );
(aux.getNext()).setInfo(tmp);
//------------FINE-----------//

//collego ricorsivamente il puntatore della testa che risulta essere "aux", con il metodo rewind che prende la stessa lista la cui testa parte però dal nodo successivo alla testa
aux.setNext( rewind(new Lista(aux.getNext())).getHead() );
return new Lista(aux);
}
else
{
//idem sopra
aux.setNext( rewind(new Lista(aux.getNext())).getHead() );
return new Lista(aux);
}
}
}

//------------------------------------MAIN--------------------------------------//
public static void main (String args[])
{
Nodo head=new Nodo(Integer.parseInt(JOptionPane.showInputDialog("Inserisci il valore della testa")));
Lista y=new Lista(head);
Nodo aux = head;
for(int i=0; i<4 ; i++)
{
aux.setNext( new Nodo(Integer.parseInt(JOptionPane.showInputDialog("Inserisci il valore del "+(i+1)+"° nodo"))));
aux = aux.getNext();
}
rewind(y).Stampa();
}

Al solito, se qualcuno si accorge che nel codice vi sono imperfezioni (utili a tutti) , può segnalarlo.
Grazie.

grazie x l'aiuto, magari tramite questo codice riesco un po a capire come potere svolgere questo tipo di esercizi, dato che non ci sto capendo niente al momento!
Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #3 on: 10-04-2009, 15:23:26 »

Se guardando il codice magari trovi il problema che da, mi faresti un favore. il risultato che da con i numeri che da il prof funziona ma inganna
Logged
Zeridos
Forumista
***
Offline Offline

Gender: Male
Posts: 705


The Original


« Reply #4 on: 10-04-2009, 18:49:22 »

Io l'ho risolto (se così si puo' dire.. funziona ma il metodo che ho usato non mi piace) così:

Code:
public static LList ordina(LList x,int contatore,LList ordinata)
{
if(contatore==0)
{
ordinata.concat(x);
}
else
{
if((x.getHead().getInfo()%2)==1)
ordinata.insertTail(x.getHead().getInfo());
else
x.insertTail(x.getHead().getInfo());
x.deleteHead();
ordina(x,contatore-1,ordinata);
}
return ordinata;
}

main:
Code:
public static void main(String [] args)
{

LList test = new LList();
for(int i=2;i<10;i+=1)  //creo la lista con numeri non in ordine di tipo diverso
{
test.insertTail(i-1);
test.insertTail(i); 
test.insertTail(i-2);
test.insertTail(i+3);
}

test.stampa();  //ho modificato lo stampa su una sola righa, separando i nodi da uno spazio
System.out.println(""); //per poterlo confrontare + facilmente con il risultato
test=ordina(test,test.getSize(),new LList());
test.stampa();

}

Spiegando a parole, il metodo a ogni sua chiamata controlla se la testa e' dispari o pari, se pari la copia in coda e cancella la testa, se dispari la inserisce in coda alla lista finale e cancella la testa dalla lista originaria.
Alla fine si avranno i numeri dispari in ordine nella lista finale e la lista originaria conterra' solo i nodi pari quindi li concateno e restituisco la lista finale ordinata cm vuole il testo.
Il risultato si puo' prendere o tramite il return della funzione o passando una lista "finale" vuota creata apposta.

Ripeto... funziona... ma non mi piace molto. Se avete qualche consiglio dite pure.

Ciauz

P.S. Se vi serve posto le classi LList e ListNode che ho usato.
Logged

I love penguins, dead ones...
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #5 on: 11-04-2009, 08:54:18 »

io ho fatto l'esercizio attenendomi a quello che era richiesto. In questo caso al metodo che ho creato, ho dato in input un solo parametro quale la Lista.
Se però il prof. accetta metodi che possono prendere in input anche parametri utili al corretto funzionamento dell'esercizio, ben venga!!!
Logged
Zeridos
Forumista
***
Offline Offline

Gender: Male
Posts: 705


The Original


« Reply #6 on: 11-04-2009, 09:46:26 »

Hai raggione non avevo letto bene il testo 
Logged

I love penguins, dead ones...
Zeridos
Forumista
***
Offline Offline

Gender: Male
Posts: 705


The Original


« Reply #7 on: 11-04-2009, 12:38:46 »

Cmq ho trovato il problema del tuo codice, non gestisci il caso in cui sono entrambi pari. In questo caso semplicemente va avanti a fare i controlli senza spostare il primo elemento che e' pari.
Es.
 3 2 8 1 4
da te diventa:
3 2 1 8 4


EDIT: uhm.. doveva editare quello sopra... vabbe  boh
« Last Edit: 11-04-2009, 12:40:42 by Zeridos » Logged

I love penguins, dead ones...
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #8 on: 11-04-2009, 15:09:20 »

questi sono gli unici che sono riuscita a fare per ora...con gli interi è più facile..appena ci sono in mezzo strutture dati o oggetti vari...la cosa si complica...
Code:
/*Fornire un metodo ricorsivo per il calcolo del prodotto di due numeri positivi
(n ed m). L'algoritmo deve fare uso solo di addizione e sottrazione.*/
public class Es5ricorsione
{
public static int prodotto(int n,int m) throws IllegalArgumentException
{
if(n<0||m<0)
throw new IllegalArgumentException();
if(n==0||m==0)
return 0;
else
return n+prodotto(n,m-1);
}
public static void main (String[] args)
{
try
{System.out.println(prodotto(0,-1));}
catch(IllegalArgumentException e)
{
System.out.println("I numeri non possono essere negativi");
}
}
}

Code:
/*Scrivere un metodo ricorsivo per trovare l'elemento massimo in un array A di n elementi*/
public class Es4ricorsione
{
public static int max(int[] A)
{
if (A.length==0)
throw new IllegalArgumentException();
if(A.length==1)
return A[0];
else
{
int[] B=new int[A.length-1];
System.arraycopy(A,1,B,0,A.length-1);
return Math.max(A[0],max(B));
}
}
public static void main (String[] args)
{
int[] a={7,-68,-74,-83,6,128,23,0,-62};
try
{System.out.println(max(a));}
catch(IllegalArgumentException e)
{
System.out.println("L'array deve avere almeno un elemento");
}
}
}
« Last Edit: 11-04-2009, 15:30:41 by Vivynz » Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Zeridos
Forumista
***
Offline Offline

Gender: Male
Posts: 705


The Original


« Reply #9 on: 11-04-2009, 17:24:39 »

Ok ora penso di essermici avvicinato un po' di +:
Code:
public static ListNode riordina(LList x)
{
if(pro==0)
return x.getHead();
else
{
if(((x.getHead().getInfo())%2)==0)
{
x.insertTail(x.getHead().getInfo());
x.deleteHead();
pro--;
riordina(x);
}
else
{
pro--;
x.getHead().setNext(riordina(new LList(x.getHead().getNext())));
}
return x.getHead();
}

}
main:
Code:
public static int pro;
public static void main(String [] args)
{
LList test = new LList();
for(int i=2;i<10;i+=1)
{
test.insertTail(i-1);
test.insertTail(i);
test.insertTail(i-2);
test.insertTail(i+3);
}

pro=test.getSize();
test.stampa();
System.out.println("");
riordina(test);
test.stampa();
}
OUTPUT:
1 2 0 5 2 3 1 6 3 4 2 7 4 5 3 8 5 6 4 9 6 7 5 10 7 8 6 11 8 9 7 12  //lista originaria
1 5 3 1 3 7 5 3 5 9 7 5 7 11 9 7 2 0 2 6 4 2 4 8 6 4 6 10 8 6 8 12  //lista riordinata

Stavolta vuole solo una lista e modifica quella stessa così come vuole il testo.
L'unica cosa che non sono riuscito ad eliminare e' il contatore che ho messo come variabile globale. (sarebbe "pro")
Ci devo studiare ancora un po', funziona ma continua a non piacermi. (devo riuscire ad eliminare il contatore)

Ciauz

P.S. Come prima, se serve vi posto anche LList e ListNode.
« Last Edit: 11-04-2009, 17:26:41 by Zeridos » Logged

I love penguins, dead ones...
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #10 on: 11-04-2009, 17:33:34 »

ecco io ho un probl simile...mi serve qualcosa che sia fisso al di fuori di tutte le chiamate ricorsive..ma non va 
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Zeridos
Forumista
***
Offline Offline

Gender: Male
Posts: 705


The Original


« Reply #11 on: 12-04-2009, 10:36:53 »

EDIT: Ho notato che c'e' un'imprecisione dovuta all'ultima cifra (se dispari o pari).
Appena correggo riedito.

Ciauz

« Last Edit: 12-04-2009, 16:58:39 by Zeridos » Logged

I love penguins, dead ones...
francesco89b
Apprendista Forumista
**
Offline Offline

Posts: 169



« Reply #12 on: 13-04-2009, 18:34:03 »

scusate voi che siete sicuramente più informati di me, ma se metto un metodo in overload che si piaglia un solo parametro e poi ne aggiunge qualche altro e lo passa all'altro metodo è barare?

Logged

Ogni mia affermazione è sempre da considerarsi con un ampio margine di errore X0
Aigor
Forumista Esperto
****
Offline Offline

Gender: Male
Posts: 1.184


"Il destino non è una catena, ma un volo."[A.B.]


« Reply #13 on: 13-04-2009, 18:36:31 »


No non è barare, anzi può essere estremamente utile.
A mio parere è forse l'unico modo per eliminare quella variabile globale.
Logged

"Era d'altronde uno di quegli uomini che amano assistere alla propria vita, ritenendo impropria qualsiasi ambizione a viverla.
Si sarà notato che essi osservano il loro destino nel modo in cui, i più, sono soliti osservare una giornata di pioggia." - Seta,Baricco
Zeridos
Forumista
***
Offline Offline

Gender: Male
Posts: 705


The Original


« Reply #14 on: 14-04-2009, 14:12:40 »

Ok giusto per fugare dubbi ho chiesto al professore oggi dopo lezione (tra l'altro oggi ha parlato proprio di questo esercizio  ) e in pratica potevamo usare variabili globali, due liste, funzioni che richiamano funzioni con + parametri... in pratica tutto cio' che poteva servirci per il corretto svolgimento del compito.

In + ha sottolineato come non ci fosse scritto che i numeri pari dovessere essere necessariamente in ordine, basta che lo siano i numeri dispari (si nell'esempio anche i pari era in ordine, ma era un opzional).

Ciauz

P.S. Se volete riposto la mia ultima soluzione senza contatore e variabili esterne, solo con la lista da modificare. L'unico problema era che l'ultimo carattere (se pari) non veniva messo in ordine tra i caratteri pari, cosa ora ammessa  ok

EDIT: Aggiungo che giovedì vedremo anche altri esercizi.
« Last Edit: 14-04-2009, 14:31:44 by Zeridos » Logged

I love penguins, dead ones...
Pages: [1] 2   Go Up
Print
Jump to: