<antirez>

antirez 7286 days ago. 4413 views.
Oggi ho letto un quesito di programmazione su programming.reddit.com, e' molto semplice risolverlo e ve lo propongo, ma leggere questo me ne ha fatto venire in mente uno che avevo incontrato tempo fa piu' complesso che mi colpi' molto perche' la mia risposta mi sembrava molto articolata dati i termini estremamente semplici della domanda ma era esattamente la risposta all'esercizio. Pensandoci un po' su e' invece la risposta piu' ovvia e diretta, sono curioso di vedere cosa risponderete voi...

Primo quesito
Dovete programmare un automa che sta su una scala e possiede una sola funzione chiamata step che fa salire l'automa di un gradino e ritorna true, ma a volte fallisce e invece fa scendere l'automa di un gradino e ritorna false.

Scrivete una funzione step_up che fa salire in maniera affidabile l'automa di un gradino senza usare alcuna variabile ne alcuna costante numerica.

Secondo quesito
Ecco invece il secondo, piu' sottile e raffinato:

Dato un qualunque computer che presenta una architettura di Von Neumann (la cui memoria (unica) insomma viene utilizzata sia per i dati che per il codice indifferentemente, come in qualunque computer con cui siete probabilmente entrati in contatto), dotato di una CPU e di un ammontare fisso di memoria, scrivete un semplice programma che ad un certo punto terminera' sicuramente che ha il tempo di esecuzione piu' lungo possibile.

Divertitevi.... e se vi va lasciate un commento :) Tra qualche giorno le soluzioni.

Originally published on oldblog.antirez.com on 6 December 2006.

10 comments from the original post

Gianni 6 Dec 2006
Per il primo... userei la ricorsione:

bool step_up() {
    if (step()) 
        return true;
    else {
        step_up();
        step_up();
    }
}
antirez 7 Dec 2006
Gianni: bravo, e' proprio la cosa giusta, hai solo un piccolo errore formale, perche' dovrebbe ritornare un valore se funziona sempre? basta:

function step_up() {
  if (!step()) {
    step_up();
    step_up();
  }
}

Ma la tua soluzione e' valida lo stesso come risposta esatta ;)

Ora pero' passa al secondo!
a presto
Fabrizio [BS] 9 Dec 2006
Questi giochini mi sono sempre piaciuti sopratutto perchè dietro a questi esercizi quasi da settimana enigmistica si nascondono poi spunti interessanti nella pratica reale.

Pertanto, la funzione step_up, quando potrebbe essere utilizzata?

Grazie Antirez per i tuoi spunti  sei un grande :)

Fabrizio
antirez 10 Dec 2006
Fabrizio: Ciao, mi fa piacere che ti siano piaciuti gli spunti, in realta' la funzione step_up mostra la potenza dello strumento ricorsivo anche quando il problema non e' banalmente ricorsivo. Una "mente allenata" alla ricorsione lo vede subito ricorsivo ma molti programmatori potrebbero inizialmente pensare ad una soluzione iterativa (anche se la ricorsione e' incoraggiata nel quesito dal fatto che non si possono usare variabili, dunque...).

Tra poco posto la soluzione ai due quesiti, in cui parlo un po' di come la ricorsione puo' essere usata per modellare vari problemi che a prima vista appaiono iterativi in maniera estramemente elegante (perche' il programma somiglia piu' alla definizione del problema che alla sua implementazione).
Emanuele S. - santoro.<NOSPAM>emanuele@gmail.com 16 Dec 2006
class automa:
    def step(self):
        #qui il codice che fa
        #salire di un gradino
    def step_up(self):
        while step() != True:
            step()



myautoma = automa()
myautoma.step_up()


#Ed ecco che il nostro automa sale di un gradino :)
#By Emanuele S. 
#p.s:
#nella classe automa non ho implementato step() 
#perchè si sapeva che c'era e funzionava a volte si 
#e a volte no. :)
Emanuele S. - santoro.<NOSPAM>emanuele@gmail.com 16 Dec 2006
cmq il codice è in python, anche se non c'è l'indentazione (io l'avevo messa :| )
sempre io (emanuele :) ) 16 Dec 2006
while 1:
   print "1"

#il codice va, e funzionerà fino a che il sistema è in
#funzione, ed allo stesso tempo ha il tempo di esecuzione 
#più lungo possibile: lo stesso del sistema operativo
:D
antirez 19 Dec 2006
x emanuele:
la classe automa non funziona in maniera corretta! Quando l'automa non va avanti, cade un gradino. Ti serve una funzione ricorsiva o tenere conto di tutte le cadute e recuperarle nel 'while'.

Per quanto riguarda la risposta al secondo quesito, non funziona poiche' il while 1 non terminera' mai. Nel quesito era chiaramente indicato che il programma doveva terminare in maniera deterministica ad un certo punto.

Ciao!
Salvatore
Enzo 3 Feb 2007
Esercizio 1:

void step_up(){
 while(step()){
    step_up();
 }
}
Enzo 3 Feb 2007
Per il secondo esercizio basta utilizzare un programma che saturi la memoria del sistema.

void satura_memoria(){
char* c;
while(1){
c = new char;
}
}
blog comments powered by Disqus
: