c++ - 递归解决一个数的指数

Question

嘿，我有一个问题，我必须以多种方式解决 x^n。其中之一涉及使用递归公式，这让我很为难。所以我对 x^n 使用递归的方法之一是 n>=0

int power2(int base, int power){
    if (power == 0)
        return 1;
    else if ( power == 1)
        return base;
    else 
        return (base * power2(base, power - 1));
}

这对我来说很有意义所以当我设置 X = 2 和 N = 4 时，它正在降低功率，这起到了计数器的作用，并且将 2x2 功率提高到 3、4*2，功率提高到 2， 8 * 2 = 16。比功率提高到 1，我有一个基本情况，如果功率提高到 1，它只会返回基数。然而，对于我的下一个问题，我必须使用三个公式来解决它。

• x⁰ = 1
• xⁿ 如果 n 是偶数 = [x^n/2]²
• xⁿ 如果 n 是奇数 = x * [x^n/2]²

所以我到目前为止是

int power3(int base, int power){
    if(power == 0){
        return 1;
    }
    else if ( power == 1)
        return base;
    // if power is even
    if (power % 2 == 0){
        return base*(power3(base,(power/2)));
    }
    // if power is odd
    else{
        return 0;
    }
}

所以我只是想让偶数先工作，当我设置 x=2 和 n=4 时它返回 8。这对我来说很有意义，因为当幂为 4/2 时只会循环两次>1。所以我真的想找出一种方法让它再循环一次，同时忠于我给出的公式。当我现在添加奇怪的基本情况时，程序将运行到 n^5 但 n^6返回 32

Answer 1

你对公式的解释有点问题。
x^n if n is even = [x^n/2]2 并不意味着:

base*(power3(base,(power/2))) //meaning x * [x^n/2]

你应该有

(power3(base,(power/2))) * 2

再次查看您的公式，它不正确 even 并且应该是 x^n if n is even = [x^n/2]^2

所以代码:

(power3(base,(power/2))) * (power3(base,(power/2)))

或:

(power3(base * base,(power/2)))

你的整个函数大概应该是这样的:

int power3(int base, int power){
    if(power == 0){
        return 1;
    }
    else if ( power == 1) // you don't really need this case,
        return base;      // power == 0 is enough as base case
        // if power is even
    if (power % 2 == 0){
        return (power3(base * base,(power/2)));
    }
    // if power is odd
    else{
         return base * (power3(base * base,(power/2)));
    }
}

好吧，因为你似乎仍然对奇数幂感到困惑。
您的 power 变量是 int，因此您得到整数除法意味着 3/2 = 1 而不是 1.5(小数点后的所有内容都被截断)。

现在让我们看看函数中的奇怪情况:

return base * (power3(base * base,(power/2)));

假设 base == 4 和 power == 5

return 4 * (power3(4 * 4,(5/2))); // 5/2 evaluates to 2

等同于 return 4 * (power3(4, 5 - 1))然后返回 (power3(4 * 4, 4/2)) 因为我们现在得到一个偶数。

我们基本上只是将这 2 个步骤作为 1 个步骤来执行。我觉得我的解释听起来有点奇怪，但希望它能有所帮助。