Algoritmi e strutture dati



Scaricare 10.94 Kb.
17.11.2017
Dimensione del file10.94 Kb.

Algoritmi e strutture dati
Esercitazione in laboratorio del 16 maggio 2002


  1. Accendere il PC e collegarsi alla sessione di Windows 2000




  1. Verificare la presenza del supporto minimo per Java

    1. jdk1.2 o successivo

    2. JCreator Lite v. 2.00




  1. Far girare una piccola applicazione di prova (ad es.: stampa su console di “Ciao mondo!”) per assicurarsi che la macchina virtuale Java funzioni correttamente




  1. Procurarsi la classe ConsoleReader (file ConsoleReader.java, disponibile sul sito Web del corso all’indirizzo http://www.dis.uniroma1.it/~damore/asd/listati/ConsoleReader/ConsoleReader.java.html)

    1. Trattasi di una classe per agevolare l’input da console, distribuita assieme al volume: C. S. Horstmann. Concetti di informatica e fondamenti di Java 2. Apogeo, 2000.

    2. Esaminarne la documentazione nonché i metodi disponibili

      1. readInt(), readDouble(), readLine() ecc.

      2. esempio di uso (lettura di una stringa da console):
        ConsoleReader lettore = new ConsoleReader(System.in);
        String s = letore.readLine();

      3. Attenzione: la lettura di caratteri a 8 bit non funziona correttamente!

    3. Modificare la semplice applicazione di prova affinché utilizzi la classe ConsoleReader (ad es.: stampa di n volte “Ciao mondo!”, con n letto da tastiera)




  1. Realizzare una semplice applicazione che, utilizzando un opportuno albero binario, consenta il gioco “Indovina l’animale”, in cui l’applicazione, tramite domande poste all’utente, tenta di indovinare il nome di un animale scelto dall’utente. L’applicazione (da console) utilizza un albero binario nei cui nodi interni sono memorizzate domande che essa potrà porre all’utente, sfruttandone le risposte (sì o no) per discendere nell’albero ed ottenere una nuova domanda da porre all’utente (ad es., per risposta “sì” scendere nel sottoalbero sinistro e per risposta “no” scendere in quello destro).

In ciascuna foglia dell’albero è invece memorizzato il nome di un animale individuato dal percorso (univoco) radice – foglia, in maniera che l’animale sia caratterizzato dalle domande/risposte presenti in tale percorso.

Esempio:


Q
uando, durante il gioco, l’applicazione giunge ad una foglia, essa propone il nome di animale ivi memorizzato. Se la risposta non è corretta, l’applicazione si arrende e:

  • chiede all’utente il nome dell’animale che non è riuscita ad indovinare

  • chiede all’utente la formulazione di una domanda che consenta di distinguere l’animale proposto da quello da indovinare.

Se, ad esempio, l’applicazione giunge alla foglia “cane”, ma la risposta esatta era “gatto”, l’applicazione chiede una domanda utilizzabile per distinguere un gatto da un cane: l’utente potrebbe inserire il testo “miagola”. In tal caso l’applicazione dovrà modificare l’albero come segue:
I
n pratica, l’algoritmo per l’inserimento di nuove informazioni esegue i seguenti passi:

  1. “stacca” la foglia

  2. inserisce al suo posto un nodo contenente la nuova domanda

  3. crea un nuovo nodo corrispondente alla risposta “sì” e contenente l’animale che non era riuscito ad indovinare; tale nodo diviene figlio “sì” del nodo domanda

  4. collega la foglia (scollegata al punto a.) al nodo inserito al punto b., rendendola figlio “no” del nodo domanda

Si suggerisce di realizzare due classi ANode e ATree: la prima istanzia nodi, la seconda istanzia alberi. Ė opportuno realizzare anche una classe TestAnimali contenente il metodo main per l’avvio del programma. Coloro che non si sentano in grado di risolvere l’esercizio possono visualizzare uno schema astratto delle prime due classi, sebbene ciò sia altamente sconsigliato, cliccando sui collegamenti AbstractANode e AbstractATree.




  1. Discutere la soluzione costruita e confrontare l’albero implementato con un albero binario di ricerca: quali le differenze e quali le affinità?




©astratto.info 2017
invia messaggio

    Pagina principale