作業是寫接收2全非負數的遞回函式b, x，回傳True如果有一個自然數n，以便b**n=x和False如果不。我不允許使用任何數學運算子或回圈，除了 % 來確定一個數字是偶數還是奇數。但我確實有可以使用的外部功能。它可以將 2 個數字相加，將 2 個數字相乘，并將一個數字除以 2。我也可以撰寫可以在主函式中使用的輔助函式。
這是我到目前為止所得到的，但它僅適用b于2^y（2,4,8,16 等）的形式
def is_power(b, x):
if b == x:
return True
if b > x:
return False
return is_power(add(b, b), x) # the func 'add' just adds 2 numbers
另外，需要復雜度O(logb * logx)
謝謝。
uj5u.com熱心網友回復：
你基本上可以保持相乘b的b，直到你到達，或傳球，n。
使用輔助函式對此的遞回實作可能如下所示：
def is_power(b, x):
if b == 1: # Check special case
return x == 1
return helper(1, b, x)
def helper(counter, b, x):
if counter == x:
return True
elif counter > x:
return False
else:
return helper(mul(counter, b), b, x) # mul is our special multiplication function
uj5u.com熱心網友回復：
使用您說可以用來乘以 2 個數字的函式，例如：
power = False
result = b
while result < x:
result = yourMultiplyFunction(b,b)
if result == x:
power = True
break
print(power)
問題已編輯（不能使用回圈）：
def powerOf(x,b):
if (b == 1) and (x == 1):
return True
elif ( b==1 ) or (x == 1):
return False
if yourMultiplyFunction(b, b) < x:
return powerOf(x, yourMultiplyFunction(b, b))
elif yourMultiplyFunction(b, b) > x:
return False
return True
uj5u.com熱心網友回復：
O(logb * logx) 的解決方案比簡單的順序搜索慢
您只需執行以下操作即可獲得 O(logx)：
def is_power(b,x,bn=1):
if bn == x: return True
if bn > x: return False
return is_power(b,x,bn*b)
我懷疑目標是比 O(logx) 更快，并且復雜性要求應該類似于 O(log(logx/logb)^2) 相當于 O(log(n)*log(n)) .
要獲得 O(log(n)*log(n)) 解決方案，您可以通過實作輔助函式在 O(log(n)) 時間內將數字提高到給定的冪并使用它在 O(log(n)) 搜索邏輯中。
def raise_power(b,n): # recursive b^n O(logN)
if not n: return 1 # b^0 = 1
if n%2: return b*raise_power(b*b,n//2) # binary decomposition
return raise_power(b*b,n//2) # of power over base
def max_power(b,x):
return 2*max_power(b*b,x) if b<x else 1 # double n until b^n >= x
def is_power(b,x,minp=0,maxp=None): # bin-search on range minp..maxp
if maxp is None: maxp = max_power(b,x) # determine higher bound
if minp>maxp: return False # no matching power
n = (minp maxp)//2 # middle of exponent range
bn = raise_power(b,n) # compute power
if bn == x: return True # match found
if bn > x: return is_power(b,x,minp,n-1) # look in lower sub-range
return is_power(b,x,n 1,maxp) # look in upper sub-range
請注意，您需要將 *、 和 //2 操作轉換為其等效的外部函式以滿足您的賦值要求
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/364970.html