用递归的方式实现快速幂算法

下面为你详细介绍如何用递归方式实现快速幂算法，同时给出相应的代码及解释。

递归思路

递归实现快速幂算法的核心在于依据指数的奇偶性来分情况处理：

• 当指数 n 为偶数时，$a^n$ 可转化为 $(a^{n/2})^2$。
• 当指数 n 为奇数时，$a^n$ 可转化为 $a\times a^{n - 1}$。

代码实现

下面是使用 C++ 实现的递归快速幂算法，代码中添加了详细注释：

#include <iostream>

// 递归实现快速幂函数，计算 a 的 n 次幂
long long recursiveFastPower(long long a, long long n) {
    // 若指数为 0，任何数的 0 次幂都为 1
    if (n == 0) {
        return 1;
    }
    // 若指数为偶数
    if (n % 2 == 0) {
        // 先计算 a 的 n/2 次幂
        long long temp = recursiveFastPower(a, n / 2);
        // 再将结果平方
        return temp * temp;
    } else {
        // 若指数为奇数，先计算 a 的 n - 1 次幂，再乘以 a
        return a * recursiveFastPower(a, n - 1);
    }
}

int main() {
    long long a = 2;  // 底数
    long long n = 13; // 指数

    // 调用递归快速幂函数计算结果
    long long result = recursiveFastPower(a, n);

    // 输出结果
    std::cout << a << " 的 " << n << " 次幂是: " << result << std::endl;

    return 0;
}    

代码解释

1. 函数定义：recursiveFastPower 函数接收两个参数 a 和 n，分别代表底数和指数，返回值为 $a^n$ 的结果。
2. 基准情况：当 n 为 0 时，函数直接返回 1，因为任何数的 0 次幂都是 1。
3. 指数为偶数的情况：若 n 为偶数，先递归计算 $a^{n/2}$ 的结果存储在 temp 中，再将 temp 平方得到最终结果。
4. 指数为奇数的情况：若 n 为奇数，先递归计算 $a^{n - 1}$ 的结果，再乘以 a 得到最终结果。
5. 主函数：在 main 函数里，设定底数 a 和指数 n，调用 recursiveFastPower 函数计算结果并输出。

复杂度分析

• 时间复杂度：$O(log n)$，由于每次递归时指数要么减半，要么减 1，所以递归深度为 $O(log n)$。
• 空间复杂度：$O(log n)$，递归调用栈的深度为 $O(log n)$。

快速幂算法简介

快速幂是一种高效计算幂运算的算法。通常，计算 $a^n$ 时，普通的方法是将 $a$ 连乘 $n$ 次，时间复杂度为 $O(n)$。而快速幂算法可以将时间复杂度降低到 $O(log n)$，大大提高了计算效率，尤其是当 $n$ 非常大的时候。

原理

快速幂算法的核心思想是利用指数的二进制表示。例如，要计算 $a^{13}$，因为 $13$ 的二进制表示是 $1101$，即 $13 = 2^3 + 2^2 + 2^0$，那么 $a^{13} = a^{2^3 + 2^2 + 2^0} = a^{2^3} \times a^{2^2} \times a^{2^0}$。

代码实现

下面是一个用C++实现的快速幂算法的示例代码，包含详细的注释：

#include <iostream>

// 快速幂函数，计算 a 的 n 次幂
long long fastPower(long long a, long long n) {
    long long result = 1;  // 初始化结果为 1
    long long base = a;    // 初始化底数为 a

    // 当指数 n 大于 0 时，继续循环
    while (n > 0) {
        // 如果 n 的二进制表示的最低位是 1
        if (n % 2 == 1) {
            result *= base;  // 将当前的底数乘到结果中
        }
        base *= base;  // 底数平方
        n /= 2;        // 指数右移一位
    }

    return result;
}

int main() {
    long long a = 2;  // 底数
    long long n = 13; // 指数

    // 调用快速幂函数计算结果
    long long result = fastPower(a, n);

    // 输出结果
    std::cout << a << " 的 " << n << " 次幂是: " << result << std::endl;

    return 0;
}

代码解释

1. 函数定义：fastPower 函数接受两个参数 a 和 n，分别表示底数和指数，返回值为 $a^n$ 的结果。
2. 初始化：result 初始化为 1，用于存储最终结果；base 初始化为 a，表示当前的底数。
3. 循环条件：while (n > 0) 表示只要指数 n 大于 0，就继续循环。
4. 判断最低位：if (n % 2 == 1) 用于判断 n 的二进制表示的最低位是否为 1，如果是 1，则将当前的底数 base 乘到结果 result 中。
5. 底数平方：base *= base 表示将底数平方，相当于将指数翻倍。
6. 指数右移：n /= 2 表示将指数右移一位，相当于去掉二进制表示的最低位。
7. 返回结果：循环结束后，返回最终的结果 result。

复杂度分析

• 时间复杂度：$O(log n)$，因为每次循环指数都会减半。
• 空间复杂度：$O(1)$，只使用了常数级的额外空间。

通过这种方式，你可以高效地计算幂运算，尤其是在处理大规模数据时，快速幂算法的优势会更加明显。

快速幂是一种高效计算幂次的算法，它可以将计算 $a^n$ 的时间复杂度从朴素算法的 $O(n)$ 降低到 $O(log n)$。下面为你详细介绍快速幂算法的原理和实现，以及如何在 C++ 中实现它。

原理

快速幂算法的核心思想是利用幂次的二进制分解。假设我们要计算 $a^n$，可以将 $n$ 表示为二进制形式，例如：$n = 2^k_1+2^k_2+\cdots+2^k_m$。那么 $a^n$ 就可以写成 $a^{2^k_1}\times a^{2^k_2}\times\cdots\times a^{2^k_m}$。

例如，计算 $a^{13}$，因为 $13$ 的二进制表示是 $1101$，即 $13 = 2^3 + 2^2 + 2^0$，所以 $a^{13}=a^{2^3}\times a^{2^2}\times a^{2^0}$。

代码实现

以下是使用 C++ 实现快速幂的代码：

#include <iostream>

// 快速幂函数
long long fastPower(long long a, long long n) {
    long long result = 1;
    while (n > 0) {
        if (n & 1) {  // 判断 n 的二进制最后一位是否为 1
            result *= a;
        }
        a *= a;  // a 平方
        n >>= 1;  // n 右移一位，相当于除以 2
    }
    return result;
}

int main() {
    long long a = 2;
    long long n = 13;
    long long ans = fastPower(a, n);
    std::cout << a << " 的 " << n << " 次幂是: " << ans << std::endl;
    return 0;
}

代码解释

1. 初始化结果：result 初始化为 1，用于存储最终结果。
2. 循环条件：当 n > 0 时，继续循环。
3. 判断二进制最后一位：使用 n & 1 判断 n 的二进制最后一位是否为 1，如果是 1，则将当前的 a 乘到 result 中。
4. 平方操作：将 a 平方，即 a *= a。
5. 右移操作：将 n 右移一位，相当于将 n 除以 2。
6. 返回结果：当 n 变为 0 时，循环结束，返回 result。

复杂度分析

• 时间复杂度：$O(log n)$，因为每次循环 n 都会减半。
• 空间复杂度：$O(1)$，只使用了常数级的额外空间。

取模运算

在实际应用中，幂次的结果可能会非常大，为了避免溢出，通常会对结果取模。以下是带有取模运算的快速幂代码：

#include <iostream>

const long long MOD = 1e9 + 7;

// 带取模的快速幂函数
long long fastPowerMod(long long a, long long n) {
    long long result = 1;
    a %= MOD;  // 防止 a 过大
    while (n > 0) {
        if (n & 1) {
            result = (result * a) % MOD;
        }
        a = (a * a) % MOD;
        n >>= 1;
    }
    return result;
}

int main() {
    long long a = 2;
    long long n = 13;
    long long ans = fastPowerMod(a, n);
    std::cout << a << " 的 " << n << " 次幂对 " << MOD << " 取模的结果是: " << ans << std::endl;
    return 0;
}

这个代码在每次乘法操作后都对结果取模，确保结果不会溢出。