Factoriel de n pour n grand

Télécharger le projet
Commenter

Description

Quand on veut calculer le factoriel d'un grand nombre, les algorithmes de base itératifs ou récursifs sont vite dépassés. En effet, lorsque n augmente, n! dépasse rapidement la valeur maximun que peut contenir un mot de mémoire. Admettons une machine dont tous les mots ont la meme taille, par exemple 32 bits : la valeur exacte d'un entier stocké dans un mot ne peut dépasser 2^31, ce qui équivaut a 14!.
Pour n>14, on ne pourra donc ni stocker n!, ni effectuer l'opération (n-1)!*n .

Ce programme vous permettra de calculer jusqu'a 2147! en stockant le résultat du calcul n! dans un tableau dont chaque élément est un chiffre de la décomposition, cadrée à droite, de n! dans une certaine base. Si Base=10^6, n(max)=2^31/Base=2147.

Source / Exemple : 


#include <stdio.h>
#include <iostream.h>
#include <math.h>

#define TAILLE 2147

void fact(int n)
{
int tab[TAILLE];
int k=1;
int m,i,p;
int base=1000000;
int x,y;

//initialisation du tableau de stockage
for(i=0;i<TAILLE;i++) tab[i]=0;
tab[TAILLE-1]=1;

//Calcul des composantes du résultats et stockage ds le tableau
	for(m=1;m<=n;m++)
	{
	p=0;
	
	for(i=1;i<=k;i++)
		{
		x=(p+m*tab[TAILLE-i]); 
		y=x%base;
		p=(x-y)/base;  
		tab[TAILLE-i]=y;
	}
	if(p!=0) tab[TAILLE+1-k]=p;
	k++;
	}

//affichage du résultat
k=0;
while(tab[k]==0) k++;

cout<<tab[k];
for(i=k+1;i<TAILLE;i++) 
{
if (tab[i]<10) cout<<"00000"<<tab[i];
else if (tab[i]<100) cout<<"0000"<<tab[i];
else if (tab[i]<1000) cout<<"000"<<tab[i];
else if (tab[i]<10000) cout<<"00"<<tab[i];
else if (tab[i]<100000) cout<<"0"<<tab[i];
else cout<<tab[i];
}
cout<<endl;
}

void main()
{
int n;
int stop=1;
while(stop==1)
{
cout<<" Valeur de n(<=2147) : ";
cin>>n;

if((n<2148)&&(n>=0)) {cout<<n<<"!= ";fact(n);}
else if(n<0) stop=0;
else cout<<"En base 10^6, 2147! est le plus gros factoriel calculable"<<endl;
}
}
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (nico8)