Edizione X – Rotary Club

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