Edizione patrocinata dal Rotary Club di Pisa e aperta alle scuole della provincia di Pisa.
Problema 1 – Ababa NO
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.
NASTRO INIZIALE | NASTRO FINALE |
AAABABBB | SI |
---|---|
ABABA | NO |
AB | SI |
A | NO |
Problema 2 – A tempo di Euro
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.
NASTRO INIZIALE | NASTRO FINALE |
14530 | 145,30 |
---|---|
219248 | 2.192,48 |
5 | 0,05 |
0 | 0,00 |
Problema 3 – Multipli di 5
Scrivere un programma per macchina di Turing che, ricevuto in ingresso un numero decimale, lasci sul nastro SI se il numero in questione è un multiplo di 5, NO altrimenti.
NASTRO INIZIALE | NASTRO FINALE |
3840 | SI |
---|---|
5 | SI |
17 | NO |
3729 | NO |
Problema 4 – Conversione araba
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 | XIX |
---|---|
1 | I |
24 | XXIV |
5 | V |
Problema 5 – Conversione latina
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).
NASTRO INIZIALE | NASTRO FINALE |
XI | 11 |
---|---|
IX | 9 |
II | 2 |
IXX | 19 |
V | 5 |
Problema 6 – Duplinverti
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.
NASTRO INIZIALE | NASTRO FINALE |
ABC | ABCCBA |
---|---|
A | AA |
ACCA | ACCAACCA |
ABBAC | ABBACCABBA |
Problema 7 – Duplinvertita
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 |
Problema 8 – Addizione araba
Scrivere un programma per macchina di Turing che, ricevuta in ingresso una addizione araba, lasci sul nastro il corrispondente risultato.
Una addizione araba è 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 |
Problema 9 – Poesia monovocalica
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 |
PERCHELEGGERESEMPRELESTESSE | SI |
---|---|
CINQUEVOCALINATURACIHADATO | NO |
FENDERELETENEBREDELLETESTE | SI |
APPARECOMPITOASSAIINGRATO | NO |
SOGNOSONNOCONTORTO | SI |
MICRESCEINPETTOUNDUBBIO | NO |
SONOSORDOOSONOMORTO | SI |
ARRGGHH | SI |
Problema 10 – Frequenza delle vocali
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 o=0 u=0 |
---|---|
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 |