编写代码实现:幂乘算法

幂乘算法，也称为快速幂算法，是一种高效计算大整数次方的方法。它通过分治策略将指数分解成二进制形式，利用循环和乘法运算减少计算次数。以下是使用Python实现的基本版本：

def power(x, n):
    # 如果n为0，任何数的0次幂都是1
    if n == 0:
        return 1

    # 如果n为负数，先取倒数，然后交换x和1的位置
    if n < 0:
        x = 1 / x
        n = -n

    result = 1  # 初始化结果为1
    while n > 0:
        # 如果n的最后一位是1，将x乘入结果
        if n % 2 == 1:
            result *= x
        # 将x自乘，n除以2
        x *= x
        n //= 2

    return result

# 示例
print(power(2, 10))  # 输出：1024

这个算法的时间复杂度是O(log n)，比直接递归乘法的O(n)效率高得多。

相关问题

根据RL和LR算法原理，编写一个底数、指数、模数均为32比特的模幂实现算法。（RL一个，LR一个）

RL算法：

def mod_pow_RL(a, b, m):
    res = 1
    while b > 0:
        if b % 2 == 1:
            res = (res * a) % m
        a = (a * a) % m
        b //= 2
    return res

在该代码中，变量 a 表示底数，b 表示指数，m 表示模数，变量 res 表示当前的结果。当 b 为奇数时，将 res 乘上 a 并取模；否则，将 a 平方取模。最后返回 res 的值即可。

LR算法：

def mod_pow_LR(a, b, m):
    res = 1
    while b > 0:
        if b & 1:
            res = (res * a) % m
        a = (a * a) % m
        b >>= 1
    return res

在该代码中，变量 a 表示底数，b 表示指数，m 表示模数，变量 res 表示当前的结果。当 b 的二进制位为 1 时，将 res 乘上 a 并取模；否则，将 a 平方取模。最后返回 res 的值即可。

实验题：常见算法时间函数的增长趋势分析 目的：理解常见算法时间函数的增长情况。 内容：编写一个程序 exp1.cpp,对于1~n（n=10）的每个整数n，输出 log2n、√n、n、nlog2n、n²、n3、2”和n！的值。

实验题目要求你分析几种常见的算术运算和递归计算的时间复杂度。这些运算包括对数（log2n）、平方根（√n）、线性（n）、线性对数（nlog2n）、平方（n²）、立方（n³）、常数乘法（2^n），以及阶乘（n!）。这里的关键是理解每种操作随着输入n增加时，它们所需的时间是如何增长的。

1. 对数（log2n）：通常表现为线性的较低次幂，比如O(log n)。这是因为二进制树的高度通常是log(n)，所以查找、分割等操作的次数大致如此。

2. 平方根（√n）：这是一个渐近于线性的操作，因为计算n的平方根所需的步骤数量不会超过n的平方根本身，所以时间复杂度是O(√n)。

3. 线性（n）：这个是最直接的，对于每一个元素的操作都独立执行，所以时间复杂度是O(n)。

4. 线性对数（nlog2n）：这通常是排序或搜索算法的时间复杂度，例如快速排序和二分查找，每次操作后都要缩小一半搜索范围。

5. 平方（n²）：典型的二次操作，如两个数组完全相乘或简单的图形面积计算，所需步骤的数量是n的平方。

6. 立方（n³）：这是立方操作，如三维空间中的体积计算，时间复杂度为三次方。

7. 常数乘法（2^n）：这是一种指数级增长，当n增大时，增长速度非常快，比如计算2的n次方。

8. 阶乘（n！）：如果用循环计算，其时间复杂度也是O(n)，因为需要依次乘到n，但阶乘的增长速度比上述所有更快，因为它包含了所有小于等于n的正整数。

为了实现这个程序，你可以使用C++编写一个循环，对于给定的范围内的每个n，计算并打印这些表达式的值。以下是一个简化的示例代码：

#include <iostream>
#include <cmath>

int main() {
    const int maxN = 10;
    for (int n = 1; n <= maxN; ++n) {
        std::cout << "n = " << n << ": ";
        std::cout << "log2(" << n << ") = " << log2(n) << "\n";
        std::cout << "sqrt(n) = " << sqrt(n) << "\n";
        std::cout << "n = " << n << "\n";
        std::cout << "n * log2(n) = " << n * log2(n) << "\n";
        std::cout << "n^2 = " << n * n << "\n";
        std::cout << "n^3 = " << n * n * n << "\n";
        std::cout << "2^n = " << pow(2, n) << "\n";
        std::cout << "factorial(n) = " << factorial(n) << "\n"; // 自定义阶乘函数
        std::cout << "\n";
    }
    return 0;
}

// 用于计算阶乘的辅助函数
long long factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

运行这段代码，你会看到不同操作在n从1到10的变化趋势。记住，这只是理论上的增长趋势，实际运行时间还会受到具体实现、编译器优化等因素的影响。完成实验后，你可以总结每种运算的典型时间复杂性，并思考它们的实际应用场景。