lunedì 28 giugno 2010

come funziona la ricorsione (esempio fattoriale)

ciao a tutti!!!
oggi parliamo degli algoritmi ricorsivi.

wikipedia ci suggerisce questa definizione:
Viene detto algoritmo ricorsivo un algoritmo espresso in termini di se stesso, ovvero in cui l'esecuzione dell'algoritmo su un insieme di dati comporta la semplificazione o suddivisione dell'insieme di dati e l'applicazione dello stesso algoritmo agli insiemi di dati semplificati.

In pratica un'algoritmo ricorsivo usa se stesso per eseguire le stesse operazioni su un numero minore di dati.

Un famoso esempio per la spiegazione degli algoritmi ricorsivi è il fattoriale.

fattoriale(n)=n*n-1*n-2*...*1

si può notare come sia semplice riscrivere iterativamente qusta funzione

//versione C++
long long int fattoriale(int n)
{
long long int fact=1;
for(int i=1; i<=n; ++i)
{
fact*=i;
}
return fact;
}


visto? semplice semplice, lineare, no?

Il risultato è quello, ma la formulazione matematica è diversa...


n=0 -> 1
fattoriale(n)={
n*fattoriale(n-1)


Entriamo ora a spiegare di cosa ha bisogno un algoritmo ricorsivo:
1)chiamata a se stesso
2)condizione di terminazione (o di arresto)

La chiamata a se stesso implica che ci sia una fine certa. La sua eventuale mancanza arriverebbe
a richiamare un numero spropositato di istanze della funzione, portando a riempire lo stack e a
bloccare l'elaboratore.

La codifica C++ dell'algoritmo del fattoriale è scrivibile così:

long long int factRic(int n)
{
if (n==0)
{return 1;}
else
{return n*factRic(n-1);}
}

Come si può vedere, il nuovo codice è molto più simile alle specifiche matematiche ed è molto più semplice.

Vediamo ora come si può creare il fattoriale in Python.

Esistono vari modi:
1) soluzione iterativa (pari pari a quella C++, non la si riscrive...)
2) soluzione funzionale (con funzione "reduce")
3) soluzione funzionale (con lambda)

Andiamo ora a spiegare gli ultimi due modi.

Soluzione "reduce"

#!/usr/bin/python
>>>n=5
>>>fattoriale=reduce(lambda x,v: x*v, range(1, n+1))
>>>fattoriale
120
>>>

Nota: questa soluzione non è il massimo da scrivere in codice reale, costringe il lettore a capire cosa fa la funzione lambda.

Spiegherò in un prossimo post cosa serve "reduce", come funziona e come si utilizza

Soluzione lambda

#!/usr/bin/python
>>>n=5
>>>fattoriale=lambda f: (not f and 1) or f*fattoriale(f-1)
>>>fattoriale(n)
120
>>>

Nota: La sintassi utilizzata fa parte di un discorso più ampio sulla programmazione funzionale, che verrà affrontato nei prossimi post, e che è possibile leggere qui
Intanto...

La funzione fattoriale valuta f. Se f è uguale a zero (qui indicato con not f, perchè in Python lo Zero è equivalente al booleano False) allora viene restituito 1, altrimenti il prodotto di f per il risultato di fattoriale con f decrementato di 1.

Posterò nel prossimo post un esempio molto più utile: la ricerca binaria.

Stay Tuned!!!

sabato 12 giugno 2010

admin grafico in RFRracing!

Sono diventato admin grafico del forum

RFRracing.forumcommunity.net


questo sito è una community di giocatori rFactor in cui si organizzano campionati,
si possono scaricare mod (modelli delle auto con cui giocare) e chiaccherare tranquillamente.

(si, ho fatto un pò di pubblicità... ma IO POSSO! sono chuck norris sotto mentite spoglie di un semplice utente blogspot... xD xD xD)

venerdì 4 giugno 2010

Rilascio DLM versione 0.6

Qui è attualmente disponibile il codice del progetto DLM, annunciato 2 post or sono.

Le features disponibili sono:
  • possibilità di tracciare poligoni regolari di N lati, con lunghezza del lato dato.
  • possibilità di tracciare cerchi ed archi
  • possibilità di gestire la dimensione e il colore della traccia
  • possibilità di mostrare/nascondere il robot
  • presenti le variabili, con metodi matematici (addizione, sottrazione, moltiplicazione,
    divisione, elevamento a potenza, radice quadrata)
  • disponibile costrutto di iterazione (ciclo for)
  • disponibili le funzioni
Si stanno sviluppando le funzioni con parametri e costrutti di selezione (if)

Aggiornamento: a causa dello sviluppo di altre applicazioni, il mantenimento della DLM è attualmente bloccato a data da destinarsi. Se avete in mente di creare patch e/o di aiutare lo sviluppo dell'interprete potete contattarmi (vedi la sezione "Sviluppo DLM" per contatti)

mercoledì 2 giugno 2010

come sprecare coca cola e mentos

Oggi non sapete cosa fare?

Provate a fare questo!






Lo staff di "delta the programmer" incentiva la ricerca scientifica, anche quando è finalizzata alla creazione di chindogu !!! xD xD xD