0

Problema

Considere todas las combinaciones enteras de ab para 2 ≤ a ≤ 5 y 2 ≤ b ≤ 5:

2^2=4, 23=8, 24=16, 25=32

3^2=9, 33=27, 34=81, 35=243

4^2=16, 43=64, 44=256, 45=1024

5^2=25, 53=125, 54=625, 55=3125

Si luego se colocan en orden numérico, con cualquier repetición eliminada, obtenemos la siguiente secuencia de 15 términos distintos:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

¿Cuántos términos distintos están en la secuencia generada por ab para 2 ≤ a ≤ 100 y 2 ≤ b ≤ 100?

Pregunta

Tengo el algoritmo hecho, lo pruebo con a=5, b=5 y funciona bien, con el numero 100 me sale 422, no estoy seguro que sea correcto ya que el problema me dice que no lo es, pero no detecto error alguno, me podrian echar una mano?

Codigo

    getPowers(100, 100);
    Collections.sort(numbers);
    System.out.println(numbers);
    System.out.println(numbers.size());

}

static List<Integer> numbers = new ArrayList<>();

public static void getPowers(int a, int b){

    double num = 0;

    for (int i = 2; i <=a ; i++) {

        for (int j = 2; j <=b; j++) {

            num = Math.pow(i,j);
            if (!numbers.contains((int)num)) numbers.add((int)num);

        }
    }

}
8
  • Pista: No necesitas calcular todas las potencias para resolver el problema, pero sí puedes ahorrarte mucho procesamiento al indicar qué operaciones no se encuentran ya repetidas. Por ejemplo, la combinación a=2 y b=4 resulta en 2^4=16, que es el mismo resultado de la combinación a=4 y b=2 (4^2=16). Y es esto lo que realmente te pregunta el ejercicio.
    – user227
    el 20 sep. 2017 a las 6:09
  • @LuiggiMendozaJ 2 elevado a 3 son 8, 3 elevado a 2 son 9. el 20 sep. 2017 a las 7:24
  • @PabloLozano obvio, no pruebas ese tipo de combinaciones. Aquí otras que realmente tienen sentido: a=3, b=4 vs a=9, b=2; a=3, b=6 vs a=27, b=2; a=25, b=4 vs a=5, b=8. Considera que piden la cantidad de resultados diferentes del cálculo de las potencias, no piden que las calcules. Usualmente calcularlos todos y luego verificar los diferentes es una solución estilo fuerza bruta.
    – user227
    el 20 sep. 2017 a las 7:29
  • @LuiggiMendozaJ A lo que voy es que para saber el número de resultados diferentes tienes que calcular esos resultados, no veo como ahorrar ese cálculo de potencias el 20 sep. 2017 a las 7:31
  • @PabloLozano no tienes que calcularlos. Otra pista: 4 es 2 * 2. 8 es 2 * 2 * 2. 16 es 2 * 2 * 2 * 2, y 32 es 2 * 2 * 2 * 2 * 2. Si descompones solo las potencias de los números del 2 al 10 que están entre 2 y 100 en sus factores primos, podrás "eliminar" o descontar los valores repetidos. Todos los demás, inevitablemente, serán diferentes, por ejemplo todas las potencias de 11. De esta manera, no necesitas calcular ningún valor para resolver este problema.
    – user227
    el 20 sep. 2017 a las 7:34

1 respuesta 1

1

Debes evaluar bien el tema, yo relice unos cambios a su código los cuales dejo a continuación y describo:

  1. Cambie la estructura de datos a un TreeSet, de esta forma no se tiene que validar si el número ya existe ya que esta estructura ya lo controla y por otro lado los datos se almacenan de forma ordenada en el momento de adicionarlos.

  2. Cambie el tipo de dato a Long que es un número más grande (2^64) y me dan 997 números diferentes.

    public static void getPowers(int a, int b) {

    long num = 0;
    TreeSet<Long> numbers = new TreeSet();
    
    for (int i = 2; i <= a; i++) {
        for (int j = 2; j <= b; j++) {
            num = (long) (Math.pow(i, j));
            numbers.add(num);
        }
    }
    
    System.out.println(numbers.size());
    
    for(Long in : numbers){
        System.out.println(in);
    }
    

    }

  3. Si entiendo el ejercicio debes hacer un ciclo doble de forma que se almacenen todos los calculos de tipo a^b donde 2 <= a <= 100 y 2 <= b <= 100, lo cual daria una serie de la forma 2^2, 2^3, ... 2^100, 3^2, 3^3, ... 3^100, ... 100^2, 100^3, ... 100^100, si esto es así debes pensar en un tipo de dato como BigInteger dado que el número 2^100 es mucho mayor que 2^64 que es el máximo permitido por un tipo de dato Long, y el número más grande a calcular es 100^100

A continuación dejo el código con la implementación cambiando el Tipo de dato por un BigInteger

public static void getPowers(int a, int b) {
        TreeSet<BigInteger> numbers = new TreeSet();
        BigInteger numbi;
        for(int i = 2; i <= a; i++){
            numbi = new BigInteger(String.valueOf(i));
            for(int j = 2; j <= b; j++){
                numbers.add(numbi.pow(j));
            }
        }
        System.out.println(numbers.size());
        for(BigInteger in : numbers){
            System.out.println(in);
        }
    }
3
  • -1 por la propuesta de fuerza bruta. ¿Por qué? Bueno, empieza a ejecutar el código desde ahora, veamos cuándo termina ;)
    – user227
    el 20 sep. 2017 a las 7:36
  • Es casi instantaneo (lo he probado) y la respuesta es 9183 valores distintos. 100* 100 posibles potencias= 10000 cálculos. Eso para un PC es menos de medio segundo. el 20 sep. 2017 a las 7:47
  • Después de ejecutado el código y tomando tiempos la salida fue Hora de inicio : 10:39:14.834 Hora finalización : 10:39:17.363 donde vemos que su tiempo de ejecución es de aproximadamente 3 segundos haciendo impresión del arreglo. Sin imprimir el arreglo los tiempos fueron de Hora de inicio : 10:42:52.996 Hora finalización : 10:42:53.036 que corresponde a 40 milisegundos. Tiempos que considero NO entran en la categoria de "... veamos cuando termina..."
    – isaac
    el 20 sep. 2017 a las 15:46

Tu Respuesta

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

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