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
Per il primo... userei la ricorsione:
bool step_up() {
if (step())
return true;
else {
step_up();
step_up();
}
}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 prestoQuesti 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
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).
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. :)cmq il codice è in python, anche se non c'è l'indentazione (io l'avevo messa :| )
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
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
Esercizio 1:
void step_up(){
while(step()){
step_up();
}
}Per il secondo esercizio basta utilizzare un programma che saturi la memoria del sistema.
void satura_memoria(){
char* c;
while(1){
c = new char;
}
}