Cálculo de factoriales grandes en C++

Question

Entiendo que este es un problema clásico de programación y, por lo tanto, quiero dejar claro que no estoy buscando el código como solución, pero agradecería un empujón en la dirección correcta. Estoy aprendiendo C++ y como parte del proceso de aprendizaje estoy intentando algunos problemas de programación. Estoy intentando escribir un programa que trata con números hasta factorial de 1 billón. Obviamente, estos serán números enormes y demasiado grandes para tratar con el uso de operaciones aritméticas normales. Cualquier indicación en cuanto a qué dirección debería tomar para tratar de resolver este tipo de problema sería apreciada.

prefiero tratar de resolver esto sin usar las bibliotecas adicionales, si es posible

Gracias

PS - el problema es que aquí http://www.codechef.com/problems/FCTRL

---

Aquí está el método que utiliza para resolver el problema Esto se logró leyendo los comentarios a continuación:

Solución: el número 5 es un factor primo de cualquier número que termine en cero. Por lo tanto, dividiendo el número factorial por 5, recursivamente, y agregando los cocientes, obtienes el número de ceros finales en el resultado factorial

E.G. - ¡Número de ceros finales en 126! = 31

126/5 = 25 resto 1

25/5 = 5 resto 0

5/5 = 1 resto 0

25 + 5 + 1 = 31

Esto funciona para cualquier valor, solo siga dividiendo hasta que el cociente sea menor que 5

Answer 1

desnatada esta pregunta, no está seguro de si realmente lo hizo bien, pero aquí es una conjetura deductiva:

Primera pregunta - ¿cómo se obtiene un cero en el final del número? Al multiplicar por 10.

¿Cómo se multiplica por 10? ya sea multiplicando por un 10 o por 2 x 5 ...

Entonces, ¡para X! ¿Cuántos 10s y 2x5s tienes ...?

(por suerte 2 & 5 son números primos)

editar: Aquí hay otra sugerencia - No creo que lo que necesita hacer ningún multiplicación. Avísame si necesitas otra pista.

Answer 2

Para comenzar, debe almacenar el número en un tipo de matriz como un st d :: vector (un dígito para cada posición en la matriz) y necesita encontrar un determinado algoritmo que calculará un factorial (tal vez en algún tipo de clase especializada). ;)

Answer 3

Necesita un paquete "big number", ya sea uno que use o uno que escriba usted mismo.

Recomiendo investigar sobre "large number algorithms". Deberá implementar el equivalente de C++ de Java BigDecimal.

Otra forma de verlo es usando el gamma function. No necesita multiplicar todos esos valores para obtener la respuesta correcta.

Answer 4

Sugerencia: es posible que no necesite calcular N! para encontrar la cantidad de ceros al final de N!

Answer 5

Esta no es una buena respuesta a su pregunta ya que la ha modificado un poco de lo que leí originalmente. Pero lo dejaré aquí de todos modos para demostrar la impracticabilidad de tratar de hacer los cálculos por la fuerza bruta principal.

Un mil millones de factoriales estará fuera del alcance de cualquier biblioteca bignum. Tales números requerirán más espacio para representar que casi cualquier persona tiene en RAM. Tendrás que comenzar a buscar los números desde el almacenamiento mientras trabajas en ellos. Hay formas de hacer esto.El guy who recently calculated π out to 2700 billion places usó dicha biblioteca

Answer 6

Para resolver esta pregunta, como dijo Chris Johnson, debe mirar el número de 0.

Los factores de 10 serán 1,2,5,10 en sí. Entonces, ¡puedes revisar cada uno de los números de N! y escríbalos en términos de 2^x * 5^y * 10^z. Descarta otros factores de los números.

Ahora la respuesta será mayor de (x, y) + z.

Una cosa interesante que aprendo de esta pregunta es que siempre es mejor almacenar factoriales de un número en términos de factores primos para facilitar las comparaciones.

De hecho, x^y, hay un método fácil de usar en el algoritmo RSA, que no recuerdo. Intentaré actualizar la publicación si encuentro una.

Answer 7

No utilice el método ingenuo. Si es necesario calcular el factorial, utilizar un algoritmo rápido: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

Answer 8

Creo que debe encontrar una manera de resolver el problema en un pseudo código antes de empezar a pensar en C++ o en cualquier otro idioma. La naturaleza de la pregunta, como algunos han señalado, es más un problema de algoritmo que un problema de C++. Aquellos que sugieren buscar alguna biblioteca oscura te están apuntando en una pendiente resbaladiza, porque aprender a programar es aprender a pensar, ¿no? Encuentre un buen texto de análisis de algoritmo y le servirá bien. En nuestro departamento enseñamos a partir del texto CLRS.

Answer 9

Para calcular grande factorial, puede utilizar este código en C++:

#include<iostream> 
using namespace std; 

long double factorial(int n); 

int main() 
{ 
    int n; 

    cout << "Enter a positive integer: "; 
    cin >> n; 

    cout << "Factorial of " << n << " = " << factorial(n); 

    return 0; 
} 

long double factorial(int n) 
{ 
    if(n > 1) 
     return n * factorial(n - 1); 
    else 
     return 1; 
} 

A medida que el tiempo doble tiene grandes datos 1.7E +/- 308, este código puede realmente funcionar bien !!