2

我是一个新手，我知道我在 Internet 上某个地方获得的这个 C 程序（学分：http ://www.geeksforgeeks.org/archives/28 ）可以正常工作。

#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)运行时间的。非常感谢你！

4

5 回答 5

4

请注意，y/2用于计算 temp 的是整数除法。因此，在您评论的问题中，5/2 的结果将是 2，而不是 2.5。

于 2012-06-29T03:44:07.740 回答
3

很难与 Wikipedia 对平方乘幂的解释竞争，但这是我的看法。

答案的关键在于这个公式：

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

这立即回答了“当幂是偶数时做什么”的问题：如果y=2*k，那么你可以先平方x，然后将结果提升到 的幂k。

奇次幂的情况有点复杂：让我们重写

x ^ (2*k+1)

作为

(x ^ 2*k) * x

现在你看到了在那个else分支中发生了什么：他们从奇数中减去 1 使其成为偶数，得到x ^ (y-1)，最后乘以它x。*

现在是时间复杂度：每一步都会减少y一半，所以递归调用的次数是O(Log2(N)).

*实现不会显式地减去1。y相反，它执行 的整数除法y/2，丢弃除法的余数。

于 2012-06-29T03:45:36.020 回答
0 
/* 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-29T03:44:56.453 回答
0

这是通常的 x n算法的一个有点笨拙的实现，它在将 n 减半的同时反复平方 x。奇数n需要额外的处理：在每一步，您检查 n 是否为奇数，然后乘以另一个因子。

Alexander Stepanov 的1 个非常好的关于通用/模板化算法的系列讲座解释了这个系列的起源：

它来自古埃及算法，用于在减半的同时通过重复加法进行乘法运算n。

第一堂课从很简单的东西开始，但要做好。他有有趣的旁白和故事。他从重复加法乘法的递归算法开始，并以各种方式对其进行改进。他到了将 + 替换为 *的地步，以使这个求幂算法在第 2 课（共 4 课）结束时进行。

1：Stepanov 设计并实现了 C++ 的大部分 STL。他是泛型编程的早期发明者/先驱之一。我喜欢他的讲座，并会推荐他们。

这个特定的实现对我来说看起来不太好。

我没有考虑过，但肯定有n比除法更好的方法来处理负奇数。这可能是 C 整数除法的舍入方向的怪癖？（它与算术右移不同，即使在>>对有符号操作数进行算术移位的 C 实现中也是如此。C 标准不要求这样做，但在某些特定的 C 实现中，它确实具有定义的行为。）

此外，变量名称具有误导性：通常您希望y具有与x. 如果您混合使用整数和 FP 变量，请使用n整数之类的名称。

于 2016-03-04T07:03:11.427 回答
-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-03T15:14:26.200 回答