Vai al contenuto

Edizione VII

Problema 1 – Musica, musica!

Tradizionalmente, le sette note della scala musicale vengono denominate in Italia do, re, mi, fa, sol, la, si.
Le stesse note nel sistema anglosassone vengono indicate con le prime lettere dell’alfabeto: A, B, … G, con

do C
re D
sol G
la A
si B

Si scriva un programma che, data una stringa di note nel sistema anglosassone, lasci sul nastro le note equivalenti nel sistema italiano, separate da un punto.

NASTRO INIZIALE NASTRO FINALE COMMENTO
CCDCFE DO.DO.RE.DO.FA.MI Tanti auguri
CDECCDECEFGEFG DO.RE.MI.DO.DO.RE.MI.DO.MI.FA.SOL.MI.FA.SOL Fra’ Martino
BACBAC SI.LA.DO.SI.LA.DO Zerlina cede alle lusinghe di Don Giovanni (Mozart)

Problema 2 – Sottostringa

Data una stringa s di caratteri di lunghezza n, e due interi i e j, con 1<=i<=j<=n, si vuole estrarre la sottostringa di s contenente i caratteri dall’i-esimo al j-esimo, estremi inclusi.

Si scriva un programma che, dati in input i e j (in notazione decimale) e una stringa, tutti separati da un punto, lasci sul nastro solo la sottostringa richiesta.
Si assuma che la stringa s possa contenere tutti i caratteri MAIUSCOLI nell’alfabeto A…Z.

NASTRO INIZIALE NASTRO FINALE
1.5.BANANA BANAN
 7.16.SUPERCALIFRAGILISTIC ALIFRAGILI
4.4.CAROTA O

Problema 3 – La dama lineare I

Il gioco della dama lineare si gioca fra due giocatori, che chiameremo Bianco e Nero, su una scacchiera di 12 caselle disposte in linea.
Ogni giocatore ha inizialmente 4 pedine del proprio colore, che indicheremo con B (per il Bianco) e N (per il Nero).
Useremo invece il carattere S per le caselle vuote.
All’inizio della partita, le quattro pedine di ogni giocatore occupano un estremo della scacchiera, e ci sono quattro caselle vuote fra i due giocatori: BBBBSSSSNNNN.
Durante il gioco, le pedine possono spostarsi e possono essere mangiate, come si vedrà più avanti.
Ad ogni momento durante una partita, la scacchiera dovrà contenere sempre 12 caselle: alcune saranno libere, altre occupate da pedine.
Ogni giocatore avrà da 0 a 4 pedine del proprio colore (se ne ha 0, ha perso e la partita è finita), ma deve sempre essere presente almeno una pedina di uno dei due giocatori.

Si scriva un programma che, data una stringa di simboli sull’alfabeto {B, S, N}, lasci sul nastro SI se la stringa rappresenta una configurazione valida della scacchiera, come definito sopra, o NO altrimenti.

Suggerimento: si noti che una configurazione è considerata valida in base al numero delle caselle e delle pedine presenti, ignorando le loro posizioni.

NASTRO INIZIALE NASTRO FINALE COMMENTO
BBBBSSSSNNNN SI
BBBNSSSSSNNN SI
BSNSN NO Troppo corta
BSSSSBBBSSNNN NO Troppo lunga
BBSBBBNNNNSS NO 5 B
NSSSSSSSSSSS SI
BNBSSSSSSNNN SI
SSSSSSSSSSSS NO Ci vuole almeno una pedina

Problema 4 – La dama lineare II

Durante una partita a dama, può essere utile poter ruotare la scacchiera, in modo da guardare le pedine dalla prospettiva dell’avversario.

Si scriva un programma che, data in ingresso una stringa rappresentante una scacchiera valida, la restituisca vista dal punto di vista dell’avversario.

NASTRO INIZIALE NASTRO FINALE
BBSBBSSNSNNN NNNSNSSBBSBB
BSBBSSSSBSNN NNSBSSSSBBSB
NNNSNSSBBSBB BBSBBSSNSNNN

Problema 5 – La dama lineare III

I giocatori muovono a turno, similmente a quanto avviene nel gioco della dama; inizia sempre il Bianco.
Al proprio turno, un giocatore può muovere una propria pedina avanti di una casella, se la casella di destinazione è libera: per esempio, la prima mossa di una partita è obbligatoriamente

BBBBSSSSNNNN -> BBBSBSSSNNNN

oppure può mangiare una pedina avversaria saltandola, se se la trova davanti e se la casella successiva è libera, come fa il bianco in questo esempio:

BBBSSBNSSNNN -> BBBSSSSBSNNN

In questo caso, se nella posizione di destinazione è ancora possibile mangiare una pedina avversaria, essa deve essere mangiata nella stessa mossa (doppio o triplo salto):

BBBSBNSNSNNN -> BBBSSSSSBNNN

Si scriva un programma che, data in input una configurazione della scacchiera, esegua una mossa valida del bianco, lasciando sul nastro la situazione della scacchiera dopo la mossa.
Si assuma che nella scacchiera di ingresso ci sia sempre esattamente una mossa possibile per il bianco.

NASTRO INIZIALE NASTRO FINALE
BBBBSSSSNNNN BBBSBSSSNNNN
SBNSNSSNSSSN SSSSSBSNSSSN
SSSBSSSSSSNN SSSSBSSSSSNN
BBSSBNNSSSSS BSBSBNNSSSSS

Problema 6 – Notazione polacca inversa

Nella notazione polacca inversa per le espressioni aritmetiche, gli operatori seguono gli operandi (sono postfissi anziché infissi):

  • 1+2 si scrive 1 2 +
  • (1+2)*(3+1) è 1 2 + 3 1 + * .

Si scriva un programma per macchina di Turing capace di calcolare il valore di semplici espressioni in notazione polacca inversa, composte da numeri decimali (a una sola cifra) e dagli operatori P (per +) e M (per ).
Si assuma che tutti gli operandi in ingresso, i risultati parziali, e il risultato finale siano interi fra 0 e 9.

NASTRO INIZIALE NASTRO FINALE
14P 5
51M 4
611PM 4
12P3M22PP 4
53P11PM1M 5

Problema 7 – Cifrario di Cesare

Durante le sue guerre in Gallia, Giulio Cesare usava un semplice cifrario per comunicare con i suoi generali.
In questo cifrario, ogni lettera era traslata di un numero fisso di posizioni.
Nel cifrario originale, questo numero era 13: si aveva dunque

ABCDEFGHIJKLMNOPQRSTUVWXYZ in chiaro
NOPQRSTUVWXYZABCDEFGHIJKLM cifrato.

Si scriva un programma per macchina di Turing che implementi un cifrario di Cesare generalizzato.
Il programma prende in ingresso un numero decimale (da 1 a 25) seguito da una stringa su A-Z, e deve lasciare sul nastro la stessa stringa, cifrata traslando ogni lettera del numero indicato di posizioni.

NASTRO INIZIALE NASTRO FINALE
3ABC DEF
13BACO ONPB
1BACO CBDP

Problema 8 – Domani è un altro giorno

Si scriva un programma che, data una data sul nastro di ingresso nel formato gg/mm/aaaa, lasci sul nastro la data incrementata di un giorno.

Si assuma che tutti gli anni divisibili per 4 (anche quelli secolari divisibili per 400) siano bisestili.

NASTRO INIZIALE NASTRO FINALE
01/02/2001 02/02/2001
31/10/2003 01/11/2003
28/02/2000 29/02/2000
28/02/2001 01/03/2001
31/12/2003 01/01/2004

Problema 9 – Scambio di coppia

Scrivere un programma per macchina di Turing che scambi a due a due i caratteri di una stringa formata da A, B e C, fornita sul nastro in ingresso.

Se la stringa contiene un numero dispari di caratteri, l’ultimo carattere rimane inalterato.

NASTRO INIZIALE NASTRO FINALE
AB BA
ABCB BABC
ABBCA BACBA
A A
BCCABA CBACAB
CCCC CCCC

Problema 10 – Il conto della serva

Si programmi una macchina di Turing che, data in ingresso una cifra espressa in euro (intera), lasci sul nastro la stessa cifra espressa in lire, con l’assunzione che 1 euro valga 2000 lire, più mille lire (la cresta della serva).

NASTRO INIZIALE NASTRO FINALE
1 3000
2 5000
15 31000
540 1081000
0 1000

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *