Esercizi di Gara della X edizione (Rotary)

---

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: Ababa NO [Punti 10]. Scrivere un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa composta di A e B, lasci sul nastro la scritta SI se la sequenza conteneva un numero uguale di A e B, NO in caso contrario. Esempi:

NASTRO INIZIALE	NASTRO FINALE
AAABABBB	SI
ABABA	NO
AB	SI
A	NO

Esercizio 2: A Tempo di Euro [Punti 25]. Scrivere un programma per macchina di Turing che, ricevuto in ingresso un numero decimale che indica una quantità monetaria espressa in centesimi di Euro, lasci sul nastro la stessa cifra, in Euro, con la virgola di separazione per i centesimi (sempre due cifre) e il punto per le migliaia. Esempi:

NASTRO INIZIALE	NASTRO FINALE
14530	145,30
219248	2.192,48
12	0,12
5	0,05
0	0,00

Esercizio 3: Multipli di 5 [Punti 10]. Scrivere un programma per macchina di Turing che, ricevuto in ingresso un numero decimale, lasci sul nastro SI se il numero in questione e' un multiplo di 5, NO altrimenti.

NASTRO INIZIALE	NASTRO FINALE
3840	SI
5	SI
17	NO
3729	NO

Esercizio 4: Conversione Araba [Punti 25]. Scrivere un programma per la macchina di Turing che, ricevuto in ingresso sul nastro un numero compreso tra 1 e 30, lasci sul nastro lo stesso numero scritto in notazione latina.

NASTRO INIZIALE	NASTRO FINALE
19	IX
1	I
24	XXIV
5	V

Esercizio 5: Conversione Latina [Punti 30]. Scrivere un programma per macchina di Turing che, ricevuta in ingresso sul nastro un numero scritto in notazione romana, lascia sul nastro il corrispondente in notazione decimale. Si assuma che il numero sia compreso fra 1 e 30 (si noti che i Romani non conoscevano lo 0). Esempi:

NASTRO INIZIALE	NASTRO FINALE
XI	11
IX	9
II	2
IXX	19
V	5

Esercizio 6: Duplinverti [Punti 15]. Scrivere un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull'alfabeto {A, B, C}, restituisca la stessa stringa, seguita da una copia invertita della stringa stessa. Alcuni esempi:

NASTRO INIZIALE	NASTRO FINALE
ABC	ABCCBA
A	AA
ACCA	ACCAACCA
ABBAC	ABBACCABBA

Esercizio 7: Duplinvertita [Punti 20]. Scrivere un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull'alfabeto {A, B, C}, lasci sul nastro la stringa SI se la stringa in ingresso era duplinvertita, cioè composta da una sottostringa seguita da una copia invertita della stessa sottostringa. Il programma deve lasciare sul nastro la stringa NO se la stringa in input non era duplinvertita.

NASTRO INIZIALE	NASTRO FINALE
ABCCBA	SI
ABCACBA	NO
BACCA	NO
A	NO
AA	SI
abccccbaabaabaabccccba	SI

Esercizio 8: Addizione araba [Punti 30]. Scrivere un programma per macchina di Turing che, ricevuta in ingresso una addizione araba, lasci sul nastro il corrispondente risultato. Una addizione araba e' costituita da due numeri in notazione decimale, separati dal simbolo "+".

NASTRO INIZIALE	NASTRO FINALE
248+418	666
234987+54298742	54533729
0+1	1
0+0	0
9+9	18

Esercizio 9: Poesia monovocalica [Punti 25]. Scrivere un programma per macchina di Turing che, ricevuta in ingresso una stringa sull'alfabeto A..Z, lasci sul nastro la stringa SI se la stringa conteneva una sola vocale (anche in istanze multiple), NO altrimenti.

NASTRO INIZIALE	NASTRO FINALE
PERCHELEGGERESEMPRELESTESSEE	SI
CINQUEVOCALINATURACIHADATO	NO
FENDERELETENEBREDELLETESTE	SI
APPARECOMPITOASSAIINGRATO	NO
SOGNOSONNOCONTORTO	SI
MICRESCEINPETTOUNDUBBIO	NO
SONOSORDOOSONOMORTO	SI
ARRGGHH	SI

Esercizio 10: Frequenza delle vocali [Punti 35]. Scrivere un programma per macchina di Turing che, ricevuta in ingresso una stringa sull'alfabeto A..Z, lasci sul nastro una tabella che riporti, per ogni vocale, il relativo numero di occorrenze nella stringa in ingresso. Il risultato lasciato sul nastro deve essere formattato come mostrato negli esempi. Si assuma che la stringa in ingresso potrà contenere al più 9 istanze di ciascuna vocale.

NASTRO INIZIALE	NASTRO FINALE
NELMEZZODELCAMMINDINOSTRAVITAMIRITROVAIPERUNASELVAOSCURA	a=7 e=5 i=6
LETTERESEGRETE	a=0 e=6 i=0 o=0 u=0
LOSOSOGNOTROPPOSOTTOLSD	a=0 e=0 i=0 o=8 u=0
AIUOLE	a=1 e=1 i=1 o=1 u=1