codice c per fattoriale

[rw]

salve a tutti, mi sto dilettando ad imparere un po il
linguaggio c, e dopo alcuni semplici esempi sono
arrivato ad un assurdo !!
ecco il codice di un algoritmo che dovrebbe
calcolare il fattoriale di un numero

#include<stdio.h>
#include<math.h>
int main() {
int n,i;
float f;
i=1;
f=1;
printf("inserisci n\n");
scanf("%d",&n);
while (i<=n) {
f=f*i;
i=i+1;
}
printf("il fattoriale e' %f\n",f);
getchar();
getchar();
}

il problema è che questo programma, compilato
calcola correttamente il fattoriale fino a n=13
dopodiche sembra che spari numeri a caso..
qualcuno mi sa dire perchè??

[Roberto Montaruli]

Post by rw
salve a tutti, mi sto dilettando ad imparere un po il
linguaggio c, e dopo alcuni semplici esempi sono
arrivato ad un assurdo !!
ecco il codice di un algoritmo che dovrebbe
calcolare il fattoriale di un numero
#include<stdio.h>
#include<math.h>
int main() {
    int n,i;
    float f;
    i=1;
    f=1;
    printf("inserisci n\n");
    scanf("%d",&n);
    while (i<=n) {
                 f=f*i;
                 i=i+1;
                 }
    printf("il fattoriale e' %f\n",f);
    getchar();
    getchar();
            }
il problema che questo programma, compilato
calcola correttamente il fattoriale fino a n=13
dopodiche sembra che spari numeri a caso..
qualcuno mi sa dire perch ??

Perche' hai usato un float.
Quando i numeri raggiungono un valore superiore al massimo esprimibile
con quel tipo di variabile, subentrano errori dovuti alla perdita
delle cifre meno significative.

Se hai bisogno di calcolare fattoriali di numeri grossi, devi usare
interi a precisione multipla, che non sono un tipo standard ma che
devi definire tu (con tutta la matematica di supporto ad esso) oppure
utilizzare qualche libreria gia' pronta.

In ogni caso il fattoriale e' piu' bello se definito ricorsivamente

int fact(int x)
{
return (x==0) ? 1 : x * fact(x-1);
}

[Andrea Laforgia]

Post by Roberto Montaruli
In ogni caso il fattoriale e' piu' bello se definito ricorsivamente

Ma manco per niente. E' solo estremamente inefficiente.

[Roberto Montaruli]

Post by Andrea Laforgia

Post by Roberto Montaruli
In ogni caso il fattoriale e' piu' bello se definito ricorsivamente

Ma manco per niente. E' solo estremamente inefficiente.

Vorrei vedere come risolvi il sudoku senza usare la ricorsione!

[Andrea Laforgia]

On Thu, 21 Jan 2010 21:15:42 +0100, Roberto Montaruli

Post by Roberto Montaruli
Vorrei vedere come risolvi il sudoku senza usare la ricorsione!

Mai fatto un sudoku in vita mia. Poi mi spieghi cosa c'entri con
quanto si sta dicendo. Voglio comunque sperare che tu sappia che
qualsiasi ricorsione è riconducibile ad una iterazione.

[Roberto Montaruli]

Post by Andrea Laforgia
On Thu, 21 Jan 2010 21:15:42 +0100, Roberto Montaruli

Post by Roberto Montaruli
Vorrei vedere come risolvi il sudoku senza usare la ricorsione!

Mai fatto un sudoku in vita mia.
Poi mi spieghi cosa c'entri con
quanto si sta dicendo.

Mi cestini un concetto sacrosanto come la ricorsivita' dicendo che e'
poco efficiente nel fattoriale.
Lo so anche io che e' poco efficiente, ma considerando che al massimo
iteri una ventina di volte, la cosa e' sopportabile, in cambio di
avere un codice piu' comprensibile.

Post by Andrea Laforgia
Voglio comunque sperare che tu sappia che
qualsiasi ricorsione è riconducibile ad una iterazione.

Si, ma al prezzo di quale codice confuso?
Sono mica tutti fattoriali le funzioni che capitano!

Voglio vederti a percorrere un albero usando l'iterazione.

Cosi' come voglio vederti risolvere un sudoku con l'iterazione, visto
che devi comunque memorizzarti tutte le posizioni prima di ogni
deviazione: tanto vale lasciare che lo faccia lo stack.

[Andrea Laforgia]

Post by Roberto Montaruli
Mi cestini un concetto sacrosanto come la ricorsivita' dicendo che e'
poco efficiente nel fattoriale.

Sto cestinando l'uso della ricorsività nel caso del calcolo del fattoriale
perché è estremamente inefficiente (specie se iteri solo 20 volte) e non
semplifica rispetto alla formuletta da usare iterativamente. Se
un'iterazione come quella ti risulta poco chiara, lasciami dire che hai
grossi problemi.

Post by Roberto Montaruli
Si, ma al prezzo di quale codice confuso?

Ripeto il concetto che forse non ti è chiaro: la ricorsività NON è
qualcosa di indispensabile. In termini tecnici si può sostituire
benissimo. E ci sono casi, come quello del fattoriale, in cui vale
assolutamente la pena farlo.

Post by Roberto Montaruli
Voglio vederti a percorrere un albero usando l'iterazione.

Non c'entra con quanto si sta dicendo in questo thread. Non buttarla in
caciara solo perché hai detto una minchiata. A parte il fatto che tra
iterazione e ricorsione, nella navigazione di un albero, la complessità è
la stessa, se hai una struttura dati adeguata (stack con push e pop),
scrivere un codice di navigazione iterativo è ESTREMAMENTE banale. Ma il
punto, come già detto, non è questo. Esistono contesti in cui può essere
più comodo usare l'iterazione della ricorsione e viceversa. Ma si tratta
di comodità e di compromesso con l'efficienza. Nel caso del fattoriale
questo compromesso non si può pagare.

[Programmatore Scarso]

Il 22/01/2010 14.33, Andrea Laforgia ha

Post by Andrea Laforgia
Non c'entra con quanto si sta dicendo in questo thread. Non buttarla in
caciara solo perché hai detto una minchiata. A parte il fatto che tra
iterazione e ricorsione, nella navigazione di un albero, la complessità è
la stessa, se hai una struttura dati adeguata (stack con push e pop),
scrivere un codice di navigazione iterativo è ESTREMAMENTE banale.

La ricorsione è lenta proprio perché
bisogna allocare dati sullo stack.

Creare una struttura dati con stack push
e pop per usare l'iterazione al posto
della ricorsione mi lascia perplesso.


In ogni caso spostare la complessità
sulla struttura dati e poi dire che
l'algoritmo iterativo è semplice mi
sembra arrampicarsi sugli specchi
in quanto la ricorsione è semplice sia
dal lato dell'algoritmo sia della
struttura dati.

Comunque se una buona fetta dello
sviluppo della teoria (e anche pratica)
della programmazione si sta muovendo
verso la ricorsione tramite linguaggi
funzionali (F#, erlang etc...) un motivo
ci sarà.

Per ultimo, dire ad altri che stanno
sparando minchiate e accusarli di
buttarla sulla caciara... mah!?

[Andrea Laforgia]

On Sat, 23 Jan 2010 10:24:53 +0100, Programmatore Scarso

Post by Programmatore Scarso
Creare una struttura dati con stack push
e pop per usare l'iterazione al posto
della ricorsione mi lascia perplesso.

Dimmi i motivi per cui ti lascia perplesso. Avanti, sentiamo,
"Programmatore Scarso". Sei capace di fare le tue affermazioni
firmandoti con nome e congome?

Post by Programmatore Scarso
In ogni caso spostare la complessità
sulla struttura dati

Spiega l'affermazione "spostare la complessità sulla struttura dati"
perché non ha molto senso.

Post by Programmatore Scarso
e poi dire che
l'algoritmo iterativo è semplice

Spiega quel "e poi" perché non si capisce che cosa stai affermando.

Post by Programmatore Scarso
mi
sembra arrampicarsi sugli specchi

Ma io non ho affatto bisogno di arrampicarmi sugli specchi.

Post by Programmatore Scarso
in quanto la ricorsione è semplice sia
dal lato dell'algoritmo sia della
struttura dati.

Ripeto il concetto: la ricorsione per calcolare il fattoriale è, a
tutti gli effetti, la scelta sbagliata, e in termini di algoritmo, e
in termini di semplicità del codice.

Post by Programmatore Scarso
Comunque se una buona fetta dello
sviluppo della teoria (e anche pratica)
della programmazione si sta muovendo
verso la ricorsione tramite linguaggi
funzionali (F#, erlang etc...) un motivo
ci sarà.

A parte il fatto che questo non è vero e cioè non è vero che "una
buona fetta dello sviluppo" si sta spostando sui linguaggi funzionali
(F# è un semplice prodotto di studio e Erlang è usato in contesti
specifici), dimmi qual è il motivo, senza ipotizzare che da qualche
parte ve ne sia uno. I linguaggi funzionali, per tua informazione,
sono molto più che semplice ricorsione.

Post by Programmatore Scarso
Per ultimo, dire ad altri che stanno
sparando minchiate e accusarli di
buttarla sulla caciara... mah!?

E' vero.

[Enrico Franchi]

Post by Andrea Laforgia
Ripeto il concetto: la ricorsione per calcolare il fattoriale è, a
tutti gli effetti, la scelta sbagliata, e in termini di algoritmo, e
in termini di semplicità del codice.

Ni. Era l'implementazione di Roberto ad essere pessima (un buon esempio
di ricorsione naive ed inefficiente). Semmai la questione è che se in un
linguaggio non si ha TCO, verosimilmente *non* si dovrebbero usare
soluzioni ricorsive (se non per ricorsione provatamente piccola).

In particolare se lavori un un linguaggio senza loop dovrai usare
proprio la ricorsione e la dovrai usare "bene", in modo da non pagare
inefficienze non volute. In determinati contesti puoi anche assumere che
la TCO venga fatta anche in C. Tipicamente è così: siamo nel famoso
mondo dell'ottimizzazione ragionevole, vogliamo fidarci che la fa o
meno?

A seconda dei casi vederemo. Io in C il fattoriale non lo implementerei
ricorsivamente, se non a scopo didattico.

Post by Andrea Laforgia
A parte il fatto che questo non è vero e cioè non è vero che "una
buona fetta dello sviluppo" si sta spostando sui linguaggi funzionali
(F# è un semplice prodotto di studio e Erlang è usato in contesti
specifici), dimmi qual è il motivo, senza ipotizzare che da qualche
parte ve ne sia uno.

Guarda, io posso dirti l'aria che respiro io, non so quello che accade
"intorno a te". La diffusione dei linguaggi funzionali è in grossissima
crescita. Qualche tempo fa erano essenzialmente argomento di interesse
fra i gruppi di geeks (oltre che nell'accademia). Essenzialmente si
stava riscoprendo tantissimo questo paradigma. Haskell è stato uno dei
primi linguaggi a farsi una "seconda giovinezza" in questa maniera.

Poi, con Erlang che fa da apripista, si è cominciato a parlare anche in
altri ambiti e ambienti. Nascono nuovi progetti. Finalmente sempre più
persone si sono rese conto di come il modello stateful della
programmazione ad oggetti ha i suoi limiti, specie in presenza di
pesante concorrenza.

Map/reduce di google, etc etc etc.

Post by Andrea Laforgia
I linguaggi funzionali, per tua informazione,
sono molto più che semplice ricorsione.

Di fatto però la ricorsione è l'unico modo "puro" che si ha per
raggiungere la turing-completezza. I loop *necessariamente* hanno
bisogno di variabili modificabili: poi ci *sono* linguaggi funzionali
che hanno i loop, ma l'idea è che lo fanno per "pragmatismo", uscendo
dal modello funzionale per quello specifico costrutto. In pratica è una
forma di ibridizzazione, che va benissimo, figurati.

[Andrea Laforgia]

Post by Enrico Franchi
In particolare se lavori un un linguaggio senza loop dovrai usare
proprio la ricorsione e la dovrai usare "bene"

E' chiaro che mi sto riferendo a linguaggi le cui più diffuse
implementazioni offrono sia la tail call optimization che i loop.

Post by Enrico Franchi
A seconda dei casi vederemo. Io in C il fattoriale non lo implementerei
ricorsivamente, se non a scopo didattico.

Appunto.

Post by Enrico Franchi
Guarda, io posso dirti l'aria che respiro io, non so quello che accade
"intorno a te". La diffusione dei linguaggi funzionali è in grossissima
crescita.

Benissimo (e questo lo so anch'io), ma da qui a dire che "una buona
fetta dello sviluppo" sta passando o è passata ai linguaggi
funzionali, ce ne passa. Nei fatti non è vero. O non è ancora vero.

Comunque torno al punto di partenza: io non critico né la ricorsione
(che mi piace), né i linguaggi funzionali (che mi piacciono).

Quando dico che la gente la "butta in caciara", voglio dire proprio
questo: uno critica un'applicazione della ricorsione e viene presa
come una critica all'intera branca dell'informatica che si occupa
dell'argomento.

Come ho detto nel mio messaggio di partenza, ci sono contesti in cui
usare la ricorsione è più comodo/elegante/conveniente rispetto
all'iterazione e contesti in cui vale il contrario. Il punto non è
questo. Io sto criticando UNA APPLICAZIONE della ricorsione.

[Enrico Franchi]

Post by Andrea Laforgia
E' chiaro che mi sto riferendo a linguaggi le cui più diffuse
implementazioni offrono sia la tail call optimization che i loop.

Che poi dovrebbero essere C/C++ (da questo punto di vista accomunabili,
visto che l'ottimizzatore è probabilmente condiviso). Probabilmente D
(ma con un market share ridicolo). Pascal-like come stanno? FPC e/o
Delphi? C# forse sta cosa la fa... ma non ho da provare.

Java e tutto quello che ci gira sopra non hanno TCO. Python non la ha,
Ruby IMHO non ottimizza quasi nulla.

Post by Andrea Laforgia
Benissimo (e questo lo so anch'io), ma da qui a dire che "una buona
fetta dello sviluppo" sta passando o è passata ai linguaggi
funzionali, ce ne passa. Nei fatti non è vero. O non è ancora vero.

Si, è vero. Era un affermazione forte. Io direi "ritengo probabile che
una fetta considerevole passerà nell'immediato futuro".

Post by Andrea Laforgia
Comunque torno al punto di partenza: io non critico né la ricorsione
(che mi piace), né i linguaggi funzionali (che mi piacciono).
Quando dico che la gente la "butta in caciara", voglio dire proprio
questo: uno critica un'applicazione della ricorsione e viene presa
come una critica all'intera branca dell'informatica che si occupa
dell'argomento.

Beh, ma sappiamo entrambi di chi stiamo parlando.

Post by Andrea Laforgia
Come ho detto nel mio messaggio di partenza, ci sono contesti in cui
usare la ricorsione è più comodo/elegante/conveniente rispetto
all'iterazione e contesti in cui vale il contrario. Il punto non è
questo. Io sto criticando UNA APPLICAZIONE della ricorsione.

Che infatti era una cattiva applicazione, specie in C. Meno male che un
compilatore dovrebbe riuscire comunque ad ottimizzare quella cosa li.
Apparentemente scheme (gambit) ci riesce, per lo meno. E' sempre meno
efficiente di fare le cose come si deve, ma tiene botta.

[Enrico Franchi]

Post by Roberto Montaruli
Mi cestini un concetto sacrosanto come la ricorsivita' dicendo che e'
poco efficiente nel fattoriale.
Lo so anche io che e' poco efficiente, ma considerando che al massimo
iteri una ventina di volte, la cosa e' sopportabile, in cambio di
avere un codice piu' comprensibile.

Non è "poco efficiente" nel fattoriale. E' "poco efficiente" nella tua
implementazione. Un'implementazione come:

(define fact
(lambda (n)
(letrec ((fact-aux
(lambda (acc n)
(if (= n 1)
acc
(fact-aux (* acc n) (- n 1))))))
(fact-aux 1 n))))

e' decisamente efficiente. Sulla mia macchina per fare il fattoriale di
100000 ci mette una decina di secondi. Ora, la mia macchina è
discretamente pompata, ma su una macchina meno veloce arriviamo magari
al minuto, non è li il problema. Poi immagina che ci sia il test per un
valore di innesco non valido, non è che ci interessi ora.

Tra l'altro non ho fatto verifiche su quale scheme sia più veloce *e*
non ho nemmeno provato a vedere altri linguaggi/piattaforme con analoghe
implementazioni. Se vuoi andiamo a vedere.

Viceversa, la "tua implementazione" ci impiegherebbe molto di piu'.
Non fosse per una classica ottimizzazione che scavalca il problema.
Poi incidentalmente la maggior parte dei linguaggi funzionali mette quel
tipo di ottimizzazioni *aggiuntive* rispetto alla TCO perchè la gente
non usa gli accumulatori (come tu stesso dimostri).

Post by Roberto Montaruli
Voglio vederti a percorrere un albero usando l'iterazione.

Si fa in modo piuttosto banale, perchè?
Tra l'altro usando linguaggi un minimo modulari si hanno le strategie di
visita ben incapsulate e si fa con un pratico iteratore. Why?

Post by Roberto Montaruli
Cosi' come voglio vederti risolvere un sudoku con l'iterazione, visto
che devi comunque memorizzarti tutte le posizioni prima di ogni
deviazione: tanto vale lasciare che lo faccia lo stack.

No ascolta, non parliamo di algoritmi naive per fare i sudoku. Se
vogliamo parlare di algoritmi per risolvere i sudoku, visto e
considerato che ci sono, usiamo quelli. Tipicamente a seconda della
piattaforma su cui stai lavorando sceglierai una soluzione marcatamente
ricorsiva oppure una marcatamente iterativa. Ma il problema non è certo
li. Tipicamente vai a fare programmazione a vincoli e amen.

[Enrico Franchi]

Post by Roberto Montaruli
Vorrei vedere come risolvi il sudoku senza usare la ricorsione!

Dipende cosa ho in mano e cosa mi sono costruito.
Ma che cavolo centra? :)