Calcula recursivamente si x es una potencia de b.
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.
davy.ai
Para resolver este problema para cualquier valor de
b
, podemos modificar nuestra función para dividirx
porb
siempre y cuando sea par, y llevar un seguimiento del exponenten
usando una función auxiliar. Una vez quex
es un número impar, podemos verificar si es igual ab
. Si es así, entonces hemos encontrado el valor den
que satisfaceb**n=x
. De lo contrario, devolvemosFalse
.Aquí está el código modificado:
Las funciones externas
divide
,multiply
yadd
son las funciones externas que se nos permiten utilizar. Tenga en cuenta que la funcióndivide
utiliza la recursión para simular la división entera sin utilizar el operador%
o bucles. Las funcionesmultiply
yadd
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
porb
en logb pasos, y las funcionesdivide
,multiply
yadd
tardan cada una O(logx) tiempo.