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