Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 14.Esercizio di Laboratorio. Gioco su alberi


GIOCO TOM & JERRY

Si implementi un gioco tra due giocatori (Tom e Jerry) realizzato su alberi binari di ricerca di interi nel modo seguente:

  • Tom e Jerry hanno a disposizione un albero binario di ricerca di interi a testa.
  • I due muovo a turni. Inizia Jerry a muovere.
  • Scopo del gioco per TOM: acciuffare JERRY. Il che si concretizza per TOM nel trovarsi in un nodo il cui valore è identico a quello in cui si trova Jerry.

Strategia del Gioco

  • Ogni giocatore può soltanto muovere da padre a figlio e non viceversa.
  • Se un giocatore raggiunge una cella che ha un solo nodo figlio può soltanto muovere verso quel nodo figlio.
  • Se un giocatore raggiunge un nodo che ha due figli allora si comporta come segue:
    • Se Jerry si trova in un nodo con valore “maggiore” a quello di Tom, Jerry cerca di scappare da Tom muovendo a destra. Se il nodo ha invece valore minore di quello di Tom, allora Jerry muove a sinistra
    • Tom farà l’opposto cercando di avvicinarsi a Jerry. In pratica, se Tom si trova in un nodo con valore “maggiore” a quello di Jerry, Tom muove a sinistra. Se invece è “minore”, allora muove a destra.
  • Se un giocatore raggiunge una foglia non può più muovere.

Condizioni di terminazione

  • Se Tom vince (entrambi i giocatori sono sullo stesso numero), si provvede a rimuovere il nodo dall’albero di Jerry e il gioco termina.
  • Se entrambi i giocatori raggiungono una foglia e Tom non ha vinto, si trasferisce la foglia raggiunta da Jerry nell’albero di Tom e si riparte con il gioco.
  • Quest’ultima operazione è ammessa per al più un numero prefissato di volte.
  • Si consideri per semplicità che tutti i nodi dell’albero abbiano valore differente. Per cui, l’operazione di inserimento nell’albero di Tom non ha “effetto” se il nodo è già presente.

IMPLEMENTAZIONE

Scrivere in linguaggio C un menù a scelta multipla che permetta le seguenti funzioni:

  • Riempimento (casuale o manuale) dei due alberi Tom e Jerry. Per semplicità si definiscano due constanti RANGE e TOT, e di riempire l’albero con TOT nodi presi nel range 1… RANGE
  • Simulazione del gioco. Tale funzione prende in input i due alberi e restituisce i due alberi modificati al termine del gioco e riporta quanti turni sono stati giocati (si supponga che al più possono essere giocati NUM turni)
  • Stampa in ordine del contenuto degli alberi prima e dopo il gioco.

Si discuta infine la complessità di tutte le funzioni implementate

Consegna

L’esercizio completo va consegnato via mail al tutor entro 4 giorni lavorativi

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion