Immaginate di scrivere un’espressione composta da un certo numero di parentesi aperte e dello stesso numero di parentesi chiuse, e di voler verificare se l’espressione è “ben formata”, nel senso che non ci siano mai più parentesi chiuse che aperte, e quindi siano tutte accoppiabili come “aperta+chiusa”. Un’espressione come ()(()) è per esempio ben fatta; le parentesi in posizione 1 e 2 si possono eliminare come quelle in posizione 4 e 5, lasciando quelle in posizione 3 e 6 che a questo punto si possono eliminare. Un’espressione come ())(()() non lo è: possiamo eliminare le parentesi in posizione 1 e 2, in posizione 5 e 6, e in posizione 7 e 8 ma restano 3 e 4 che sono chiusa+aperta. La domanda è: è sempre possibile prendere un certo numero (eventualmente nessuna) di parentesi dal fondo di un’espressione e trasportarle all’inizio nello stesso ordine per avere un’espressione ben formata? In questo caso potrei spostare cinque parentesi e ottenere (()()()).
![[ ((()())(())))))(((() ]](https://i0.wp.com/xmau.com/wp/notiziole/wp-content/uploads/sites/6/2021/09/q542a.png?resize=544%2C78&ssl=1)
(trovate un aiutino sul mio sito, alla pagina http://xmau.com/quizzini/p542.html; la risposta verrà postata lì il prossimo mercoledì. Problema di James Tanton.)
Ultimo aggiornamento: 2021-09-22 16:03
Mi si permetta una battuta…
Con tutte queste parentesi, è forse che hai deciso di imparare a programmare in LISP?
stavo per metterlo come battuta, ma poi ho pensato che anche tra i miei ventun lettori l’avrebbero capita in pochi.
A questo proposito vorrei ricordare un mio collega, informatico e poeta, che scrisse molti anni fa questo breve componimento monovocalico: “visti i MIPS / riscrissi il CICS in Lisp”
Il link alla pagina del quizzino porta al quizzino precedente.
ero convinto di averlo cambiato, tanto che i due prossimi che sono già pronti hanno la numerazione corretta… devo essermi dimenticato di salvarlo.