java: convierte un número en otro número mediante operaciones específicas. Necesito ayuda con respecto a esto

CorePress2024-01-24  10

Este fue un problema que encontré recientemente-

Supongamos que tengo 3 números enteros k,m,n. Tengo que llegar a m desde k en un número mínimo de operaciones, y las operaciones posibles son-

Puedes multiplicar k por n.

Puedes disminuir k en 2.

Puedes disminuir k en 1.

Además, estas 3 operaciones se pueden realizar en cualquier orden.

Hay varias formas de probar esto, ya sea recursiva o dinámicamente. Pero encontré una solución interesante para esto que no implementó ninguno de ellos y me cuesta descifrarla. Aquí está el código de referencia:

        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int m = sc.nextInt();
        int n = sc.nextInt();
        int count = 0;
        int x = 0;
        while (k < m) {
            if (m % n == 0) {
                m = m / n;
                count++;
            } else {
                x = (n - (m % n));
                m += (x) / 2 * 2 + (x) % 2;
                count += x / 2 + x % 2;
            }
        }
        if (k > m) {
            count += (k - m) / 2 + (k - m) % 2;
        }
        System.out.println(count);

Bueno, lamento mucho no poder incluir comentarios, ya que no puedo entender este código. ¿Alguien puede revisar el código una vez y explicar cómo funciona realmente? I¡Sería de gran ayuda! (Por cierto, ¡el código funciona bien!)

1

Bueno, uso Intellij, ¡pero nunca había oído hablar de esta característica! ¿Realmente me ayudará a comenzar a comprender este código?

- Abhinav Tahlani

27/03/2021 a las 14:41

1

este código se bloqueará si especifica n=1

- el hutt

27/03/2021 a las 14:48

1

¿No? Mencioné explícitamente que las operaciones se pueden realizar en cualquier orden, lo que hace que este problema sea un desafío. Puedes restar 1 de 2, luego multiplicar por 6, luego restar 1 nuevamente y ¡listo! Llegas a 5.

- Abhinav Tahlani

27/03/2021 a las 15:00

1

Muchas gracias @IntoVoid por publicar los comentarios. En realidad, necesitaba un poco de ayuda para comprender el código :) Estoy algo familiarizado con la estructura de Java, solo necesitaba un poco de información sobre el algoritmo utilizado en el código para resolver el problema.

- Abhinav Tahlani

27/03/2021 a las 15:10

1

entonces lo que hace es: redondea m hasta un múltiplo par de n y luego divide m por n. Luego redondea m hasta un múltiplo par de n y luego lo divide nuevamente. Y así sucesivamente, hasta que m sea menor o igual a k

– en el vacío

27/03/2021 a las 15:22



------------------------------------

Entonces, lo que el algoritmo hace básicamente es lo siguiente:

redondea el m actual hasta un múltiplo par de n, pero solo si m no es ya un múltiplo par de n y luego divide m por n. La primera parte se puede hacer usando la siguiente línea (el resultado será 0 si m ya es un múltiplo par de n):

x = n - (m - 1) % n - 1;

sumando x a m haremos de m un múltiplo par de n o mantendremos m como está si ya es uno.

PERO también podemos usar x para calcular nuestro número de operaciones realizadas.

Puedes multiplicar k por n. Puedes disminuir k en 2. Puedes disminuir k en 1

lo que significa que si aplicamos estas ruarchivos a m entonces deberían ser algo como (corríjame si me equivoco):

Puedes dividir m entre n. Puedes aumentar m en 2. Puedes aumentar m en 1

Así que cada vez que redondeamos m al siguiente múltiplo par de n básicamente decimos que aumentamos el valor de m en 2 'x / 2 veces', pero como esto sólo funciona si x es par, también podríamos decir que aumentamos m en un 1 adicional si x no es par.

Entonces, para este paso necesitamos aumentar nuestro valor de conteo en 'x / 2 + x % 2'

Ahora que hemos hecho esto, necesitamos dividir m entre n (como dicen mis reglas invertidas para m en lugar de k, puedes hacerlo ahora). Después de dividir m por n, necesitamos sumar 1 al contador, ya que realizamos una operación. Y aquí está el código completo condensado:
int count = 0, x;
while (k < m) {
    x = n - (m - 1) % n - 1;
    m = (m + x) / n;
    count += x / 2 + x % 2 + 1;
}
if (k > m) {
    count += (k - m) / 2 + (k - m) % 2;
}
Conclusión:

Este algoritmo realiza todas las operaciones en my no en k comolas reglas sugieren. Por lo tanto, es necesario "revertir" las reglas (como lo hice arriba) Y luego analizas el código con tu "nuevo" conjunto de reglas y descubre que básicamente ya sigue tus "nuevas" conjunto de normas. ¡Coincidencia, no lo creo!



------------------------------------

EDITAR 2: consulte mi otra respuesta para obtener una explicación completa (https://stackoverflow.com/a/66833446/13187363)

EDITAR: Podrías acortar el algoritmo a:

while (k < m) {
    m += n - (m - 1) % n - 1;
    m /= n;
}

pero aún no descubrí el valor del conteo

Anterior: Aquí hay una versión comentada (también reformatear ayuda mucho):

    Scanner sc = new Scanner(System.in);

    int k = sc.nextInt();
    int m = sc.nextInt();
    int n = sc.nextInt();
    
    sc.close();

    int count = 0, x;
    while (k < m) { // Loop while k is smaller then m (meaning our end goal for m is to be smaller or equal to k) (since k will not change inside of the while loop we know that m must change)
        if (m % n == 0) { // Check if m divided by n has NO remainder, if so do the division and increase count by one
            m = m / n;
            count++;
        } else { // If not then...
            // ...subtract the remainder from n and store it in x. X now contains the number which you would need to add to m to make 'm % n == 0' (the if statement) result in true
            x = (n - (m % n));

            // In here we do 'x / 2 * 2' first which will result in even value (rounding x to its lower even value. eg. x = 5 would become 4. Since we are using integers) which we then add to m.
            // Then we also add the missing '1' to m to make the if statement in the next loop result in true
            // I tested this algorithm btw. it does not change the value of x:
            /*
                for (int x = 0; x < 5000; x++) {
                    boolean same = x == (x / 2 * 2 + x % 2);
                    System.out.println(x + " -> " + same);
                }
                Result: same is always true
            */
            m += x / 2 * 2 + x % 2; // This line can be simplified to 'm += x;'
            
            // Then we add half of the x and a 0 or a 1 to count
            count += x / 2 + x % 2;
        }
    }
    if (k > m) { // This will run always if k is not eual to m
        
        // This line is almost equal to this one: 'count += x / 2 + x % 2;'
        // except, that every x was replaced by '(k - m)'
        
        count += (k - m) / 2 + (k - m) % 2;
    }
    
    // Then we print out count
    System.out.println(count);

0

Su guía para un futuro mejor - libreflare
Su guía para un futuro mejor - libreflare