Accesso

Cherubino     Gara nazionale di programmazione della
Macchina di Turing
 
 

Esercizi di Gara della XI edizione


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. Si ricorda che a parità di punteggio, verrà considerato l'istante dell'ultimo salvataggio per ordinare la classifica finale.


Esercizio 1: Moltiplicatore per 10 [Punti 3]. Si scriva un programma per Macchina di Turing che, ricevuto sul nastro un numero decimale, lasci sul nastro alla fine della computazione il risultato della moltiplicazione del numero di ingresso per 10.


Esempi:

NASTRO INIZIALE

NASTRO FINALE

3

30

450

4500

123456

1234560

0

0





Esercizio 2: Divisore per 10 (I) [Punti 5]. Si scriva un programma per Macchina di Turing che, ricevuto sul nastro un numero decimale, lasci sul nastro alla fine della computazione il risultato della divisione del numero di ingresso per 10, approssimato in basso.


Esempi:

NASTRO INIZIALE

NASTRO FINALE

145

14

534623

53462

10

1

0

0





Esercizio 3: Riconoscimento numeri reali [Punti 10]. Si scriva un programma per Macchina di Turing che, ricevuta sul nastro una stringa qualunque sull'alfabeto { 0-9, +, -, .} lasci sul nastro la scritta SI se la stringa di ingresso rappresenta un numero reale in notazione decimale, definito come


[ + o - ] <sequenza di cifre> [ . <sequenza di cifre> ]


Se la stringa di ingresso non è un numero reale in notazione decimale, il programma deve lasciare sul nastro la stringa NO. Si noti che, sotto l'assunzione che l'input sia finito, tutti i numeri esprimibili in questa notazione sono in realtà numeri razionali: come tutti i sistemi di elaborazione digitali, la Macchina di Turing può solo trattare approssimazioni razionali dei numeri reali.


Esempi:

NASTRO INIZIALE

NASTRO FINALE

34

SI

-342.123

SI

-343-342

NO

234.234.23

NO

+12.45

SI

-38

SI

--34

NO

0

SI





Esercizio 4: Divisore per 10 (II) [Punti 12]. Si scriva un programma analogo a quello dell'esercizio 2, in grado però di operare su numeri reali (con opzionalmente segno e parti decimali) e approssimante verso lo 0. Il segno va preservato nel risultato.


Esempi:

NASTRO INIZIALE

NASTRO FINALE

145

14

-3017

-301

-3.1415926

0

31.415926

3

-100.5

-10



Esercizio 5: Divisore per 10 (III) [Punti 15]. Si scriva un programma analogo a quello dell'esercizio 4, che approssimi il risultato all'intero più vicino anziché verso lo 0.


Esempi:

NASTRO INIZIALE

NASTRO FINALE

145

14

145.1

15

137.81

14

-218.0001

-22

5

0

6

1





Esercizio 6: Conteggio di sottostringhe [Punti 25]. Si scriva il programma di una Macchina di Turing che, date sul nastro due stringhe formate da lettere nell'alfabeto { A..J } separate da $, conta le occorrenze distinte della stringa a sinistra del $ all'interno di quella a destra del $. Il programma deve lasciare sul nastro il numero di occorrenze trovate, espresso in notazione decimale.


Esempi:

NASTRO INIZIALE

NASTRO FINALE

AB$ABBACCHIA

1

BA$BABA

2

AB$CABABBAABDABBBABABBBBE

6

AA$AAABBAA

2

F$ABCDE

0

AAA$AAABBAA

1





Esercizio 7: Percentuale [Punti 25]. Si scriva un programma per Macchina di Turing che, ricevuta in ingresso una stringa della forma a%b, in cui a e b sono numeri decimali e a è compreso fra 0 e 100 (inclusi), lasci sul nastro al termine della computazione il numero naturale corrispondente all'a% di b, approssimato in basso.


Esempi:

NASTRO INIZIALE

NASTRO FINALE

10%50

5

25%100

25

33%1000

333

4%1890

75

0%3240

0

100%12

12

50%0

0





Esercizio 8: Parole simili [Punti 30]. Definiamo la distanza tra due parole composte di lettere A..Z come il numero di posizioni in cui le lettere corrispondenti nelle due parole differiscono. Nel caso una parola sia più corta dell'altra, si assume che essa differisca in tutte le posizioni rimaste. Per esempio, ABACO e ABATE sono a distanza 2, mentre ACANTO e ABATE sono a distanza 4. Una nozione di distanza simile a questa (ma leggermente più complessa) è usata, fra l'altro, dai correttori ortografici forniti con i programmi di videoscrittura.

Si scriva il programma di una macchina di Turing che, dato sul nastro di input una parola seguita dal simbolo $ e una lista di parole separate da :, lasci sul nastro alla fine della computazione la parola della lista più "vicina" alla prima (ovvero, la cui distanza rispetto alla prima parola è minima). Nel caso vi siano più parole con pari distanza minima, il programma dovrà restituire come risultato la prima della lista (ovvero, quella più a sinistra). Si assuma che ciascuna parola sia lunga al più 9 caratteri.


Esempi:

NASTRO INIZIALE

NASTRO FINALE

PEFA$PELO:PERA:PASSA

PERA

PASSARE$FIUTARE:PASSATA:PASSARE

PASSARE

NULLA$


SQUOLA$SQUALO:SCUOLA:STUOLO:STOLA

SCUOLA

Esercizio 9: La prova del 9 [Punti 42]. La prova del 9 è un metodo per verificare la correttezza di una moltiplicazione, basato sulle proprietà dell'aritmetica modulare. Il metodo di prova si basa sul fatto che per ogni n, 10n mod 9 = 1; tecnicamente, diciamo che la somma delle cifre di un numero decimale mantiene l'equivalenza al numero in Z9 (l'anello degli interi modulo 9).

La forma tradizionale della prova del 9 è la seguente. Innanzitutto si traccia una croce, che delimita quattro spazi che chiameremo A, B, C e D:

A

B

C

D


Nelle quattro zone si scrive (volendo verificare per esempio se è corretto il risultato 1902×1964=3735528):

  1. In A: si sommano ripetutamente le cifre del moltiplicando, il primo fattore, finché non resta un numero ad una sola cifra: es. 1902  =>  1+9+0+2=12;   12  =>  1+2=3

  2. In B: si applica lo stesso procedimento con il moltiplicatore, il secondo fattore: es. 1964  =>  1+9+6+4=20;   20  => 2+0=2

  3. In C: si moltiplicano i 2 numeri appena ottenuti e posti in alto sulla croce. Se il risultato della moltiplicazione ha più cifre, esse sono ripetutamente sommate come prima: es. 3*2=6.

  4. In D: si sommano le cifre del risultato presunto della moltiplicazione: es. 3735528  =>  3+7+3+5+5+2+8=33;   33  => 3+3=6


Nel caso del nostro esempio avremo dunque:

3

2

6

6

Quando, come in questo caso, i due numeri in basso sono uguali allora la prova ha esito positivo, altrimenti ha esito negativo.

Si noti però che:

  • se la prova ha esito negativo allora la moltiplicazione è sicuramente errata

  • se la prova ha esito positivo, il risultato trovato potrebbe essere errato, e differire dal risultato reale per un multiplo di 9. Infatti, se al risultato si sommasse o sottraesse 9 o un suo multiplo, il test sarebbe ancora superato (9 è infatti equivalente a 0 in Z9)!


Si scriva un programma per Macchina di Turing che, ricevuta sul nastro una moltiplicazione con un risultato presunto, nella forma a*b=c (con a, b e c numeri decimali) lasci sul nastro la stringa SI se la prova del 9 ha esito positivo, NO in caso contrario. Come già osservato, il programma deve rispondere SI anche se la moltiplicazione è errata, ma la prova del 9 è superata.


Esempi:

NASTRO INIZIALE

NASTRO FINALE

123*456=56088

SI

123*456=56089

NO

123*456=56097

SI

0*12=0

SI

150*30=4500

SI

150*30=9

SI

150*30=4300

NO




Esercizio 10: Espressioni regolari [Punti 45]. Una espressione regolare identifica un insieme di stringhe, ovvero un linguaggio. Un'espressione regolare è denotata da un pattern, ovvero da una sequenza di caratteri, alcuni dei quali dotati di una particolare interpretazione, che indica quali stringhe appartengono all'insieme e quali no. Ad esempio il pattern CIAO+ denota l'insieme di tutte le stringhe formate dai caratteri 'C', 'I', 'A' e che terminano con una sequenza di uno o più caratteri 'O'. Ecco quindi che le stringhe CIAO, CIAOO, CIAOOOOO ecc. apparterranno all'insieme (si usa dire che esse soddisfano l'espressione regolare), mentre XX, CIA, CIAOA ecc. non vi apparterranno.

Consideriamo pattern formati da sequenze di caratteri da interpretare come segue:

  • Ogni carattere nell'alfabeto { A..Z } indica che nella stringa da verificare deve essere presente lo stesso carattere

  • Il carattere '.' indica che nella stringa da verificare deve essere presente un carattere qualsiasi

  • Se un carattere è seguito dal carattere '*' si intende che nella stringa da verificare il carattere precedente l'* può occorrere 0 o più volte (es. CI*AO indica le stringhe della forma CAO, CIAO, CIIAO, ...)

  • Se un carattere è seguito dal carattere '+' si intende che nella stringa da verificare il carattere precedente il + può occorrere 1 o più volte (es. CI+AO indica le stringhe della forma CIAO, CIIAO, ...). Si noti che per ogni carattere c, il pattern c+ è equivalente al pattern cc*.


Si scriva il programma di una Macchina di Turing che data sul nastro un pattern nel formato descritto, seguito dal simbolo $ di separazione e da una stringa (anche vuota) sull'alfabeto { A..Z }, lasci sul nastro SI se la stringa soddisfa l'espressione regolare denotata dal pattern, NO altrimenti.


Esempi:

NASTRO INIZIALE

NASTRO FINALE

CIAO$CIAOO

NO

CIAO$CIAO

SI

C*I*A*O*$

SI

C*I*A*O*$IIAAA

SI

C*I*A*O*$ICIAO

NO

C+I*AO$CIAO

SI

C+I*AO$CCIIIAO

SI

C+I*AO$CIAOO

NO

C.AO$CIAO

SI

C.AO$CEAO

SI

C.AO$EEAO

NO

.*$

SI

.*$BUONLAVORO

SI

.*A$BUONLAVORO

NO

  I GARA
  II GARA
  III GARA
  IV GARA
  V GARA
  VI GARA
  VII GARA
  VIII GARA
  IX GARA
  GARA ROTARY 2006
  X GARA
  XI GARA
  XII Gara
  XIII Gara
  XIV Gara
  XV Edizione
  XVI Edizione
  XVII Edizione
  XVIII Edizione
  XIX Edizione
(Altri collegamenti...)