Laboratorio 6

Esercizio 0

Questionario di autovalutazione: risposte e statistiche

Esercizio 1

Argomento: ricorsione semplice, argomenti sulla riga dei comandi

Scrivere una classe eseguibile RecStringReverser capace di invertire una stringa in modo ricorsivo (ad es., l'inverso della stringa "Hello" e` la stringa "olleH"). Esempio di uso:
$java RecStringReverser Hello
Suggerimento: scrivere un metodo statico ricorsivo reverseString che realizza l'algoritmo ricorsivo di inversione di stringhe, poi scrivere un metodo main che realizza il comportamento sopra specificato invocando il metodo reverseString. Il metodo main non deve eseguire alcuna azione se non riceve parametri.


Soluzione6_1


Esercizio 2

Argomento: ricorsione semplice, argomenti sulla riga di comando, lancio/cattura di eccezioni

Scrivere una classe eseguibile avente il funzionamento seguente: Si scriva un metodo statico ausiliario, recursiveMCD, invocato dal metodo main per realizzare il comportamento sopra indicato. Tale metodo calcola ricorsivamente il massimo comun divisore (MCD) fra due numeri interi positivi m ed n (con m>n), ricevuti come parametri espliciti, usando il ben noto Algoritmo di Euclide: Si confronti questa definizione ricorsiva dell'algoritmo di Euclide con la definizione iterativa data nell'esercizio 3 del laboratorio 3, e si verifichi che le due sono equivalenti

Soluzione6_2


Esercizio 3

Argomento: ricorsione doppia, rilevazione delle prestazioni

Scrivere una classe eseguibile il cui metodo main Suggerimenti:
  1. Ripassare quanto detto a lezione sulla serie di Fibonacci. In particolare si ricorda che la serie di Fibonacci e` cosi` definita:
  2. Si consiglia di scrivere due metodi ausiliari statici, recursiveFib e iterativeFib, invocati dal metodo main per realizzare il comportamento sopra indicato. Entrambi i metodi ricevono un parametro n di tipo int e (dopo aver verificato la pre-condizione che n non sia negativo) restituiscono un valore di tipo long che rappresenta l'n-esimo numero Fib(n) nella sequenza di Fibonacci.
  3. Osservare il rapidissimo aumento del tempo di calcolo richiesto dal metodo recursiveFib all'aumentare di n (dipendentemente dalla velocita` del calcolatore, il calcolo ricorsivo non e` piu` "istantaneo" a partire da valori di n superiori a 30.


Soluzione6_3


Esercizio 4

Argomento: ricorsione semplice, argomenti sulla riga di comando

Scrivere una classe eseguibile RecSubstringGenerator capace di generare tutte le sottostringhe di una stringa. Ad esempio, l'insieme delle sottostringhe della stringa "abc" e` il seguente: {a, ab, abc, b, bc, c}. Esempio di uso:
$java RecSubstringGenerator abc
Suggerimento: il problema presenta analogie con il problema della generazione delle permutazioni di una stringa, che abbiamo visto a lezione. In questo caso costruire l'insieme delle sottostringhe come unione tra:
  1. l'insieme delle sottostringhe che contengono il primo carattere (n sottostringhe, se n e` il numero di caratteri della stringa; ad es. se la stringa e` "Roma" gli elementi di questo sottoinsieme sono: "R" "Ro" "Rom" "Roma") e
  2. l'insieme delle sottostringhe che non contengono il primo carattere (ovvero le sottostringhe della stringa privata del primo carattere; ad es. se la stringa e` "Roma" gli elementi di questo sottoinsieme sono le sottostringhe della stringa "oma").


Soluzione6_4


Esercizio 5

Argomento: ricorsione semplice, argomenti sulla riga di comando

Scrivere una classe eseguibile che verifica se una stringa, fornita come parametro sulla riga di comando, e` una palindrome. Si ricordi che una stringa e` una palindrome se e` composta da una sequenza di caratteri (anche non alfabetici) che possa essere letta allo stesso identico modo anche al contrario (es. "radar", "anna", "inni", "xyz%u%zyx").
ATTENZIONE: Il programma NON deve avere alcun costrutto iterativo (cioe` non deve avere cicli).
Verificare il corretto funzionamento del programma con: Approfondimento: il programma puo` essere esteso in maniera tale da verificare se intere frasi sono palindrome, usando le seguenti regole: Secondo queste regole, la frase "Madam, I'm Adam!" e` una palindrome (ovvero e` la piu` antica palindrome del mondo...). Per fornire come parametro sulla riga di comando una stringa che comprende anche separatori bisogna racchiuderla tra virgolette.
Per questo approfondimento si consultino anche i Consigli Pratici 12.1 del libro di testo.

Soluzione6_5


Esercizio 6

Argomento: array riempiti solo in parte, ordinamento di array, ricerca binaria in un array

Studiare la classe ArrayAlgs vista a lezione. Studiare con attenzione gli algoritmi di ordinamento e ricerca.
Approfondimento: testare gli algoritmi di ordinamento e ricerca scrivendo una classe di collaudo ArrayAlgsTester che

Soluzione6_6


Esercizio 7

Argomento: array riempiti solo in parte, ordinamento di array, ricerca binaria in un array

Scrivere la classe SortedArray, la cui interfaccia pubblica e` documentata qui, in grado di memorizzare numeri interi mantenendo l'insieme ordinato.
Scrivere successivamente una classe di collaudo IntSorter che:
  1. riceve due parametri dalla riga di comando: un numero intero N ed una stringa
  2. genera N numeri casuali fra 1 e N compresi (N e` il primo parametro passato dalla riga di comando) memorizzandoli in un oggetto di tipo SortedArray
  3. calcola la media dei valori dell'oggetto SortedArray e la invia a standard output
  4. esegue il seguente ciclo
  5. esce dal suddetto ciclo quando viene inserita la stringa "Q"
  6. memorizza in ordine decrescente i valori dell'oggetto SortedArray in un file di testo (il cui nome e` stato passato come secondo parametro dalla riga di comando), 10 numeri per riga in colonne equispaziate
Esempio di uso:
$java IntSorter < dimensione > < nomefile >


Soluzione6_7