Problema 1 – Quadristringhe
Una quadristringa è una stringa su un alfabeto dato che ha la forma XXXX, ovvero, che è composta di quattro parti uguali ripetute.
Per esempio, abcabcabcabc è una quadristringa.
Si scriva un programma che, data in ingresso una stringa sull’alfabeto a, b, c, lasci sul nastro SI se la stringa di ingresso è una quadristringa, NO altrimenti.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| abababab | SI |
| bacbacbacbac | SI |
| cbabcbcb | NO |
| cccc | SI |
| aaaaa | NO |
Problema 2 – Tristringhe
Analogamente all’esercizio precedente, una tristringa è una stringa che ha la forma XXX, ovvero, che è composta di tre parti uguali ripetute.
Per esempio, abcabcabc è una tristringa.
Si scriva un programma che, data in ingresso una stringa sull’alfabeto a, b, c, lasci sul nastro SI se la stringa di ingresso è una tristringa, NO altrimenti.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| aaa | SI |
| bbbbbb | SI |
| abababab | NO |
| babacbabacbabac | SI |
Problema 3 – I multidispari I
Riconoscimento di espressioni
I numeri multidispari sono quelli che hanno la forma (2(2(2(…(2+1)…)+1)+1)+1).
Sono multidispari
- 2+1=3,
- 2(2+1)+1=7
- 2(2(2+1)+1)+1=15
- …
Si scriva un programma che, ricevuta in ingresso una stringa sull’alfabeto {1, 2, +, [, ]} (in cui le parentesi quadre prendono il posto delle tonde), lasci sul nastro SI se la stringa ricevuta è l’espressione di un numero multidispari racchiusa fra parentesi, NO altrimenti.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| [2+1] | SI |
| [[1]+2] | NO |
| 2+2 | NO |
| 2[2+2] | NO |
| [2[2[2[2+1]+1]+1]+1] | SI |
| 2[2[2[2+1]+1]+1]+1 | NO |
Problema 4 – I multidispari II
Calcolo
Con riferimento all’esercizio precedente, si scriva un programma che, ricevuta in ingresso una espressione valida per un numeromultidispari (sempre racchiusa fra parentesi), lasci sul nastro il numero decimale corrispondente al risultato del calcolo.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| [2+1] | 3 |
| [2[2+1]+1] | 7 |
| [2[2[2[2[2[2[2+1]+1]+1]+1]+1]+1]+1] | 255 |
Problema 5 – I multidispari III
Riconoscimento dei valori
Con riferimento agli esercizi precedenti sui multidispari, si scriva un programma che, ricevuto in ingresso un numero decimale, lasci sul nastro SI se il numero in questione è un multidispari, NO altrimenti.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 3 | SI |
| 7 | SI |
| 35 | NO |
| 511 | SI |
| 2041 | NO |
Problema 6 – Conversione esadecimale-binario
I numeri in base 16, o esadecimali, utilizzano come cifre le consuete cifre decimali 0..9, più le lettere A, B, C, D, E, F che rappresentano, rispettivamente, 10, 11, 12, 13, 14, 15.
- Per esempio, il numero esadecimale 2B vale 2×161+11×160, ovvero 43 in decimale.
- I numeri in base 2, o binari, utilizzano invece esclusivamente le cifre 0 e 1.
- Per esempio, 1001 in binario vale 1×23+0x22+0x21+1×20, ovvero 9 in decimale.
Si scriva un programma che, ricevuto in ingresso un numero esadecimale, lasci sul nastro lo stesso numero espresso in notazione binaria.
Suggerimento: si noti che una cifra esadecimale corrisponde al più a 4 cifre binarie.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 1 | 1 |
| A | 1010 |
| F1ABA | 11110001101010111010 |
| B8 | 10111000 |
| 20 | 100000 |
| 0 | 0 |
Problema 7 – Vettori fagici
Il DNA degli esseri viventi è costituito da una lunga catena di basi (adenina, timina, guanina, citosina, indicate rispettivamente con A, T,G, C).
Su una sequenza di basi operano degli enzimi, che per via chimica possono operare trasformazioni sulla sequenza di DNA.
In particolare, i vettori fagici sono in grado di eliminare certe sotto-sequenze di DNA, ricongiungendo le estremità del frammento dopo la rimozione.
Si scriva un programma che simuli il funzionamento di un vettore fagico.
Il programma, ricevute in ingresso due stringhe sull’alfabeto {A, T, G, C} separate da X, rimuove tutte le occorrenze disgiunte della prima stringa all’interno della seconda stringa, e lascia sul nastro la sola stringa risultante.
Nel caso di più occorrenze sovrapposte (per esempio: se si vuole rimuovere ATA da CATATAG), si rimuova soltanto l’occorrenza più a sinistra (producendo come risultato CTAG).
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| AXCTAAGAC | CTGC |
| ACCXCACTACCTACCAG | CACTTAG |
| CTTAXGATTACA | GATTACA |
| ATAXCATATAG | CTAG |
| ATTAXATTAATTA |
Problema 8 – XOR esadecimale
Si scriva un programma che, dati in ingresso due numeri esadecimali (si veda l’esercizio 6) separati da un punto, lasci sul nastro il risultato dell’or esclusivo (o xor) applicato ai due numeri.
L’operatore xor è definito come segue: se nella rappresentazione binaria dei due operandi le cifre nella stessa posizione hanno lo stesso valore, allora la cifra corrispondente del risultato sarà 0; altrimenti, essa sarà 1.
Per esempio (…)
Si assuma che i numeri esadecimali passati in ingresso abbiano la stessa lunghezza, e si produca un risultato della stessa lunghezza.
Per questo esercizio, sono ammessi gli 0 iniziali.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| A5.BC | 19 |
| 1B4.020 | 194 |
| 1.1 | 0 |
| 0A224.55555 | 5F771 |
| 00.00 | 00 |
Problema 9 – Gruppi ciclici
Un gruppo ciclico G(n,k), con 0 < n < k, è una sequenza di interi tali che il primo elemento è sempre 0, e quelli successivi sono calcolati aggiungendo n al precedente e calcolando il risultato modulo k.
La sequenza si interrompe quando viene generato un numero già presente.
Per esempio,
- G(2,5)={0,2,4,1,3}
- G(3,6)={0,3}
- G(1,5)={0,1,2,3,4}.
Si scriva un programma che, presi in ingresso n e k, con 1 < k < 10, lasci sul nastro il gruppo ciclico G(n,k), nell’ordine corretto.
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| 25 | 02413 |
| 36 | 03 |
| 49 | 048372615 |
| 39 | 036 |
| 14 | 0123 |
| 28 | 0246 |
Problema 10 – Il lamba-calcolo
Il lambda-calcolo è un formalismo per la definizione e l’applicazione di funzioni.
Una lambda-espressione è costituita da una dichiarazione di parametri, preceduti dalla lettera L, seguita da una espressione; le due parti sono separate da un punto.
Per esempio, la lambda-espressione Lx.x rappresenta la funzione f(x)=x (si noti però che le lambda-espressioni non introducono nomi per le funzioni: nel primo caso, non compare il nome f).
L’applicazione di una funzione a un argomento viene denotata scrivendo l’argomento a destra della funzione: per esempio, (Lx.x)3rappresenta la funzione f(x)=x applicata a 3, ovvero f(3), e dunque vale 3).
Le applicazioni possono anche essere multiple: in questo caso, si calcola prima l’applicazione più a sinistra e più interna rispetto alle parentesi.
Per esempio, (Lx.x+1)((Lx.2x)3) = (Lx.x+1)6 = 7, mentre (Lx.xx)(Lx.x)3 = (Lx.x)(Lx.x)3 = (Lx.x)3 = 3.
Useremo un lambda-calcolo semplificato con una sola variabile (x), e un solo termine base (e).
Una lambda-espressione è una sequenza di elementi, ciascuno dei quali può essere un termine oppure una applicazione.
Un termine può essere una x oppure una e.
Una applicazione ha la forma [lambda-espressione]termine oppure [lambda-espressione]applicazione.
Si noti che, visto che abbiamo una sola variabile, non occorre avere un simbolo distinto per “Lx.”: è sufficiente la partentesi quadra.
Si scriva un programma che, ricevuta in ingresso una lambda-espressione, lasci sul nastro il risultato della sua valutazione secondo le regole sopra esposte.
Suggerimento: si scriva il programma in modo che esso applichi ripetutamente una riscrittura di una applicazione (la più interna a sinistra).
Per esempio:
- [xx]ex -> eex
- [x[xx]e]x -> [xee]x -> xee
- [[xex]e]x -> [eee]x -> eee
- [[xe]x][ex]e -> [xe][ex]e -> [xe]ee -> eee
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| e | e |
| [x]e | e |
| [xx][x]x | xx |
| [xx][x]e | ee |
| [x[xx]e]x | xee |
| x | x |
| [ex[x]e]x | exe |