es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Calcula recursivamente si x es una potencia de b.

03 Jun, 2023 Programación

El objetivo es escribir una función recursiva que recibe 2 números enteros no negativos b, x, y devuelve True si hay un entero natural n tal que b**n=x y False en caso contrario. No se permite el uso de operadores matemáticos o bucles, excepto % para determinar si un número es par o impar.
Sin embargo, se pueden utilizar funciones externas que permitan sumar y multiplicar 2 números, y dividir un número por 2. También se pueden escribir funciones auxiliares para utilizar en la función principal.

Esto es lo que tengo hasta ahora, pero solo funciona si b está en forma de 2^y (2,4,8,16, etc.)


def is_power(b, x):
if b == x:
return True
if b > x:
return False
return is_power(add(b, b), x) # la función 'add' simplemente suma 2 números

Además, la complejidad debe ser O(logb * logx).
Gracias.

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para resolver este problema para cualquier valor de b, podemos modificar nuestra función para dividir x por b siempre y cuando sea par, y llevar un seguimiento del exponente n usando una función auxiliar. Una vez que x es un número impar, podemos verificar si es igual a b. Si es así, entonces hemos encontrado el valor de n que satisface b**n=x. De lo contrario, devolvemos False.

    Aquí está el código modificado:

    def is_power(b, x):
    if x == 1:
        return True
    if x % 2 != 0 or x < 1:
        return False
    exp = 1
    while x > 1:
        x = divide(x, b)
        if x % 2 == 0:
            exp = multiply(exp, 2)
        else:
            if x == b:
                return True
            return False
    return False

def divide(a, b):
    if a == b:
        return 1
    return divide(a // 2, b) + divide(a // 2, b) if a % 2 == 0 else divide((a - 1) // 2, b) + divide((a - 1) // 2, b) + b

def multiply(a, b):
    if b == 0:
        return 0
    if b > 0:
        return multiply(add(a, a), divide(b, 2)) if b % 2 == 0 else add(multiply(add(a, a), divide(b - 1, 2)), a)
    return multiply(-a, -b)

def add(a, b):
    return add(a ^ b, (a & b) << 1) if b != 0 else a

    Las funciones externas divide, multiply y add son las funciones externas que se nos permiten utilizar. Tenga en cuenta que la función divide utiliza la recursión para simular la división entera sin utilizar el operador % o bucles. Las funciones multiply y add utilizan operaciones bit a bit para realizar sus respectivas operaciones.

    La complejidad temporal de esta función es O(logb * logx), ya que estamos dividiendo x por b en logb pasos, y las funciones divide, multiply y add tardan cada una O(logx) tiempo.

Comments are closed.