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
 
 
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