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
