把x提升到n的能力

我是一個新手，我知道這個我在互聯網上得到的C程序（學分：http://www.geeksforgeeks.org/archives/28）工作正常。

把x提升到n的能力

#include<stdio.h> 

float power(float x, int y) 
{ 
    float temp; 
    if(y == 0) 
     return 1; 
    temp = power(x, y/2); 
    if (y%2 == 0) 
     return temp*temp; 
    else 
    { 
     if(y > 0) 
      return x*temp*temp; 
     else 
      return (temp*temp)/x; 
    } 
} 

/* Program to test function power */ 
int main() 
{ 
    float x=2; 
    int y=5; 
    printf("%f", power(x, y)); 
    getchar(); 
    return 0; 
}

我只是想知道如何和爲什麼。我做了我的問題/評論評論我的代碼，這個函數的行後...

float temp; 
if(y == 0) 
    return 1; 
     //this I understand because for instance 2^0 is 1 
temp = power(x, y/2); 
if (y%2 == 0) 
    return temp*temp; 
     //if y is even, eg. 2^4 then 2^2 * 2^2 is still equal to 16 
else 
{ 
    if(y > 0) 
     //this part I don't get anymore. eg. 2^5, then temp=2^(5/2) 
     return x*temp*temp; 
      //2 * 2^(5/2) * 2^(5/2) how? this will become 64 but the answer is 32. 
      //but when I run the program it halts the right answer ie, 32 
    else 
     return (temp*temp)/x; 
}

我請解釋發生了什麼。也許我錯過了一些東西。以及它如何成爲運行時間的O（lg n）。非常感謝你！該y/2用於計算臨時

來源

2012-06-29 First Lady

這是一個遞歸函數 - 谷歌「遞歸」 – Jason

你應該學會調試/斷點/監視/跨過/踏進等調試技術。然後去調試代碼。 –

Alexander Stepanov（C++ STL的設計者）給出了一個以此爲例的系列講座。他解釋了這個問題，並指出這種算法在200BC是古印度數學家所熟知的。看到我的答案的鏈接。 –

注是整數除法。所以在你評論的問題中，5/2的結果將是2，而不是2.5。

來源

2012-06-29 03:44:07 Turix

整數變量的一個更好的變量名稱（如'n'）可能有助於防止這種混淆。 –

/* if y is even and positive, e.g., 5, then floor of y/2 is (y-1)/2, e.g. 4/2 
    then x^((y-1)/2 + (y-1)/2 + 1) = x^y, e.g., x * x^2 * x^2 = x^(1+2+2) = x^5) */ 
if(y > 0) 
    return x*temp*temp; 

/* if y is even and negative, e.g., -5, then floor of y/2 is (y+1)/2, e.g. -4/2 
    then x^((y+1)/2 - (y+1)/2 - 1) = x^y, e.g., x^-1 * x^-2 * x^-2 = x^(-1-2-2) = x^-5) */ 

else 
    return (temp*temp)/x;

對於複雜度爲O（LGN），因爲你是除以2，每次遞歸調用電力之前，你會做LG（N）調用最多。

來源

2012-06-29 03:44:56 perreal

很難與維基百科對exponentiation by squaring的解釋競爭，但這裏是我的看法。

答案的關鍵是這個公式：

a^(b*c) == ((a^b)^c)

這立即回答的問題「時，功率還要做什麼」：如果y=2*k，那麼你可以先廣場x，然後提高結果以k的力量。

奇功率的情況下是一個比較複雜的：讓我們改寫

x^(2*k+1)

爲

(x^2*k) * x

現在你看到的是else分支發生了什麼：他們減一奇數甚至得到x^(y-1)，最後乘以x。 ^*

現在的時間複雜度：每一步降低了y了一半，所以次遞歸調用是由數爲O(Log2(N))。

^*實現不減去 y 1明確。相反，它執行 y/2的整數除法，它丟棄除法的其餘部分。

來源

2012-06-29 03:45:36 dasblinkenlight

斯捷潘諾夫亞歷山大（STL的作者）使用該算法在他的系列講座的例子，所以他最終解釋的地獄吧：P。查看我的答案以獲取鏈接。 –

-1

private int nthPower(int num, int power) 
    { 
     int [] arr = new int[power+1]; 
     arr[0] = 1; // Any number to the power '0' is '1' 
     arr[1] = num; // Any number to the power '1' is num itself. 
     int i =2; 
     //Now in the for loop you just fill the next element in the array 
     // by multiplying the num with its previous result. Once you are out 
     // of loop you have the desired answer in 'i-1' th index. 
     for (i =2; i<=power;i++) 
     { 
      arr[i] = num*arr[i-1]; 
     } 
     return arr[i-1]; //This is your answer 
    }

來源

2016-03-03 15:14:26 vinni

嗨，歡迎來到StackOverflow。請不要將代碼轉儲爲答案。解釋你的思路，以便尋找答案的人可以更好地理解他們在做什麼。謝謝。用於代碼轉儲的 – Cthulhu

downvoted沒有解釋的目的。還有內存泄漏（假設你的意思是C++，作爲C問題的答案）。 –

這是什麼意思？對於OP的算法，你做乘法，而不是'O（log2（n））'。而且你不需要任何數組。爲我的糟糕算法和糟糕的實現留下了我的失望。 –

這是一個有些-笨重執行通常的X ^Ñ算法，它反覆正方形X而減半的n。奇數n需要額外的處理：在每一步，你檢查n是否是奇數，並乘以另一個因子。

非常好的lecture series on generic/templated algorithms解釋這其中的由來：

這是來自古埃及的算法而減半n重複加入相乘。

第一堂課開始具有相當簡單的東西，但得到很好的。他有有趣的旁白和故事。他從遞歸算法開始，通過重複加法進行乘法運算，並以各種方式對其進行細化。他得到了replacing + with * to make this exponentiation algo near the end of lecture 2 (of 4)。

1：Stepanov設計並實現了很多C++的STL。他是泛型編程的早期發明者/先驅之一。我喜歡他的講座，並會推薦他們。

這個特殊的實現對我來說並不好看。

我還沒有想過這個問題，但肯定有一個更好的方式來處理負奇n不是分歧。這可能是C的整數除法舍入方向的怪癖嗎？（這是從算術右移不同，即使是在C實現其做一個符號操作數的算術移位在所有的>>。C標準不要求，但在某些特定的C實現它確實有定義的行爲。）

此外，變量名是誤導：通常你會期望y具有相同類型x。如果你正在混合整數和FP變量，請使用整數等名稱，如n。

來源

2016-03-04 07:03:11

把x提升到n的能力

回答

相關問題