6.1 预排序

例1 检验数组中元素的唯一性

例2 找出数字列表中最常出现的数值

6.2 高斯消去法

前向消去

其中代码for k<-n+1 downto i do使得A[j,i]在最后更新

采用了部分选主元法的前向消去

6.5 霍纳法则和二进制幂

霍纳法则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>

// 使用霍纳法则计算多项式的值
double horner(const std::vector<double>& coefficients, double x) {
    double result = coefficients.back();
    for (int i = coefficients.size() - 2; i >= 0; --i) {
        result = result * x + coefficients[i];
    }
    return result;
}

int main() {
    // 多项式系数，从低次项到高次项排列
    std::vector<double> coefficients = {1, 2, 3};  // 表示多项式 3x^2 + 2x + 1
    double x = 2;  // 要计算多项式值的 x 值

    double polynomialValue = horner(coefficients, x);
    std::cout << "多项式在 x = " << x << " 处的值为: " << polynomialValue << std::endl;

    return 0;
}

二进制幂

从左至右二进制幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>

// 从左至右二进制幂法计算 a 的 n 次方
double powerLeftToRight(double a, const std::vector<int>& binary_n) {
    if (binary_n.empty()) {
        return 1;
    }

    double result = a;
    for (size_t i = 1; i < binary_n.size(); ++i) {
        result = result * result;
        if (binary_n[i] == 1) {
            result = result * a;
        }
    }
    return result;
}

int main() {
    double a = 2;
    // 假设 n 的二进制展开式为 1010（对应十进制的 10）
    std::vector<int> binary_n = {1, 0, 1, 0};

    double result = powerLeftToRight(a, binary_n);
    std::cout << a << " 的 n 次方是: " << result << std::endl;
    return 0;
}

从右至左二进制幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
   #include <iostream>
#include <vector>

// 从右至左二进制幂法计算 a 的 n 次方，n 以二进制展开式数组形式传入
double powerRightToLeft(double a, const std::vector<int>& binary_n) {
    double result = 1;
    double current_power = a;
    for (int bit : binary_n) {
        if (bit == 1) {
            result *= current_power;
        }
        current_power *= current_power;
    }
    return result;
}

int main() {
    double a = 2;
    // 假设 n 的二进制展开式为 1010（对应十进制的 10）
    std::vector<int> binary_n = {1, 0, 1, 0};

    double result = powerRightToLeft(a, binary_n);
    std::cout << a << " 的n次方是: " << result << std::endl;
    return 0;
}

不需要使用二进制展开式的方法

设计一个非递归方法，模仿从右到左二进制幂算法计算a的n次方，但不要明确使用n的二进制表示形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>

// 计算 a 的 n 次方的函数
double power(double a, int n) {
    double result = 1;
    double current_power = a;
    while (n > 0) {
        if (n % 2 == 1) {
            result *= current_power;
        }
        current_power *= current_power;
        n /= 2;
    }
    return result;
}

int main() {
    double a = 2;
    int n = 10;
    double result = power(a, n);
    std::cout << a << " 的 " << n << " 次方是: " << result << std::endl;
    return 0;
}