Newsgroup: it.comp.lang.c++
Titolo: algoritmi di ordinamento iterativi e ricorsivi..

Chiedo scusa a tutti per la banale domanda, vorrei sapere se in rete c'e'
qualche buona risorsa che spieghi decentemente e in modo CHIARO gli
algoritmi ordinamento di un vettore (selction sort, bubble sort etc etc)
vorrei sapere perche' il seguente listato non funziona per i numeri
superiori al 7...(perdonatemi l'ignoranza, ma sono alle prime armi con la
programmazione ;) )
forma ricorsiva
#include <iostream.h>
#include <conio.h>
int fatt(int n);
void main(void)
{
 int n,fattoriale;
 clrscr();
 cout << "Vuoi calcolare il fattoriale del numero:";
 cin >> n;
 fattoriale=fatt(n);
 cout << "Il fattoriale del numero " << n << " S " << fattoriale;
 getch();
}
int fatt(int n)
{
 int f;
 if(n<=1) f=1;
 else{
      f=n*fatt(n-1);
     }
 return f;
}
forma iterativa
#include <iostream.h>
#include <conio.h>
int fatt(int n);
void main(void)
{
 int n,fattoriale;
 clrscr();
 cout << "Vuoi calcolare il fattoriale del numero:";
 cin >> n;
 fattoriale=fatt(n);
 cout << "Il fattoriale del numero " << n << " S " << fattoriale;
 getch();
}
int fatt(int n)
{
 int f=1;
 for(int i=1;i<=n;i++) f*=i;
 return f;
}
Un GRAZIE a tutti quelli che mi sapranno e vorranno dare una mano! ;)
CIAoz

Su che piattaforma compili il programma?
Probabilmente la causa e` dovuta all'uso del tipo int
che nella piattaforma che usi non riesce a contenere
i valori generati da n!  n>7.
Usa unsigned long che ti permette di memorizzare valori
piu` grandi.
Paolo
-----------------------------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
-----------------------------------------------------------------

 void main(void)
main deve rstituire un int:
  int main()  
oppure
  int main( int argc, char* argv[] )
	Mauro

 superiori al 7...
Forse perché i tuoi int sono a 16 bit e il fattoriale di 7 non ci entra.
Prova a dichiarare i valori long.
EMG

   int main( int argc, char* argv[] )
e perche' mai il main deve restituire un int?
scusate la banalita delle domande, ma sono veramente alle prime armi! ;)
Ciao

 piu` grandi.
quindi al posto di int n, unsigned long int n. Giusto?
Ciao

 e perche' mai il main deve restituire un int?
Perche' lo dice lo standard.
Il valore restituito da main e' quello che viene poi passato al sistema
operativo (di solito 0 indica successo e  != 0 indica qualce errore).
Non e' necessario mettere una istruzione return ...; alla fine del
main; non metterla equivale a return 0;
C'e' stata recentemente una discussione sullo stesso argomento
in comp.lang.c++.moderated, li puoi trovare altre informazioni.
	Mauro

quindi al posto di int n, unsigned long int n. Giusto?
Esattamente...


e perche' mai il main deve restituire un int?
E` quanto previsto dallo standard.


 main; non metterla equivale a return 0;
Non lo sapevo. Pensavo fosse obbligatorio. Lo dice lo standard?
EMG


Si, paragrafo 3.6.1.5 del CD2 (draft del nov. 1996).  Non e' la
versione definitiva, ma in questa parte non ci dovrebbero essere
variazioni.
Lo dice anche lo Stroustrup 3 ed., paragrafo 3.2
	Mauro

 superiori al 7...(perdonatemi l'ignoranza, ma sono alle prime armi con 
Come molti ti hanno detto dipende dal fato che 8! = 40.320, che supera
32.768 (il massimo per un inero con segno a 16 bit puo' contenere).
Attenzione pero'!
Usando un unsigned long (32 bit) si arriva a 42.294.967.296 che puo'
contenere al massimo 12!
Se non hai necessita' di utilizzare gli interi (ovvero non ti
interessa il risultato esatto) puoi utilizzare i numeri in virgola
mobile.
Con un duble a 64 bit puoi contenere 1.7 * 10^308 (piu' o meno
1 seguito da 308 zeri, se non ricordo male il numero di atomi
nell'universo e' circa 1 seguito da 100 zeri).
Con questo arrivi a 170 fattoriale, ma non so con quale precision
(bisognerebbe fare qualche calcolo).
Con un long duble a 80 bit arrivi a 1.1 * 10^4932.
Circa 1 seguito da 5000 zeri.
Con questo dovresti arrivare al fattoriale di un numero tra 1500
e 2000 (forse meno). Ma a questo punto sono pronto a scommettere
che neanche l'esponente e' piu' significativo.
Come vedi il fattoriale cresce molto velocemente. Una volta mi ero
divertito a cercare di determinare l'ordine di grandezza del
fattoriale ed ero riuscito a dimostrare che e' sicuramente una
funzione super-esponenziale (cresce piu' velocmente di a^n, per
qualsiasi costante a) ma che cresce meno velocemente di n^n.
Una curiosita'. Nessuno sa un modo per conoscere almeno l'ordine di
grandezza di un fattoriale molto grande?
Andrea Polci
--
Andrea Polci    
apo...@geocities.com

Non lo sapevo. Pensavo fosse obbligatorio. Lo dice lo standard?
Si, e vale solo per la main() (ch'io sappia).


 contenere al massimo 12!
E' 4.294.967.296.
EMG

Innanzitutto grazie a tutti per le risposte! ;)
Penso che per il fattoriale passero' ad una variabile di tipo double.Ora
pero' ho un altro prob..;)
ho questo listatino, non riesco a capire perche' funzioni SOLO con array che
arrivano al massimo a 12 elementi...
me la date una mano? ;)
#include <iostream.h>
#include <conio.h>
const int nmax=100;
typedef int T;
typedef T Vettore[nmax];
void leggi_elementi(Vettore,int &);
void visualizza_vett(const Vettore, const int);
void bubble_sort(Vettore, const int);
void scambia_elem(T &, T &);
void main(void){
     int num_elem;
     Vettore v;
     clrscr();
     cout << "Ordinamento di un vettore.Algoritmo di Bubble Sort Ricorsivo";
     leggi_elementi(v,num_elem);
     cout << "\nIl vettore inserito e' cosi' composto:\n";
     visualizza_vett(v, num_elem);
     bubble_sort(v,num_elem);
     cout << "\nOrdinamento completato! Ora il vettore e':\n";
     visualizza_vett(v, num_elem);
     getch();
}
void leggi_elementi(Vettore v, int & num_elem){
     cout << "\n\nDa quanti elementi deve essere formato il vettore";
     cout << "\nche vuoi ordinare? N.B gli elementi devono essere < 100";
     do{
 cout << "\n\nInserisci il numero di elementi del vettore -->";
 cin >> num_elem;
     }while(num_elem>100);
     for(int i=1;i<=num_elem;i++){
     cout << "Inserisci l'elemento v["<< i << "] --> ";
     cin >> v[i];
     }
}
void visualizza_vett(const Vettore v, const num_elem){
     for(int i=1;i<=num_elem;i++){
     cout << v[i] << "-";
     }
}
void bubble_sort(Vettore v, const num_elem){
     if(num_elem<=1) return;
     else{
   for(int j=1;j<=num_elem-1;j++){
  if(v[j]>v[j+1]) scambia_elem(v[j],v[j+1]);
   bubble_sort(v,num_elem-1);
   }
  }
}
void scambia_elem(T & a, T & b){
     T temp;
     temp=a;
     a=b;
     b=temp;
     }
Scusate...ma proprio non riesco a capire! ;)

Scusate...ma proprio non riesco a capire! ;)
Prova a tracciarne l'esecuzione e vedi cosa non funziona.


 Scusate...ma proprio non riesco a capire! ;)
Ciao
*Fabio*
-- 
The entire CHINESE WOMEN'S VOLLEYBALL TEAM all share ONE personality --
and have since BIRTH!!