resueltos - factorial de grandes números con cadenas en c++

funciones de cadenas de caracteres en c++

Question

Estoy haciendo un programa factorial con cadenas porque necesito el factorial de números mayor que 250

Intento con:

string factorial(int n){
string fact="1";
for(int i=2; i<=n; i++){
b=atoi(fact)*n;
}
}

Pero el problema es que atoi no funciona. ¿Cómo puedo convertir mi cadena en un número entero?

Y lo más importante ¿Quiero saber si el programa de esta manera funcionará con el factorial de 400, por ejemplo?

Answer 1

Hay un sitio web que calculará factoriales para usted: http://www.nitrxgen.net/factorialcalc.php . Informa:

¡El factorial resultante de 250! tiene 493 dígitos de largo. El resultado también contiene 62 ceros finales (que constituyen el 12.58% del número total)

3232856260909107732320814552024368470994843717673780666747942427112823747555111209488817915371028199450928507353189432926730931712808990822791030279071281921676527240189264733218041186261006832925365133678939089569935713530175040513178760077247933065402339006164825552248819436572586057399222641254832982204849137721776650641276858807153128978777672951913990844377478702589172973255150283241787320658188482062478582659808848825548800000000000000000000000000000000000000000000000000000000000000

Muchos sistemas que usan C ++ double solo funcionan hasta 1E + 308 o más o menos; el valor de 250! es demasiado grande para almacenar en tales números.

Por lo tanto, deberá utilizar algún tipo de biblioteca aritmética de precisión múltiple, ya sea que usted mismo diseñe usando valores de string C ++ o utilizando alguna otra biblioteca de precisión múltiple ampliamente utilizada (por ejemplo, GNU GMP ).

Answer 2

La lógica debería ser:

unsigned int factorial(int n)
{
unsigned int b=1;
for(int i=2; i<=n; i++){
b=b*n;
}
return b;
}

Sin embargo, b puede desbordarse. Entonces puedes usar un tipo integral más grande. O puede usar el tipo de letra flotante, que es impreciso pero puede contener números mucho más grandes. Pero parece que ninguno de los tipos incorporados es lo suficientemente grande.

Answer 3

Puede hacer una compilación atoi agregando c_str (), pero será un largo camino hasta obtener factorial. Actualmente no tienes b alrededor. Y si lo hiciste, todavía multiplicas int por int. Entonces, incluso si eventualmente lo conviertes en una cadena antes de regresar, tu rango sigue siendo limitado. Hasta que no comiences a multiplicar realmente con ASCII o uses una biblioteca bignum, no tiene sentido tener una cadena alrededor.

Answer 4

Si va a resolver factorial para números mayores de alrededor de 12, necesita un enfoque diferente que usar atoi , ya que eso solo le da un entero de 32 bits, y no importa lo que haga, no obtendrá más de 2 mil millones (dar o recibir) de eso. Incluso si duplica el tamaño del número, solo obtendrá 20 o 21.

No es tan difícil (hablando relativamente) escribir una rutina de multiplicación de cuerdas que toma un número pequeño (ish) y multiplica cada dígito y riza los resultados hasta el número (comienza desde la parte posterior del número y lo llena).

Aquí está mi código ofuscado: está escrito intencionalmente, de modo que no puedes simplemente tomarlo y entregarlo como tarea escolar, pero parece funcionar (coincide con el número en la respuesta de Jonathan Leffler), ¡y funciona hasta (al menos) 20000! [sujeto a suficiente memoria].

std::string operator*(const std::string &s, int x)
{
int l = (int)s.length();
std::string r;
r.resize(l);
std::fill(r.begin(), r.end(), ''0'');
int b = 0;
int e = ~b;
const int c = 10;
for(int i = l+e; i != e;)
{
int d = (s[i]-0x30) * x, p = i + b;
while (d && p > e)
{
int t = r[p] - 0x30 + (d % c);
r[p] = (t % c) + 0x30;
d = t / c + d / c;
p--;
}
while (d)
{
r = static_cast<char>((d % c) +0x30)+r;
d /= c;
b++;
}
i--;
}
return r;
}

Answer 5

Su factorial depende de la conversión a int, que se desbordará bastante rápido, por lo que desea poder calcular factoriales grandes de esa manera. Para implementar correctamente la computación en grandes cantidades, es necesario implementar la lógica en cuanto al cálculo en papel, reglas que se tenían en la escuela primaria, pero tratar ints largos como "átomos", no dígitos individuales. Y no lo haga en cadenas, sería dolorosamente lento y lleno de desagradables conversiones

Answer 6

El siguiente código utiliza unsigned double long para calcular dígitos muy grandes.

#include<iostream.h>
int main()
{
long k=1;
while(k!=0)
{
cout<<"/nLarge Factorial Calculator/n/n";
cout<<"Enter a number be calculated:";
cin>>k;
if (k<=33)
{
unsigned double long fact=1;
fact=1;
for(int b=k;b>=1;b--)
{
fact=fact*b;
}
cout<<"/nThe factorial of "<<k<<" is "<<fact<<"/n";
}
else
{
int numArr[10000];
int total,rem=0,count;
register int i;
//int i;
for(i=0;i<10000;i++)
numArr[i]=0;
numArr[10000]=1;
for(count=2;count<=k;count++)
{
while(i>0)
{
total=numArr[i]*count+rem;
rem=0;
if(total>9)
{
numArr[i]=total%10;
rem=total/10;
}
else
{
numArr[i]=total;
}
i--;
}
rem=0;
total=0;
i=10000;
}
cout<<"The factorial of "<<k<<" is /n/n";
for(i=0;i<10000;i++)
{
if(numArr[i]!=0 || count==1)
{
cout<<numArr[i];
count=1;
}
}
cout<<endl;
}
cout<<"/n/n";
}//while
return 0;
}

Salida:

![Large Factorial Calculator
Enter a number be calculated:250
The factorial of 250 is
32328562609091077323208145520243684709948437176737806667479424271128237475551112
09488817915371028199450928507353189432926730931712808990822791030279071281921676
52724018926473321804118626100683292536513367893908956993571353017504051317876007
72479330654023390061648255522488194365725860573992226412548329822048491377217766
50641276858807153128978777672951913990844377478702589172973255150283241787320658
18848206247858265980884882554880000000000000000000000000000000000000000000000000
000000000000][1]

Answer 7

No estoy seguro de por qué está tratando de usar una cadena. ¿Probablemente para ahorrar algo de espacio al no usar un vector entero? Esta es mi solución al usar un vector entero para almacenar factorial e imprimir. ¡Funciona bien con 400 o cualquier número grande para el caso!

//Factorial of a big number
#include<iostream>
#include<vector>
using namespace std;
int main(){
int num;
cout<<"Enter the number :";
cin>>num;
vector<int> res;
res.push_back(1);
int carry=0;
for(int i=2;i<=num;i++){
for(int j=0;j<res.size();j++){
int tmp=res[j]*i;
res[j]=(tmp+carry)%10 ;
carry=(tmp+carry)/10;
}
while(carry!=0){
res.push_back(carry%10);
carry=carry/10;
}
}
for(int i=res.size()-1;i>=0;i--) cout<<res[i];
cout<<endl;
return 0;
}

Ingrese el número: 400 Factorial de 400:

Answer 8

En C ++, el tipo entero más grande es ''long long'', y contiene 64 bits de memoria, ¡así que obviamente no puedes almacenar 250! en un tipo entero. Es una idea inteligente usar cadenas, pero lo que básicamente estás haciendo con tu código es (nunca he usado la función atoi (), así que no sé si incluso funciona con cadenas de más de 1 carácter, pero no lo hace no importa)

1. encubierta la cadena a entero (una cadena que si este código funcionó bien, en un momento contiene el valor de 249)
2. multiplicar el valor de la cadena

Entonces, después de que termines de multiplicar, ni siquiera conviertes el número entero en una cadena. E incluso si lo hicieras, en un momento cuando vuelvas a convertir la cadena en un número entero, tu programa se bloqueará, porque el número entero no podrá contener el valor de la cadena.

Mi sugerencia es usar alguna clase para enteros grandes. Desafortunadamente, no hay uno disponible en C ++, por lo que tendrá que codificarlo usted mismo o buscar uno en Internet. Pero no se preocupe, incluso si lo codifica usted mismo, si piensa un poco, verá que no es tan difícil. Incluso puede usar su idea con las cuerdas, lo que, incluso difícil, no es el mejor enfoque, para este problema, todavía producirá los resultados en el tiempo deseado sin usar demasiada memoria.