Accesso

Cherubino     Gara nazionale di programmazione della
Macchina di Turing
 
 

Esercizi di Gara della XII 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.

 

Esercizio 1: Notazione unaria [Punti 3]. Un numero intero n è rappresentato in notazione unaria da una sequenza di n simboli uguali, per esempio U. Si scriva un programma per macchina di Turing che, ricevuto sul nastro un intero positivo in notazione decimale, lasci come risultato lo stesso numero, scritto in notazione unaria.

 

NASTRO INIZIALE

NASTRO FINALE

4

UUUU

0

 

13

UUUUUUUUUUUUU

1

U

 

Esercizio 2: Inversione [Punti 5]. Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull'alfabeto {H, O, C} (attenzione: si tratta della lettera O, non della cifra 0), lasci sul nastro alla fine della computazione la stessa stringa, ma scritta in ordine inverso.

 

NASTRO INIZIALE

NASTRO FINALE

OOOH

HOOO

C

C

HCCOH

HOCCH

HOCCOCH

HCOCCOH

OOO

OOO

 

Esercizio 3: Completezza [Punti 4]. Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull'alfabeto {H, O, C}, lasci sul nastro la scritta SI se la stringa in ingresso conteneva ciascuno dei caratteri dell'alfabeto almeno una volta (la stringa in questo caso si dice completa rispetto all'alfabeto), NO in caso contrario.

 

NASTRO INIZIALE

NASTRO FINALE

COO

NO

HCCO

SI

COCO

NO

HHHHH

NO

OHHHHC

SI

 

Esercizio 4: Ordinamento [Punti 7]. Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull'alfabeto {H, O, C}, lasci sul nastro una stringa composta dagli stessi simboli presenti nell'input, ciascuno con lo stesso numero di occorrenze, ma ordinati in modo che tutte le H precedano le O, e tutte le O precedano le C.

 

NASTRO INIZIALE

NASTRO FINALE

CHOO

HOOC

COCCO

OOCCC

HHHOOCCC

HHHOOCCC

COCHCOCH

HHOOCCCC

O

O

 

Esercizio 5: La chimica di Turing I [Punti 12]. Usiamo i caratteri H, O, C per rappresentare, rispettivamente, un atomo di idrogeno, ossigeno, carbonio. Una sequenza di queste lettere può quindi rappresentare una molecola (ovviamente è anche possibile scrivere formule che non possono rappresentare una molecola stabile, ma per semplicità non ci poniamo il problema). Nella chimica di Turing si usa una notazione compatta per scrivere queste formula, consistente in un numero decimale preceduto dalla lettera che identifica una molecola. Per esempio, O2 (ossigeno molecolare) sta per OO, CH4 (metano) per CHHHH e H2O (acqua) per HHO. Si scriva un programma per macchina di Turing che, ricevuto in ingresso una formula in notazione compatta, lasci sul nastro la stessa formula in notazione espansa. Si assuma per semplicità che le quantità siano sempre espresse da una sola cifra decimale (da 2 a 9; l'assenza di un numero indica 1).

 

NASTRO INIZIALE

NASTRO FINALE

COMMENTO

CO2

COO

Anidride carbonica

H2O2

HHOO

Acqua ossigenata

CH4

CHHHH

Metano

CH3CH3

CHHHCHHH

Etano

CH2CH2

CHHCHH

Etilene

O2

OO

Ossigeno

 

Esercizio 6: La chimica di Turing II [Punti 15]. Come ulteriore forma di compressione, una formula in notazione compatta può essere preceduta da un numero decimale, che indica quante volte la formula è ripetuta. Per esempio, 2H2O (due molecole di acqua) sta per HHOHHO, e 4CO2 (quattro molecole di anidride carbonica) sta per COOCOOCOOCOO. Si scriva un programma per macchina di Turing per effettuare il cambio di notazione, con l'assunzione che il numero iniziale (che rappresenta il numero di molecole) sia compreso fra 2 e 9 (estremi inclusi), oppure assente del tutto.

 

NASTRO INIZIALE

NASTRO FINALE

4CO2

COOCOOCOOCOO

CO2H

COOH

COOH

COOH

3C2H2O

CCHHOCCHHOCCHHOCCHHO

 

 

Esercizio 7: Successione di Fibonacci [Punti 15]. I numeri di Fibonacci sono definiti, per ricorrenza, dalla seguente equazione:

 

f(x) = 1, se x <= 2

f(x) = f(x-1)+f(x-2), altrimenti

La successione di Fibonacci è formata dai numeri di Fibonacci consecutivi, partendo da f(1) (si noti che ogni termine della successione dopo i primi due è dato dalla somma dei due termini precedenti). Si scriva un programma per macchina di Turing che, dato in ingresso un numero decimale n, lasci in uscita sul nastro i primi n termini della successione di Fibonacci, separati esattamente da uno spazio.

NASTRO INIZIALE

NASTRO FINALE

5

1 1 2 3 5

8

1 1 2 3 5 8 13 21

10

1 1 2 3 5 8 13 21 34 55

1

1

 

Esercizio 8: Successione di Collatz [Punti 22]. Si consideri la funzione

 

c(x) = 3x+1, se x è dispari

c(x) = x/2, se x è pari

 

Si scriva un programma per macchina di Turing che, ricevuto sul nastro un intero x, lasci sul nastro la sequenza

x c(x) c(c(x)) c(c(c(x))) ... 1

(con i valori separati da un singolo spazio). Si noti che, benché i valori della successione così ottenuta crescano e decrescano in maniera apparentemente imprevedibile, esiste una congettura (non un teorema), detta Congettura di Collatz, secondo la quale per qualunque valore iniziale x, la successione raggiunge prima o poi il valore 1. La lunghezza della sequenza è anch'essa molto variabile: per x=26, occorrono 11 passi per giungere a 1, ma per x=27 ne occorrono ben 111. La congettura è stata verificata su calcolatore per tutti gli interi x fino a circa 2,88·1018, ma manca una dimostrazione che ne garantisca la verità per qualunque x. Sarete voi a trovarla?

 

NASTRO INIZIALE

NASTRO FINALE

5

5 16 8 4 2 1

6

6 3 10 5 16 8 4 2 1

13

13 40 20 10 5 16 8 4 2 1

27

27 82 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1

2

2 1

1

1

 

Esercizio 9: La chimica di Turing III [Punti 35]. Una formula stechiometrica di Turing è un'equazione, i cui termini sono separati dal simbolo =, e ciascuno dei termini è formato da una somma di molecole, in cui ogni addendo è una formula in notazione compatta (es.: 2H2O). Una formula di questo tipo si dice bilanciata se il numero totale di occorrenze di ogni elemento a destra e a sinistra del segno di uguale è identico. Per esempio, 2H2O+O2+H+H=2O2+4H è bilanciata (sono presenti 4 atomi di ossigeno e 4 di idrogeno in entrambi i termini), così come CH4+2O2=CO2+2H2O (che rappresenta la combustione del metano in presenza di ossigeno, e produce anidride carbonica e acqua), mentre CO2+H2O=4CHO non lo è. Si scriva un programma per macchina di Turing che, ricevuta in ingresso una stringa rappresentante una formula stechiometrica, lasci sul nastro la scritta SI se la formula è bilanciata, NO altrimenti.

 

NASTRO INIZIALE

NASTRO FINALE

2H2O=O2H4

SI

2H2O+O2+2H=2O2+4H

SI

H2O+2OH=CH4

NO

4O=2O2

SI

CH4+CO2+O2=2CO2+2H2O

NO

 

 

Esercizio 10: La chimica di Turing IV [Punti 30]. In tempi di crisi energetica, si cerca di estrarre idrocarburi dalle fonti più variegate. Siamo interessati in particolare al metano, che ha formula CH4. Si scriva un programma per macchina di Turing che, ricevuta in input un termine di una formula stechiometrica (gli "ingredienti"), lasci sul nastro il numero di molecole di metano che sarebbe potenzialmente possibile estrarre dagli ingredienti. Per esempio, 8CO2+8H2O contiene 8 atomi di carbonio e 16 di idrogeno (oltre a 24 di ossigeno, che però non ci interessano); sarebbe quindi possibile estrarre da questi ingredienti fino a 4 molecole di metano (ovvero, 4 atomi di carbonio e 16 di idrogeno). Si noti che il numero di molecole di metano estraibili da una formula potrebbe richiedere più cifre decimali per essere espresso.

 

NASTRO INIZIALE

NASTRO FINALE

8CO2+8H2O

4

6H2O+4CO2+COOH+4H2O

5

H2O+5CO2

0

6CH4

6

4O2+8H2O+4OH+4CO2+4C2H5

10

 

 I testi

  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...)