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
|