Accesso

Cherubino     Gara nazionale di programmazione della
Macchina di Turing
 
 

 

Esercizi di Gara della XIII edizione


AVVISI:

·       Se non specificato altrimenti negli esercizi, le sequenze iniziali su nastro si intendono non vuote, ovvero contenenti almeno un simbolo.

·          Per numero decimale si intende un numero positivo o nullo rappresentato con le cifre 0, 1, 2, ..., 9, senza zeri iniziali non significativi; per esempio 0 e 19 sono numeri validi, mentre 0032 deve essere scritto come 32.

·          Nel fornire le soluzioni, ricordarsi di pulire il nastro finale da ogni simbolo che non costituisca la risposta!

·          Ogni volta che si salva la soluzione di un esercizio con il simulatore della macchina di Turing, il “timestamp” dell’esercizio viene aggiornato con il tempo trascorso fino a quel momento.

Esercizio 1: La morra cinese [Punti 3]. Nel gioco della “Morra cinese” (anche nota come Carta-Forbice-Pietra, Roshambo, Rochambeau, Row-Sham-Bow, Ick-Ack-Ock, Janken, Mora, Gawi-Bawi-Bo, JanKenPon, Ca-Chi-Pun, Farkle, Ken Ken Pa, o Kai Bai Bo), due giocatori scelgono ciascuno un simbolo fra Carta, Forbice, Pietra (di solito, indicandolo in contemporanea con un gesto della mano). Forbice vince su Carta, Carta vince su Pietra, Pietra vince su Forbice. Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro una giocata composta da due simboli sull'alfabeto {C, F, P}, lasci in uscita “1” se vince il primo giocatore (ovvero, se il primo simbolo vince sul secondo), “2” se vince il secondo giocatore (ovvero, se il secondo simbolo vince sul primo), “0” altrimenti.

NASTRO INIZIALE

NASTRO FINALE

CF

2

FC

1

PP

0

FP

2

PC

2

Esercizio 2: Pari e Dispari [Punti 4]. Nel gioco “Pari e Dispari”, due giocatori puntano uno su Pari, l'altro su Dispari, e quindi scelgono ciascuno un numero compreso fra 0 e 5 (di solito, indicandolo in contemporanea con le dita aperte di una mano). Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro i numeri scelti dai due concorrenti, lasci in uscita P se la somma è pari, D se la somma è dispari.

NASTRO INIZIALE

NASTRO FINALE

40

P

00

P

53

P

14

D

Esercizio 3: Testa o croce [Punti 5]. Nel gioco “Testa o Croce”, due giocatori puntano uno su Testa, l'altro su Croce, e quindi lanciano una moneta un numero concordato di volte, scrivendo i risultati di ogni lancio sul nastro di una macchina di Turing. Vince il concorrente che ha puntato sul simbolo uscito più volte. Si scriva dunque un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull'alfabeto {T, C} rappresentante gli esiti dei lanci, lasci sul nastro T se sono uscite più teste, C se sono uscite più croci, P se la partita è patta (sono uscite cioè tante teste quante croci).

NASTRO INIZIALE

NASTRO FINALE

TTCTC

T

TCTCCTCCCTT

C

TC

P

CCTCTTCTTC

P

Esercizio 4: Il baro [Punti 7]. Un mazzo di carte napoletane contiene un totale di 40 carte, 10 per seme. Esistono quindi esattamente 4 carte, di diverso seme, per ogni valore; i valori sono i numeri dall'1 al 7, il Fante, il Cavallo e il Re. Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull'alfabeto {1, 2, 3, 4, 5, 6, 7, F, C, R}, dica se la stringa rappresenta una mano valida, ovvero se ogni valore compare al più 4 volte. In caso di mano valida, la macchina deve lasciare sul nastro “OK”, altrimenti “BARO”.

NASTRO INIZIALE

NASTRO FINALE

4457FR

OK

11112

OK

FCRFFR1F5F

BARO (ci sono cinque Fanti)

54R4C

OK

11111

BARO (ci sono cinque assi)

Un livello di Super Alan Bros

Esercizio 5: Super Alan Bros [Punti 9].  Nei videogiochi del genere platform, il personaggio controllato dal giocatore deve muoversi lungo un percorso, superando degli ostacoli di vario tipo, fino a raggiungere il premio finale del livello. In Super Alan Bros, il giocatore (A) si trova inizialmente a sinistra di una piattaforma, composta da tratti di terreno (.) e da tratti di staccionata (#). Il giocatore ha a disposizione solo due mosse: un passo verso destra (P), che lo porta nella successiva casella a destra, e un salto (S) che lo porta due caselle verso destra, “saltando” una casella. Poiché non è possibile camminare attraverso una staccionata, questi tratti possono solo essere saltati. Scopo del gioco è portare Alan nella posizione del tesoro (X), nel minor numero di mosse possibile. Si scriva un programma per macchina di Turing che, ricevuto sul nastro una stringa descrivente il livello nella situazione iniziale, lasci sul nastro la sequenza di mosse di lunghezza minima che porta Alan sul tesoro di fine livello, senza mai camminare attraverso staccionate. Alan ha un comportamento eager: tutte le volte che è possibile sia fare un passo che fare un salto (atterrando su terreno piano e senza superare il tesoro), Alan preferisce fare un salto. È garantito che il livello di input sia risolubile (per esempio, non ci saranno lunghi tratti di staccionata come ### che non possono essere superati con un salto).

NASTRO INIZIALE

NASTRO FINALE

A....X

SSP

A#..#X

SPS

A.#...#.#.X

PSSSSP

AX

P

A.X

S

A#.X

SP

A.#..#X

PSPS

Esercizio 6: Sette e mezzo [Punti 12]. Nel gioco “Sette e mezzo”, ciascun giocatore riceve inizialmente una carta da un mazzo napoletano, e può poi chiedere ulteriori carte a sua discrezione. Lo scopo è di avvicinarsi il più possibile al punteggio di 7 e mezzo (ogni carta vale il proprio punteggio nominale, mentre le figure Fante, Cavallo, Re valgono ciascuna mezzo punto), senza superarlo. Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro una stringa sull'alfabeto {1, 2, 3, 4, 5, 6, 7, F, C, R}, in cui ogni simbolo rappresenta una carta, dica se la giocata ha “sballato” superando il 7 e mezzo (lasciando sul nastro “KO”) o no (lasciando sul nastro “OK”).

NASTRO INIZIALE

NASTRO FINALE

34

OK (punteggio: 7)

145

KO (punteggio: 10)

4RF

OK (punteggio: 5)

2R4C

OK (punteggio: 7)

411

OK (punteggio: 6)

3R4

OK (punteggio: 7 e mezzo)

1R16

KO (punteggio: 8 e mezzo)

Esercizio 7: Dadi [Punti 15]. Le scommesse sui dadi hanno portato alla rovina più di un giocatore. In una variante di questo gioco, il giocatore punta una cifra a sua discrezione (strettamente maggiore di 0) su un numero fra 1 e 6; vengono quindi lanciati tre dadi a sei facce, e il giocatore incassa tante volte la posta quanti sono i dadi che hanno fornito il risultato su cui ha puntato. Se nessun dado ha dato quel risultato, il giocatore perde la posta. Si scriva un programma per macchina di Turing che, ricevuta sul nastro una sequenza composta da un numero rappresentante la puntata, un simbolo “/”, il valore su cui si è puntato, un altro simbolo “/” e infine i tre valori forniti dai dadi, lasci sul nastro la vincita da incassare.

NASTRO INIZIALE

NASTRO FINALE

100/6/326

100

100/6/114

0

20/1/141

40

1300/6/666

3900

8320/2/422

16640

8320/2/153

0

1/1/111

3

Esercizio 8: Black jack [Punti 17]. Il gioco “Black jack”, simile al Sette e mezzo, usa un mazzo di carte francesi, dall'asso al re (13 carte per seme), che indicheremo con {A, 2, 3, 4, 5, 6, 7, 8, 9, D, J, Q, K} (D=10, J=Jack, Q=Queen, K=King). Nel Black jack, l'asso vale 1 o 11 punti a scelta del giocatore; J, Q e K valgono 10 punti, le carte dal 2 al 10 valgono ciascuna il proprio valore nominale. Scopo del gioco è avvicinarsi il più possibile al 21, senza superarlo. Il punteggio più ambito è ovviamente il “black jack”, dato da asso (con valore 11) e una figura (con valore 10), per un totale di 21. Si scriva un programma per macchina di Turing che, data sul nastro di ingresso una serie di carte, lasci in uscita il valore numerico della giocata, scegliendo per l'asso il valore 1 o 11 a seconda di quale è più conveniente al giocatore; se il risultato supera il 21, il programma deve lasciare in uscita il solo simbolo S (superamento).

NASTRO INIZIALE

NASTRO FINALE

478

19

5Q

15

KK

20

KKA

21

A8

19

AJ

21

4QD

S

111AA

15

Esercizio 9: Scopa [Punti 25]. La “Scopa” si gioca con le carte napoletane. A turno, i giocatori scartano una carta, e se sono presenti a terra una o più carte per cui la somma del valore coincide con la carta scartata, il giocatore “prende” la propria carta e quelle che assommano lo stesso valore; in caso contrario, la carta viene lasciata a terra. Nella scopa, il Fante vale 8, il Cavallo vale 9, il Re vale 10, tutte le altre carte valgono il proprio valore nominale. Si scriva un programma per macchina di Turing che riceva sul nastro in ingresso l'elenco di carte a terra, seguito da una “/” e dalla carta giocata dal giocatore, e lasci sul nastro in uscita l'insieme delle carte a terra dopo la giocata (e l'eventuale presa). In caso siano possibili più prese, esse sono considerate tutte ugualmente accettabili.

NASTRO INIZIALE

NASTRO FINALE

436/4

36 (prende il 4)

165F/5

16F (prende il 5)

165F/7

5F (prende 6+1=7)

165F/3

165F3 (non prende)

113R2/7

R (prende 1+1+3+2=7)

46/R

  (prende 4+6=10, scopa!)

46/1

461 (non prende)

/F

F (non prende, cala un fante)

Esercizio 10: Il Tris [Punti 25]. Nel gioco del “Tris”, i concorrenti piazzano alternativamente un simbolo “O” (lettera O, non numero 0) o “X” in una casella di una scacchiera 3x3, spesso rappresentata come nelle figure sotto. Vince il concorrente che allinea tre simboli uguali in orizzontale, verticale o diagonale; il gioco continua, con mosse alternate, finché ci sono caselle libere sulla scacchiera. Si scriva un programma per macchina di Turing che, ricevuta sul nastro in ingresso una rappresentazione “per righe” di una scacchiera valida, in cui il simbolo “.” indica una casella vuota, lasci sul nastro il simbolo “X” o “O” se uno dei due giocatori ha vinto, “P” se è un pareggio, “C” se il gioco continua.

NASTRO INIZIALE

NASTRO FINALE

COMMENTO

X

O

X

 

X

O

 

 

O

XOX.XO..O

C

Nessun tris, partita continua

X

O

O

 

X

O

X

X

O

XOO.XOXXO

O

Il giocatore O ha fatto tris

X

O

X

X

X

O

O

X

O

XOXXXOOXO

P

Nessun tris, partita patta

X

 

O

 

X

O

 

 

X

X.O.XO..X

X

Il giocatore X ha fatto tris

 

 

 

 

 

 

 

 

 

.........

C

Nessun tris, partita continua

 

 

 

 

O

 

 

 

 

....O....

C

Nessun tris, partita continua

X

X

 

 

X

 

O

O

O

XX..X.OOO

O

Il giocatore O ha fatto tris

 

 I testi

  I GARA
  II GARA
  III GARA
  IV GARA
  V GARA
  VI GARA
  VII GARA
  VIII GARA
  IX GARA
  GARA ROTARY 2006
  X GARA
  XI GARA
  XII Gara
  XIII Gara
  XIV Gara
  XV Edizione
  XVI Edizione
  XVII Edizione
  XVIII Edizione
  XIX Edizione
(Altri collegamenti...)