功能函數Python

這個函數計算a^b的值並返回它。我的問題是如果m = log（b）最好的情況是它確實有m + 1個交互但是什麼是最壞的情況？以及它進入while循環的次數？功能函數Python

def power(a,b): 
    result=1 
    while b>0: # b is nonzero 
     if b % 2 == 1: 
      result=result*a 
     a=a*a 
     b = b//2 
    return result

來源

2016-11-26 Yasmin12

這不應該起作用。 '結果'未申報，我不明白你用來計算權力的邏輯。 –

嘗試一下，它應該工作。它使用我將其解釋爲代碼的數學原理。 – Yasmin12

當我嘗試它時，我得到這個：'UnboundLocalError：在賦值之前引用的局部變量'結果'。 –

正如@EliSadoff在評論中所述，在函數中需要初始值result。插入線

result = 1

緊接在def後面。該代碼然後工作，這是隱式使用b的二進制表示快速獲取指數的標準方法。（循環不變的是，result * a ** b值保持不變，這說明該算法的有效性。）

最壞的情況是你if b % 2線通過while循環，每次執行。只要b小於2的冪，就會發生這種情況，因此b的二進制表示中的每個數字都是1。 while迴路條件while b>0仍然只檢查m+1次，但每個迴路現在還有一點點要做。

有幾種方法可以加速您的代碼。使用while b而不是while b>0和if b & 1而不是if b % 2 = 1。使用result *= a而不是result = result*a和a *= a而不是a = a*a和b >>= 1而不是b = b // 2。當然，這些都是很小的改進。進一步加速循環的唯一方法是使用非結構化代碼，我相信這在Python中是不可能的。（還有一個a的修改比必要的更多，但沒有好的方法來防止這種情況，而不會跳到循環中。）這個代碼有一些變化，比如一個內部循環保持修改a和b，只要b是偶數，但這並不總是更快。

最後的代碼是那麼

def power(a, b): 
    """Return a ** b, assuming b is a nonnegative integer""" 
    result = 1 
    while b: 
     if b & 1: 
      result *= a 
     a *= a 
     b >>= 1 
    return result

我清理你的代碼一點，以更好地適應PEP8（Python的風格標準）。請注意，在代碼中沒有錯誤檢查，特別是要確保b是非負整數。如果b是一個負整數，而您的返回的結果是錯誤的，我相信我的代碼會無限循環。所以請做錯誤檢查！還要注意，你的代碼說power(0, 0) == 1這是一個非常標準的功能，但仍然讓一些人感到意外。

來源

2016-11-26 23:48:53

功能函數Python

回答

相關問題