Due quesiti di programmazione
Wednesday, 06 December 06
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...
Scrivete una funzione step_up che fa salire in maniera affidabile l'automa di un gradino senza usare alcuna variabile ne alcuna costante numerica.
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.
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.
Do you like this article?
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.
Note: you'll not see this box again if you are a usual reader.
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.
Note: you'll not see this box again if you are a usual reader.
Comments
07 Dec 06, 06:08:00
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
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
08 Dec 06, 19:58:51
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
Pertanto, la funzione step_up, quando potrebbe essere utilizzata?
Grazie Antirez per i tuoi spunti sei un grande :)
Fabrizio
10 Dec 06, 06:01:14
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).
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).
16 Dec 06, 12:54:32
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. :)
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. :)
16 Dec 06, 12:55:56
cmq il codice è in python, anche se non c'è l'indentazione (io l'avevo messa :| )
16 Dec 06, 12:58:59
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
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
19 Dec 06, 03:43:57
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
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
03 Feb 07, 03:55:37
Per il secondo esercizio basta utilizzare un programma che saturi la memoria del sistema.
void satura_memoria(){
char* c;
while(1){
c = new char;
}
}
void satura_memoria(){
char* c;
while(1){
c = new char;
}
}
bool step_up() {
if (step())
return true;
else {
step_up();
step_up();
}
}