algorithm - geeksforgeeks - dynamic programming problems

número mínimo de pasos para reducir el número a 1

Question

Dado cualquier número n, y tres operaciones en n:

1. agregar 1
2. restar 1
3. divide por 2 si el número es par

Quiero encontrar el número mínimo de las operaciones anteriores para reducir n a 1. He intentado el enfoque de programación dinámico, también BFS con poda, pero n puede ser muy grande (10 ^ 300) y no sé cómo hacer mi algoritmo Más rápido. El enfoque codicioso (dividir entre 2 si es par y restar 1 si es impar) tampoco da el resultado óptimo. ¿Existe otra solución?

Answer 1

Me gusta la idea por ossifrage aprensivo de mirar con avidez (para el caso de números impares) si n + 1 o n - 1 parece más prometedor, pero creo que decidir lo que parece más prometedor se puede hacer un poco mejor que mirar el número total de establecer bits

Para un número x ,

bin(x)[:: -1].index(''1'')

indica el número de ceros menos significativos hasta el primero 1. La idea, entonces, es ver si este número es más alto para n + 1 o n - 1 , y elegir el más alto de los dos (muchos ceros consecutivos menos significativos indican más a la mitad consecutiva).

Esto lleva a

def min_steps_back(n):
    count_to_1 = lambda x: bin(x)[:: -1].index(''1'')

    if n in [0, 1]:
        return 1 - n

    if n % 2 == 0:
        return 1 + min_steps_back(n / 2)

    return 1 + (min_steps_back(n + 1) if count_to_1(n + 1) > count_to_1(n - 1) else min_steps_back(n - 1))

Para comparar los dos, corrí

num = 10000
ms, msb = 0., 0.
for i in range(1000):
    n =  random.randint(1, 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999)

    ms += min_steps(n)
    msb += min_steps_back(n)

print ms / num, msb / num

Que salidas

57.4797 56.5844

mostrando que, en promedio, esto usa menos operaciones (aunque no por mucho).

Answer 2

Hay un patrón que le permite conocer el siguiente paso óptimo en tiempo constante. De hecho, puede haber casos en los que haya dos opciones igualmente óptimas: en ese caso, una de ellas puede derivarse en tiempo constante.

Si observa la representación binaria de ny sus bits menos significativos, puede sacar algunas conclusiones sobre qué operación conduce a la solución. En breve:

• si el bit menos significativo es cero, divida por 2
• si n es 3, o los 2 bits menos significativos son 01, entonces reste
• En todos los demás casos: agregar.

Prueba

Si el bit menos significativo es cero, la siguiente operación debería ser la división por 2. En cambio, podríamos intentar 2 adiciones y luego una división, pero luego se puede lograr el mismo resultado en dos pasos: dividir y agregar. Del mismo modo con 2 restas. Y, por supuesto, podemos ignorar los inútiles pasos posteriores de sumar y restar (o viceversa). Entonces, si el bit final es 0, la división es el camino a seguir.

Entonces los patrones restantes de 3 bits son como **1 . Hay cuatro de ellos. Escribamos a011 para denotar un número que termina con los bits 011 y tiene un conjunto de bits prefijados que representarían el valor a :

• a001 : agregar uno daría a010 , después de lo cual debería ocurrir una división: a01 : 2 pasos tomados. No quisiéramos restar uno ahora, porque eso llevaría a a00 , que podríamos haber a00 en dos pasos desde el comienzo (restar 1 y dividir). Así que de nuevo agregamos y dividimos para obtener a1 , y por la misma razón lo repetimos nuevamente, dando: a+1 . Esto tomó 6 pasos, pero conduce a un número al que se podría llegar en 5 pasos (restar 1, dividir 3 veces, agregar 1), así que claramente, no debemos realizar la suma. La resta siempre es mejor.

• a111 : la suma es igual o mejor que la resta. En 4 pasos obtenemos a+1 . La resta y la división daría a11 . Agregar ahora sería ineficiente en comparación con la ruta de adición inicial, por lo que repetimos este restar / dividir dos veces y obtener a en 6 pasos. Si a termina en 0, entonces podríamos haber hecho esto en 5 pasos (agregar, dividir tres veces, restar), si a termina en 1, y luego en 4. Entonces, la suma siempre es mejor.

• a101 : resta y división doble lleva a a1 en 3 pasos. La adición y la división llevan a a11 . Ahora restar y dividir sería ineficiente, en comparación con la ruta de resta, por lo que añadimos y dividimos dos veces para obtener a+1 en 5 pasos. Pero con la ruta de resta, podríamos llegar a esto en 4 pasos. Entonces, la resta siempre es mejor.

• a011 : suma y doble división lleva a a1 . Para obtener a tomaría 2 pasos más (5), para obtener a+1 : uno más (4). Resta, división, resta, división doble lleva a a (5), para obtener a+1 daría un paso más (6). Entonces la adición es al menos tan buena como la resta. Sin embargo, hay un caso que no debe pasarse por alto: si a es 0, entonces la ruta de resta alcanza la solución a la mitad, en 2 pasos, mientras que la ruta de adición toma 3 pasos. Entonces, la adición siempre conduce a la solución, excepto cuando n es 3: luego se debe elegir la resta.

Entonces, para los números impares, el segundo bit determina el siguiente paso (excepto para 3).

Código Python

Esto lleva al siguiente algoritmo (Python), que necesita una iteración para cada paso y, por lo tanto, debe tener una complejidad O (logn) :

def stepCount(n):
    count = 0
    while n > 1:
        if n % 2 == 0:             # bitmask: *0
            n = n // 2
        elif n == 3 or n % 4 == 1: # bitmask: 01
            n = n - 1
        else:                      # bitmask: 11
            n = n + 1
        count += 1
    return count

Véalo ejecutar en repl.it.

Fragmento de JavaScript

Aquí hay una versión donde puede ingresar un valor para n y dejar que el fragmento produzca el número de pasos:

function stepCount(n) {
    var count = 0
    while (n > 1) {
        if (n % 2 == 0)                // bitmask: *0
            n = n / 2
        else if (n == 3 || n % 4 == 1) // bitmask: 01
            n = n - 1
        else                           // bitmask: 11
            n = n + 1
        count += 1
    }
    return count
}

// I/O
var input = document.getElementById(''input'')
var output = document.getElementById(''output'')
var calc = document.getElementById(''calc'')

calc.onclick = function () {
  var n = +input.value
  if (n > 9007199254740991) { // 2^53-1
    alert(''Number too large for JavaScript'')
  } else {
    var res = stepCount(n)
    output.textContent = res
  }
}

<input id="input" value="123549811245">
<button id="calc">Caluclate steps</button><br>
Result: <span id="output"></span>

Tenga en cuenta que la precisión de JavaScript está limitada a alrededor de 10 ¹⁶ , por lo que los resultados serán incorrectos para números más grandes. Utilice la secuencia de comandos de Python para obtener resultados precisos.

Answer 3

Para resolver el problema anterior, puede usar recursividad o bucles Ya se proporciona una respuesta recursiva, así que trataría de dar un enfoque de ciclo while.

Lógica : Debemos recordar que el número múltiplo de 2 siempre tendrá menos bits configurados que aquellos que no son divisibles por 2.

Para resolver tu problema, estoy usando el código de Java. Lo he intentado con pocos números y funciona bien, si no agrega un comentario o edita la respuesta

while(n!=1)
    {
        steps++;
        if(n%2 == 0)
        {
            n=n/2;

        }
        else
        {
            if(Integer.bitCount(n-1) > Integer.bitCount(n+1))
            {
                n += 1;
            }
            else
            {
                n -=1;
            }
        }
    }

    System.out.println(steps);

El código está escrito de una forma muy simple para que todos puedan entenderlo. Aquí n es el número ingresado y los pasos son los pasos necesarios para alcanzar 1

Answer 4

La solución ofrecida por Ami Tavoy funciona si se considera el 3 (agregar 4 produciría 0b100 y count_to_1 es igual a 2, que es mayor que restar 2 para 0b10 y count_to_1 es igual a 1). Puede agregar dos pasos cuando no baje n = 3 para finalizar la solución:

def min_steps_back(n):
count_to_1 = lambda x: bin(x)[:: -1].index(''1'')

if n in [0, 1]:
    return 1 - n

if n == 3:
    return 2

if n % 2 == 0:
    return 1 + min_steps_back(n / 2)

return 1 + (min_steps_back(n + 1) if count_to_1(n + 1) > count_to_1(n - 1) else min_steps_back(n - 1))

Lo siento, sé que haría un mejor comentario, pero recién comencé.