4

真的很尴尬！！我只是不明白下面这个小程序的工作原理，它使用递归来计算数字“a”的幂（“a”提升到“b”的幂）。请解释一下背后使用的逻辑函数。我不明白“x*x”参数、n​​/2 参数和“n 模 2”部分的用法。请为我剖析。

    #include<stdio.h>

    int foo(int,int);

    int main() {
      int a,b;

      printf("Enter number a and its power b\n");
      scanf("%d%d",&a,&b);

      printf("a raised to b is %d", foo(a,b));
      return 0;
    }


    int foo ( int x , int n) {
      int val=1;

      if(n>0) {
        if (n%2 == 1) 
          val = val *x;
        val = val * foo(x*x , n/2);
      }

      return val;
    }
4

3 回答 3

6

这个递归背后的想法是 a b = (a 2 ) b/2和 a b = a(a 2 ) (b-1)/2。

根据 b 是奇数还是偶数（这就是n%2 == 1部分），您可以选择其中一个公式来确保 b/2 或 (b-1)/2 仍然是整数。请注意，n/2您的代码中的实际是 (n-1)/2 表示奇数 n，因为整数除法会自动向下舍入。

由于指数随着每一步而变小，因此递归终止。

于 2013-04-03T06:29:07.277 回答
4

这利用了这样一个事实，例如，幂x^23可以重写为x^16 * x^4 * x^2 * x^1

现在计算x^16相当容易，因为它只是(((x^2)^2)^2)^24 次乘法而不是计算x * x * x * ... 16 times ... * x。

现在请注意，在计算时，x^16您还遇到了计算数字所需的问题。所以最后，你只计算了 7 次乘法而不是 22 次。x^4x^2x^23

现在n % 2和n / 2进入图片的地方是决定 2 的幂是否在 n 中（在我们的示例中，在 23 的二进制表示中是 8 吗？否）。

因此，您只需遍历 n 的位。您每次都将 x 平方，如果您正在查看的当前 n 位中有 1，则将平方数乘以结果。

更新：

以这种方式写出数字的诀窍是以n二进制形式查看。23 是 10111 2，或者我们可以写出位值23 = 1*16 + 0*8 + 1*4 + 1*2 + 1*1。

这意味着x^23 = x^(16 + 4 + 2 + 1)并感谢指数定律，= x^16 * x^4 * x^2 * x^1这是我们开始的。

作为另一个简单的例子：采取x^44. 我们把它写成二进制 101100 2所以我们可以说

44  =  1*32 + 0*16 + 1*8 + 1*4 + 0*2 + 0*1  =  32 + 8 + 4

所以

x^44 = x^(32 + 8 + 4) = x^32 * x^8 * x^4

然后我们计算以下

1:   x^2  = (x)^2                     (from the x we are given)
2:   x^4  = (x^2)^2                   (x^2 from step 1)
3:   x^8  = (x^4)^2                   (x^4 from step 2)
4:   x^16 = (x^8)^2                   (x^8 from step 3)
5:   x^32 = (x^16)^2                  (x^16 from step 4)
6:   x^44 = (x^32) * (x^8) * (x^4)    (using results of steps 2, 3, and 5)
于 2013-04-03T06:30:39.180 回答
1

正如你所说，foo递归工作。为什么不一步一步来呢？假设a==2和b==3，你得到

第一步

int foo ( int x , int n) // x == 2, n==3
{
int val=1;

if(n>0) // n == 3, true!
{
    if (n%2 == 1) //true!
    val = val *x; // val = 1 * 2;
    val = val * foo(x*x , n/2); // next step
}

return val;
}

第二步

int foo ( int x , int n) // x == 4, n==1
{
int val=1;

if(n>0) // n == 1, true!
{
    if (n%2 == 1) //true
    val = val *x; val = 1 * 4;
    val = val * foo(x*x , n/2); // next step -> 4 * ...
}

return val;
}

在第二步中，您返回 4 在第一步中产生

val = val * foo(x*x , n/2); // 2 * 4 in the first step and this equals 8
于 2013-04-03T06:30:18.437 回答