Pages: [1]   Go Down
Print
Author Topic: Soluzione dell'esame di giorno 10 febbraio 2011  (Read 1024 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Simone Faro
Moderator
Matricola
*****
Offline Offline

Gender: Male
Posts: 67


WWW
« on: 10-02-2011, 17:38:20 »

Di seguito propongo una possibile (semplice) soluzione all'esame di giorno 10 febbraio 2011.
Ho inserito alcuni commenti per rendere più chiaro il procedimento.
Non è stata curata la gestione degli errori. Il codice è lungo circa 70 riga (esclusi i commenti)

Code:
import java.io.*;
import java.util.*;


final class QuickSortRecursiveCall {
// Questa classe non contiene metodi setter. Dichiarata come final per evitarne l'estensione
private int[] array; // rappresenta l'array passato come input
private final int leftEnd, rightEnd; // indice di inizio e fine della porzione di array coinvolta nella chiamata
private final int depth; // profondita' della chimata ricorsiva
private final QuickSortRecursiveCall leftSideCall, rightSideCall;

public QuickSortRecursiveCall(int[] A, int i, int j, int depth) {
array = new int[A.length];
int[] tmp = new int[A.length];
for(int k=0; k<A.length; k++) array[k]=tmp[k]=A[k]; // creo una copia difensiva dell'array
leftEnd = i;
rightEnd = j;
this.depth = depth;
// poiche' l'oggetto e' immutabile devo costruire le sottochiamate ricorsive
// prima di terminare la costruzione della chiamata principale
if ( i<j )  { // in questo caso sono necessarie due sottochiamate ricorsive
int q = partition(tmp,i,j); //qui l'array viene modificato in base alla partizione
leftSideCall   = new QuickSortRecursiveCall(tmp,i,q,depth+1);
rightSideCall = new QuickSortRecursiveCall(tmp,q+1,j,depth+1);
}
else  leftSideCall = rightSideCall = null;
}

public String toString() {
String str = "";
for(int i=leftEnd; i<=rightEnd; i++)  str += array[i]+" ";
return str;
}

private int partition(int[] A, int p, int r) {
int x = A[p];
int i = p - 1;
int j = r + 1;
while(true)  {
do j = j - 1;  while (A[j] > x);
do i = i + 1; while (A[i] < x);
if (i < j) {
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
else return j;
}
}
int getSize() {return rightEnd-leftEnd+1;}
QuickSortRecursiveCall getLeftSideCall()  {return leftSideCall;}
QuickSortRecursiveCall getRightSideCall()  {return rightSideCall;}
int[] getArray() {
int[] A = new int[array.length];
for(int k=0; k<array.length; k++) A[k]=array[k];
return A; // ritorno una copia difensiva dell'array
}
}


public class esame  {
    public static void main( String args[] ) throws IOException {
Scanner input = new Scanner(new File("input.txt"));
PrintWriter output = new PrintWriter("output.txt");

int numero = input.nextInt(); // numero di elementi dell'array
int[] A = new int[numero];
for(int i=0; i<numero; i++)  A[i] = input.nextInt();
QuickSortRecursiveCall  RC = new QuickSortRecursiveCall(A,0,numero-1,0);
InorderVisit(RC,output); // inizio la visita inorder e stampo solo le foglie
input.close();
output.close();
}

private static void InorderVisit(QuickSortRecursiveCall rc, PrintWriter out) {
if(rc==null) return;
InorderVisit(rc.getLeftSideCall(),out);
if(rc.getSize()==1) out.write(rc.toString());
InorderVisit(rc.getRightSideCall(),out);
}

}
Logged

________________________________
Simone Faro, Ph.D.
Dipartimento di Matematica e Informatica
Università di Catania
________________________________
nelson
Apprendista Forumista
**
Offline Offline

Posts: 109



« Reply #1 on: 10-02-2011, 17:55:53 »

Io non ce la faccio piu...............
« Last Edit: 10-02-2011, 17:57:39 by nelson » Logged
equivoco
Matricola
*
Offline Offline

Posts: 69


« Reply #2 on: 10-02-2011, 18:20:19 »

complimenti al signor messina l'unico che è passato con 18...
 testate
Logged
Grillo
Apprendista Forumista
**
Offline Offline

Posts: 219


« Reply #3 on: 15-02-2011, 11:35:15 »

Signor Messina com'è andato l'orale? E' riuscito a passare?
Cosa ti ha chiesto il prof.
Logged
Pages: [1]   Go Up
Print
Jump to: