1

Me estoy iniciando en la programación competitiva, y hay un problema en el cual hay que calcular el último dígito del factorial de cada número recibido por entrada.

Hasta ahí bien, el problema es que no consigo hacer el programa lo suficientemente óptimo para que tarde menos del tiempo máximo puesto en la página donde lo estoy haciendo.

Imagino que para estos casos habrá algún algoritmo matemático que permita hacerlo en menor tiempo, pero actualmente no tengo idea de algoritmia.

Este es mi código, y no se me ocurre hacerlo más óptimo con mis conocimientos actuales. ¿Alguna sugerencia?

package ultimodigitofactorial;

import java.util.Scanner;

public class UltimoDigitoFactorial {

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int casos = scanner.nextInt();
    int n, factorial;

    for (int i = 0; i < casos; i++) {
        n = scanner.nextInt();
        factorial = 1;
        for (int j = n; j > 1; j--) {
            factorial *= j;
        }
        System.out.println(factorial % 10);
    }
}
}
6
  • Creo que deberías usar un método recursivo. Es más eficiente que el método que usas con un bucle for. Commented el 10 feb. 2019 a las 13:30
  • Usar un método recursivo no va a hacer que sea más eficiente, lo contrario. El código será más bonito, pero será menos eficiente, además de que hará el mismo número de operaciones, le añades que irás haciendo muchas llamadas al método, e incluso pudiendo generar un stack overflow.
    – Reteweee
    Commented el 10 feb. 2019 a las 14:09
  • Creo que te equivocas al asumir que un método recursivo no es eficiente. Además, existen formas de prevenir el stack overflow con métodos recursivos. Te animo a leer: Funciones Factoriales rápidas. El método más rápido de los listados allí es el método Split Recursive, que como su nombre lo indica es un método recursivo. Existe el método los factores primos... Commented el 10 feb. 2019 a las 15:44
  • ... en esta respuesta doy un ejemplo de un método básico para calcular los factores primos. Se puede optimizar mucho más. Te animo a que lo estudies. La recursión es muchas veces mal vista o mal interpretada, pero es una herramienta excelente para optimizar algoritmos. Los lenguajes funcionales, como Erlang, no usan bucles, solo recursión. Commented el 10 feb. 2019 a las 15:48
  • Otra de las cosas a las que te enfrentas con tu algoritmo, es el desbordamiento por el uso de variables int. El máximo valor de un etero positivo en Java es: 2147483647. El número 13! es 6227020800 que ya sobrepasa el máximo valor de un int. Commented el 10 feb. 2019 a las 15:51

2 respuestas 2

3

En este problema en particular te solicitan calcular el último digito del factorial del número, por lo tanto no es necesario calcular el valor del factorial, que ya has visto que lleva demasiado tiempo de procesamiento y/o memoria.

Para resolver el problema, en primer lugar deberías leer sobre aritmética modular.

Dos números son congruentes módulo n si tienen el mismo resto después de dividir a cada uno de ellos por n. Por ejemplo, 9 y 17 son congruentes módulo 4, ya que ambos dan como resto 1 después de dividirlos por 4. 9/4 = 2, resto 1, y 17/4 = 4, resto 1.

Se define el operador módulo (en java se utiliza el símbolo %) para obtener el resto de una división entera. Por ejemplo, si calculamos i = 6 % 4 obtendríamos como resultado que i vale 2, que es el resto de la división entre 6 y 4.

El sistema de numeración que utilizamos es de base 10, por lo tanto, para obtener el último dígito de un número, solamente deberíamos calcular el valor del resto de dividir ese número entre 10. Por ejemplo, para saber el último dígito del número 145, calculamos el resto de la división 145/10, y obtenemos 5. Esto se comprueba fácilmente, ya que 145 = 14*10 + 5.

Ya estamos mas cerca de resolver el problema. Ahora falta ver qué pasa cuando hay una operación de multiplicación. Para el problema del factorial, ya sabes que factorial(n) se calcula como 1*2*...*(n-1)*n. Pero como dice el enunciado, solamente nos interesa el último dígito de este resultado.

De acuerdo a las clases de equivalencia que están en el artículo de wikipedia que enlacé más arriba, resulta ser que para calcular el producto modulo n de dos números, solamente basta con calcular el producto de cada uno de ellos módulo n.

Esto quiere decir, por ejemplo, que si necesitamos calcular el último dígito de 173*265 (que da como resultado 45845, y el último dígito es 5) podemos operar directamente como 173*265 (mod 10), o bien como (173 (mod 10) * 265 (mod 10)) (mod 10). Si haces el cálculo, ambos resultados dan 5. Te invito a que no me creas, y lo compruebes por tí mismo.

En resumen, no es necesario almacenar todo el número si lo único que necesitas es el último dígito. Con almacenar el último dígito de cada producto, y utilizando aritmética modular, puedes calcular el último dígito del factorial de cualquier número, sin necesidad de BigIntegers, en tiempos relativamente cercanos a 0 segundos.

Edito: Agrego el código.

int ultimodigito = 1; 
for(int i = 1; i <= n; i++) {
    ultimodigito = (ultimodigito * i) % 10;
}

Y como dije en los comentarios, el factorial de cualquier número mayor o igual a 5 tiene que terminar en cero porque contiene el producto 5*2. En ese caso, este código es mucho más rápido:

int ultimodigito = 0;
int[] menoresa5 = {1, 1, 2, 6, 4};

if(n > 4) {
    ultimodigito = 0;
} else {
    ultimodigito = menoresa5[n];
}

El arreglo menoresa5 contiene los últimos dígitos de 0! hasta 4!.

6
  • 1
    de hecho si deberías colocarlo, la idea de SO es volverse una biblioteca de preguntas y respuestas de calidad, y si bien tu aporte es muy explicativo; sigue siendo solo teoría
    – user75901
    Commented el 11 feb. 2019 a las 4:11
  • Tal vez, pero implementando el algoritmo es fácil de ver que el último dígito de cualquier n! donde n > 5 es 0, ya que el producto 5*2 multiplica cualquier número por 10. No sé si es una trampa del ejercicio o si no está correctamente explicado en el enunciado.
    – Guille
    Commented el 11 feb. 2019 a las 4:21
  • @Guille, tu respuesta es realmente la que debería ser correcta. Por alguna razón no entendí el enunciado o no le presté atención. Solo escribí un programa que calculara un factorial de manera recursiva. Deberías subir el código para votar tu respuesta como positiva y que se vea primero. Ya que la mía no es la correcta. Saludos. Commented el 11 feb. 2019 a las 8:12
  • @element agregado el código. De cualquier forma, también es probable que tu respuesta, Mauricio, le haya sido útil para resolver el problema.
    – Guille
    Commented el 11 feb. 2019 a las 12:48
  • Muy bien y por eso te doy +1
    – user75901
    Commented el 11 feb. 2019 a las 12:49
0

Como te comenté, a veces la recursión no es muy bien vista o recibida. Pero en realidad es una herramienta muy potente.

Tu algoritmo está bien, es un algoritmo que funciona. Sin embargo, tiene algunos problemas:

  1. El máximo entero positivo representable en Java con el tipo int es 2147483647, el cual es un número de 10 dígitos. Si queremos calcular el valor de 13!, el resultado es 6227020800, el cual tiene 6 unidades de billón, ya se pasa por al menos 4 unidades de billón del máximo int.

Alguien puede sugerir usar un tipo long cuyo máximo es 9223372036854775807. Igual, si deseamos calcular el valor de 21! el resultado es 51090942171709440000, que tiene un dígito más. Por lo tanto usar un long solo nos permite calcular hasta 20!. Nuestro programa así es solo basura.

  1. El método que usas implica como es esperado, multiplicar N*(N-1)(N-2)...*(1), la cual es la definición matemática de un número factorial. Suponiendo que resolvemos el problema 1, el problema al que ahora nos enfrentamos es el de la velocidad al realizar las operaciones aritméticas.

El usar un ciclo for implica iterar desde 1 hasta N-1 (N - 1 veces), en cada iteración i calculamos la multiplicación de Acumulado * (N-i) donde Acumulado es el valor de la multiplicación en la iteración anterior. Cuando i = 1 entonces Acumulado = N, y cuando i = N - 1 entonces (N-i) = 1.

Usar un método recursivo también implica llamar a la función N-1 veces, en eso estamos de acuerdo. Además, si tengo que llamarla 't' veces, debo alojar espacio en memoria para las 't' llamadas, y siendo los números tan grandes, se producirá un stack overflow. En eso estamos de acuerdo.

Sin embargo, no es necesario alojar 't' elementos en memoria, basta alojar 2. Y allí es donde ocurre la magia.

Usaremos lo que se conoce como recursión de cola (tail recursion), de donde cito lo siguiente:

La importancia de recursión de cola es que cuando se realiza una llamada recursiva de cola, la posición de retorno de la función que llama necesita grabarse en el call stack; cuando la función recursiva retorna, continuará directamente a partir de la posición de retorno grabada previamente. Por ello, en compiladores que dan soporte a optimización de recursión de cola, este tipo de recursión ahorra espacio y tiempo.

(Negrillas agregadas por mi)

Siendo que esto no es una clase de Algoritmos, tampoco entraré en detalles. Solo te diré que la recursividad existe con un propósito, y no es precisamente hacer que el código se vea bonito.

Ahora te dejo este ejemplo, no solo para ti, sino para todo S.O. en Español. La idea es que todos aprendamos por la experiencia compartida.

En mi programa he implementado un método recursivo y un método tradicional. En ambos métodos realizo un cálculo de tiempo para mostrar la diferencia de cada uno.

Para resolver el problema del punto 1, usaré la clase BigInteger de Java. Realmente no estoy seguro cuál es valor máximo representable por dicha Clase, pero me permite calcular 5000! sin problemas.

import java.util.Scanner;
import java.math.*;

public class factorialRecursivo {
    //La siguiente función permite usar la recursividad de cola, enviando un
    //parámetro adicional a nuestra función recursiva.
    //No es necesario, pero me gusta que al llamar la función se le pase un solo parámetro. Así el prototipo tiene sentido.
    public static BigInteger factorial(BigInteger N) {
        return factorial_tail(N, BigInteger.ONE); // BigInteger.ONE representa el entero 1
    }
    // Esta función es recursiva de cola, solo almacena 2 valores en memoria
    // el valor de Acc (acumulador) y el valor de N-1 en cada llamada recursiva.
    public static BigInteger factorial_tail(BigInteger N,BigInteger Acc) {
        if(N.compareTo(BigInteger.ZERO) <= 0) {
            return Acc; // Cuando N es cero o negativo
        } else {
            //llamada recursiva
            return factorial_tail(N.subtract(BigInteger.ONE), N.multiply(Acc));
        }
    }

    //Esta función es la forma tradicional de bucle
    public static BigInteger factorialBucle(BigInteger N) {
        if(N.compareTo(BigInteger.ZERO) <= 0) {
            return BigInteger.ONE; // Devuelve 1 si N es cero o negativo
        } else {
            BigInteger acumulado = N;
            int valor = N.intValue(); // usaremos el bucle 'for' con valores 'int'
            for(int i = 1; i < valor; i++) {
                BigInteger index = new BigInteger(String.valueOf(i));
                acumulado = acumulado.multiply(index);
            }
            return acumulado;
        }
    }

    public static void main(String[] args) {
        long timeStart, timeEnd, timeBucle, timeRecursivo;
        Scanner sc = new Scanner(System.in);
        System.out.println("El entero más grande es: " + Integer.MAX_VALUE);
        System.out.println("El long más grande es: " + Long.MAX_VALUE);
        System.out.println("Introduzca un número entero:");
        BigInteger numero = sc.nextBigInteger();
        System.out.println("Introdujo: " + numero);
        System.out.println("LLamada a método tradicional (bucle)");
        timeStart = System.currentTimeMillis();
        BigInteger factBucle = factorialBucle(numero);
        timeEnd = System.currentTimeMillis();
        timeBucle = timeEnd - timeStart;
        System.out.println("LLamada a método recursivo");
        timeStart = System.currentTimeMillis();
        BigInteger factRecursivo = factorial(numero);
        timeEnd = System.currentTimeMillis();
        timeRecursivo = timeEnd - timeStart;
        System.out.println("El factorial de " + numero + " calculado de forma tradicional es " + factBucle);
        System.out.println("El factorial de " + numero + " calculado de forma recursiva es " + factRecursivo);
        System.out.println("El método tradicional tardó "+ timeBucle +" milisegundos.");
        System.out.println("El método recursivo tardó "+ timeRecursivo +" milisegundos.");
    }
}

Espero que esto te ayude a resolver el problema y te aclare las dudas y temores sobre recursividad.

NOTA

Otra forma de optimizar es usar Hilos, pero no está planteado en la pregunta original.

2
  • Mil gracias amigo por hacer la respuesta fácil de comprender, se me quita el miedo de aprender la recursividad, gracias.
    – Reteweee
    Commented el 10 feb. 2019 a las 18:16
  • Si la respuesta es satisfactoria, no olvides marcarla como respuesta válida, asi tu reputación y la mía suben. :) Commented el 10 feb. 2019 a las 18:30

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.