# Algorithms_4th学习: 基本算法模型
·
ASCII 直方图（Histogram）详解
一、程序做了什么
把一堆数据按区间分组统计，然后用 ## 字符在控制台画出柱状图。
输入: N=5, l=0, r=1, 数据: 0.1 0.15 0.3 0.55 0.72 0.91 0.05 0.88
输出:
##
##
## ##
## ## ## ##
-------- -------- -------- -------- --------
3 1 1 1 2
二、整体流程
三、第一步：划分区间
对应代码
double width = (r - l) / N; // 每个区间的宽度
例子：N=5, l=0, r=1
width = 1 − 0 5 = 0.2 \text{width} = \frac{1 - 0}{5} = 0.2 width=51−0=0.2
产生 5 个区间：
区间编号 k: 0 1 2 3 4
范围: [0, 0.2) [0.2, 0.4) [0.4, 0.6) [0.6, 0.8) [0.8, 1.0)
数轴:
0 0.2 0.4 0.6 0.8 1.0
|------|------|------|------|------|
k=0 k=1 k=2 k=3 k=4
注意最后一个区间是左闭右开 [ 0.8 , 1.0 ) [0.8, 1.0) [0.8,1.0)，值恰好等于 r r r 的数据会被忽略。
四、第二步：数据分桶（统计频次）
核心问题
给一个数据 val，如何快速判断它落在第几个区间？
公式
k = ⌊ val − l width ⌋ k = \lfloor \frac{\text{val} - l}{\text{width}} \rfloor k=⌊widthval−l⌋
就是算 val 离左端点 l 有多远，除以区间宽度，取整数部分。
对应代码
while (std::cin >> val) {
if (val >= l && val < r) { // 先检查是否在总范围内
int k = (int)((val - l) / width); // 算区间编号
if (k >= N) k = N - 1; // 防止浮点精度越界
counts[k]++; // 对应区间计数 +1
}
}
手算演示（N=5, l=0, r=1, width=0.2）
val=0.10: k = (int)(0.10 / 0.2) = (int)(0.5) = 0 --> counts[0]++
val=0.15: k = (int)(0.15 / 0.2) = (int)(0.75) = 0 --> counts[0]++
val=0.30: k = (int)(0.30 / 0.2) = (int)(1.5) = 1 --> counts[1]++
val=0.55: k = (int)(0.55 / 0.2) = (int)(2.75) = 2 --> counts[2]++
val=0.72: k = (int)(0.72 / 0.2) = (int)(3.6) = 3 --> counts[3]++
val=0.91: k = (int)(0.91 / 0.2) = (int)(4.55) = 4 --> counts[4]++
val=0.05: k = (int)(0.05 / 0.2) = (int)(0.25) = 0 --> counts[0]++
val=0.88: k = (int)(0.88 / 0.2) = (int)(4.4) = 4 --> counts[4]++
最终 counts 数组：
counts[0] = 3 区间 [0.0, 0.2) 有 0.10, 0.15, 0.05
counts[1] = 1 区间 [0.2, 0.4) 有 0.30
counts[2] = 1 区间 [0.4, 0.6) 有 0.55
counts[3] = 1 区间 [0.6, 0.8) 有 0.72
counts[4] = 2 区间 [0.8, 1.0) 有 0.91, 0.88
数据落入区间的过程图
五、为什么要 if (k >= N) k = N - 1
浮点数计算有精度误差。比如：
val = 0.9999999999999999, width = 0.2
(val - l) / width = 4.999999999999999
(int)(4.999999999999999) = 4 --> 正常
但如果精度恰好让结果变成 5.000000000000001:
(int)(5.000000000000001) = 5 --> 越界! 数组只有 0~4
加上 if (k >= N) k = N - 1 就能兜底，把这种边界情况归入最后一个区间。
六、第三步：找最大计数
对应代码
int max_count = *std::max_element(counts.begin(), counts.end());
std::max_element 返回一个迭代器（指针），指向最大元素。前面加 * 取出它的值。
本例中
counts = {3, 1, 1, 1, 2}
max_count = 3
找最大值是为了后面归一化——让最高的柱子刚好占满 10 行。
七、第四步：画直方图（最烧脑的部分）
思路
用文本模拟柱状图，从上往下逐行打印。每一行判断每个柱子在这一行该不该画 ##。
对应代码
int bar_height = 10; // 最高柱子占 10 行
for (int row = bar_height; row >= 1; row--) { // 从第10行画到第1行
for (int k = 0; k < N; k++) { // 每行遍历所有区间
int bar = (max_count > 0)
? (counts[k] * bar_height + max_count - 1) / max_count
: 0;
std::cout << (bar >= row ? " ## " : " "); // 够高就画，不够就空
}
std::cout << std::endl;
}
归一化公式详解
int bar = (counts[k] * bar_height + max_count - 1) / max_count;
这是向上取整的整数除法。等价于数学上的：
bar = ⌈ counts [ k ] × bar_height max_count ⌉ \text{bar} = \lceil \frac{\text{counts}[k] \times \text{bar\_height}}{\text{max\_count}} \rceil bar=⌈max_countcounts[k]×bar_height⌉
作用：把 counts[k] 映射到 0~10 的高度。最大的 count 一定映射到 10。
手算本例的 bar 值
bar_height = 10, max_count = 3：
k=0: counts=3 bar = ceil(3*10/3) = ceil(10) = 10
k=1: counts=1 bar = ceil(1*10/3) = ceil(3.33) = 4
k=2: counts=1 bar = ceil(1*10/3) = ceil(3.33) = 4
k=3: counts=1 bar = ceil(1*10/3) = ceil(3.33) = 4
k=4: counts=2 bar = ceil(2*10/3) = ceil(6.67) = 7
用整数公式验证 k=1：
(1 * 10 + 3 - 1) / 3 = 12 / 3 = 4 (整数除法，正确)
逐行绘制过程
bar 值: {10, 4, 4, 4, 7}
判断规则：bar >= row 时画 ##，否则画空格。
row=10: 10>=10? Y 4>=10? N 4>=10? N 4>=10? N 7>=10? N
##
row=9: 10>=9? Y 4>=9? N 4>=9? N 4>=9? N 7>=9? N
##
row=8: 10>=8? Y 4>=8? N 4>=8? N 4>=8? N 7>=8? N
##
row=7: 10>=7? Y 4>=7? N 4>=7? N 4>=7? N 7>=7? Y
## ##
row=6: 10>=6? Y 4>=6? N 4>=6? N 4>=6? N 7>=6? Y
## ##
row=5: 10>=5? Y 4>=5? N 4>=5? N 4>=5? N 7>=5? Y
## ##
row=4: 10>=4? Y 4>=4? Y 4>=4? Y 4>=4? Y 7>=4? Y
## ## ## ## ##
row=3: 10>=3? Y 4>=3? Y 4>=3? Y 4>=3? Y 7>=3? Y
## ## ## ## ##
row=2: 10>=2? Y 4>=2? Y 4>=2? Y 4>=2? Y 7>=2? Y
## ## ## ## ##
row=1: 10>=1? Y 4>=1? Y 4>=1? Y 4>=1? Y 7>=1? Y
## ## ## ## ##
最终效果
##
##
##
## ##
## ##
## ##
## ## ## ##
## ## ## ##
## ## ## ## ##
## ## ## ## ##
---- ---- ---- ---- ----
3 1 1 1 2
八、向上取整的整数除法
为什么不直接用 counts[k] * 10 / 3
C++ 整数除法是向下取整（截断）：
普通整数除法（向下取整）:
1 * 10 / 3 = 10 / 3 = 3 (实际 3.33，截断成 3)
向上取整的整数除法:
(1 * 10 + 3 - 1) / 3 = 12 / 3 = 4 (把 3.33 变成 4)
通用公式
对正整数 a a a 和 b b b：
⌈ a b ⌉ = a + b − 1 b （整数除法） \lceil \frac{a}{b} \rceil = \frac{a + b - 1}{b} \quad \text{（整数除法）} ⌈ba⌉=ba+b−1（整数除法）
为什么成立：
a 能整除 b 时: a=6, b=3 --> (6+3-1)/3 = 8/3 = 2 (正确，6/3=2)
a 不能整除 b 时: a=7, b=3 --> (7+3-1)/3 = 9/3 = 3 (正确，ceil(7/3)=3)
a=8, b=3 --> (8+3-1)/3 = 10/3 = 3 (正确，ceil(8/3)=3)
加上 b − 1 b-1 b−1 的效果是：如果有余数，就把商"推"上去一个。
九、打印分隔线和计数
对应代码
// 分隔线
for (int k = 0; k < N; k++) std::cout << "----";
std::cout << std::endl;
// 各区间的原始计数
for (int k = 0; k < N; k++) {
std::cout << " " << counts[k] << " ";
}
std::cout << "\n（各区间计数）" << std::endl;
每个区间占 4 个字符宽度（---- 和 ## 或 都是 4 字符），保持对齐。
十、从上往下画 vs 从下往上画
为什么要从上往下（row 从大到小）
控制台输出只能从上往下逐行打印，不能回头修改已经打印的行。
如果从 row=1 开始画，最底部会先出现，柱子就倒过来了。
类比
想象你在纸上画柱状图：
你实际画的顺序（从下往上叠方块）: 程序打印的顺序（从上往下逐行）:
第3步画 -> ## 第1行打印 -> ##
第2步画 -> ## ## 第2行打印 -> ## ##
第1步画 -> ## ## ## 第3行打印 -> ## ## ##
--------- ---------
虽然画的方向相反，但最终结果一样。程序通过先判断每行该画什么，再打印来实现。
十一、完整运行示例
输入
5 0 1
0.1
0.15
0.3
0.55
0.72
0.91
0.05
0.88
第一行 5 0 1 是参数（5个区间，范围 0 到 1），后面每行一个数据值。
处理过程
+-------+-------------------+--------+-----------+
| 数据 | (val-l)/width | k | 区间 |
+-------+-------------------+--------+-----------+
| 0.10 | 0.10/0.2 = 0.50 | 0 | [0, 0.2) |
| 0.15 | 0.15/0.2 = 0.75 | 0 | [0, 0.2) |
| 0.30 | 0.30/0.2 = 1.50 | 1 | [0.2,0.4) |
| 0.55 | 0.55/0.2 = 2.75 | 2 | [0.4,0.6) |
| 0.72 | 0.72/0.2 = 3.60 | 3 | [0.6,0.8) |
| 0.91 | 0.91/0.2 = 4.55 | 4 | [0.8,1.0) |
| 0.05 | 0.05/0.2 = 0.25 | 0 | [0, 0.2) |
| 0.88 | 0.88/0.2 = 4.40 | 4 | [0.8,1.0) |
+-------+-------------------+--------+-----------+
counts = {3, 1, 1, 1, 2}
max_count = 3
bar = {10, 4, 4, 4, 7}
输出
===== 直方图 =====
##
##
##
## ##
## ##
## ##
## ## ## ##
## ## ## ##
## ## ## ## ##
## ## ## ## ##
---- ---- ---- ---- ----
3 1 1 1 2
（各区间计数）
十二、Godbolt 上的输入方式
在 Godbolt 中，把所有输入放在 Stdin 框里，一次性粘贴：
5 0 1
0.1
0.15
0.3
0.55
0.72
0.91
0.05
0.88
不需要按 Ctrl+D，Godbolt 会自动在数据末尾发送 EOF。
1.1.33 矩阵库（Matrix Library）
思路理解
线性代数中的基本运算：
向量点积（两个向量对应元素相乘再求和）：
dot ( x , y ) = ∑ i x i ⋅ y i \text{dot}(\mathbf{x}, \mathbf{y}) = \sum_{i} x_i \cdot y_i dot(x,y)=i∑xi⋅yi
矩阵乘法（ m × n m \times n m×n 乘以 n × p n \times p n×p 得 m × p m \times p m×p）：
C [ i ] [ j ] = ∑ k A [ i ] [ k ] ⋅ B [ k ] [ j ] C[i][j] = \sum_{k} A[i][k] \cdot B[k][j] C[i][j]=k∑A[i][k]⋅B[k][j]
矩阵转置（行列互换）：
A T [ i ] [ j ] = A [ j ] [ i ] A^T[i][j] = A[j][i] AT[i][j]=A[j][i]
矩阵×向量：
( b ) i = ∑ j A [ i ] [ j ] ⋅ x j (\mathbf{b})_i = \sum_{j} A[i][j] \cdot x_j (b)i=j∑A[i][j]⋅xj
向量×矩阵：
( b ) j = ∑ i y i ⋅ A [ i ] [ j ] (\mathbf{b})_j = \sum_{i} y_i \cdot A[i][j] (b)j=i∑yi⋅A[i][j]
C++ 完整代码
#include <iostream>
#include <vector>
#include <cassert>
#include <iomanip>
// 类型别名，让代码更简洁
using Vec = std::vector<double>;
using Mat = std::vector<std::vector<double>>;
// ==============================
// 向量点积：x · y = Σ(x[i] * y[i])
// ==============================
double dot(const Vec& x, const Vec& y) {
assert(x.size() == y.size()); // 两向量必须等长
double sum = 0.0;
for (size_t i = 0; i < x.size(); i++) {
sum += x[i] * y[i]; // 对应元素相乘累加
}
return sum;
}
// ==============================
// 矩阵乘矩阵：C = A × B
// A 是 m×n，B 是 n×p，C 是 m×p
// ==============================
Mat mult_mat_mat(const Mat& A, const Mat& B) {
size_t m = A.size(); // A 的行数
size_t n = A[0].size(); // A 的列数（= B 的行数）
size_t p = B[0].size(); // B 的列数
assert(B.size() == n); // 维度匹配检查
// 初始化结果矩阵 C，全为 0
Mat C(m, Vec(p, 0.0));
for (size_t i = 0; i < m; i++) {
for (size_t j = 0; j < p; j++) {
for (size_t k = 0; k < n; k++) {
// C[i][j] += A[i][k] * B[k][j]
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
// ==============================
// 矩阵转置：A^T[i][j] = A[j][i]
// ==============================
Mat transpose(const Mat& A) {
size_t m = A.size();
size_t n = A[0].size();
// 结果是 n×m 的矩阵
Mat AT(n, Vec(m));
for (size_t i = 0; i < m; i++) {
for (size_t j = 0; j < n; j++) {
AT[j][i] = A[i][j]; // 行列互换
}
}
return AT;
}
// ==============================
// 矩阵×向量：b = A × x
// A 是 m×n，x 是长度 n，b 是长度 m
// ==============================
Vec mult_mat_vec(const Mat& A, const Vec& x) {
size_t m = A.size();
size_t n = A[0].size();
assert(x.size() == n);
Vec b(m, 0.0);
for (size_t i = 0; i < m; i++) {
for (size_t j = 0; j < n; j++) {
b[i] += A[i][j] * x[j];
}
}
return b;
}
// ==============================
// 向量×矩阵：b = y × A
// y 是长度 m，A 是 m×n，b 是长度 n
// ==============================
Vec mult_vec_mat(const Vec& y, const Mat& A) {
size_t m = A.size();
size_t n = A[0].size();
assert(y.size() == m);
Vec b(n, 0.0);
for (size_t j = 0; j < n; j++) {
for (size_t i = 0; i < m; i++) {
b[j] += y[i] * A[i][j];
}
}
return b;
}
// 工具函数：打印矩阵
void print_mat(const Mat& M) {
for (const auto& row : M) {
for (double v : row)
std::cout << std::setw(8) << std::fixed << std::setprecision(2) << v;
std::cout << "\n";
}
}
// 工具函数：打印向量
void print_vec(const Vec& v) {
std::cout << "[";
for (size_t i = 0; i < v.size(); i++) {
std::cout << std::fixed << std::setprecision(2) << v[i];
if (i + 1 < v.size()) std::cout << ", ";
}
std::cout << "]\n";
}
int main() {
// === 测试点积 ===
Vec x = {1, 2, 3};
Vec y = {4, 5, 6};
std::cout << "点积 [1,2,3]·[4,5,6] = " << dot(x, y) << "\n";
// 期望：1*4 + 2*5 + 3*6 = 32
// === 测试矩阵乘法 ===
Mat A = {{1, 2}, {3, 4}};
Mat B = {{5, 6}, {7, 8}};
std::cout << "\nA × B =\n";
print_mat(mult_mat_mat(A, B));
// 期望：[[19,22],[43,50]]
// === 测试转置 ===
Mat C = {{1, 2, 3}, {4, 5, 6}};
std::cout << "\n转置 [[1,2,3],[4,5,6]] =\n";
print_mat(transpose(C));
// 期望：[[1,4],[2,5],[3,6]]
// === 测试矩阵×向量 ===
Vec v = {1, 2};
std::cout << "\n[[1,2],[3,4]] × [1,2] = ";
print_vec(mult_mat_vec(A, v));
// 期望：[5, 11]
// === 测试向量×矩阵 ===
std::cout << "[1,2] × [[1,2],[3,4]] = ";
print_vec(mult_vec_mat(v, A));
// 期望：[7, 10]
return 0;
}
向量与矩阵运算详解
目录
一、向量点积（Dot Product）
定义
两个等长向量，对应元素相乘再求和，结果是一个标量（单个数字）。
x ⃗ ⋅ y ⃗ = ∑ i = 0 n − 1 x i ⋅ y i \vec{x} \cdot \vec{y} = \sum_{i=0}^{n-1} x_i \cdot y_i x⋅y=i=0∑n−1xi⋅yi
对应代码
double dot(const Vec& x, const Vec& y) {
assert(x.size() == y.size()); // 两向量必须等长
double sum = 0.0;
for (size_t i = 0; i < x.size(); i++) {
sum += x[i] * y[i]; // 对应元素相乘累加
}
return sum;
}
手算演示
x = [1, 2, 3]
y = [4, 5, 6]
点积 = 1*4 + 2*5 + 3*6
= 4 + 10 + 18
= 32
逐步累加过程
+------+------+------+---------+---------+
| i | x[i] | y[i] | x[i]*y[i] | sum |
+------+------+------+---------+---------+
| 初始 | - | - | - | 0 |
| 0 | 1 | 4 | 4 | 4 |
| 1 | 2 | 5 | 10 | 14 |
| 2 | 3 | 6 | 18 | 32 |
+------+------+------+---------+---------+
结果: 32
ASCII 图示
x: [ 1 , 2 , 3 ]
| | | 对应位置相乘
y: [ 4 , 5 , 6 ]
| | |
v v v
1*4 2*5 3*6
= 4 =10 =18
\ | /
\ | / 全部加起来
v v v
4+10+18 = 32 --> 一个数字
二、矩阵乘矩阵
定义
A A A 是 m × n m \times n m×n 矩阵， B B B 是 n × p n \times p n×p 矩阵，结果 C C C 是 m × p m \times p m×p 矩阵。
C [ i ] [ j ] = ∑ k = 0 n − 1 A [ i ] [ k ] ⋅ B [ k ] [ j ] C[i][j] = \sum_{k=0}^{n-1} A[i][k] \cdot B[k][j] C[i][j]=k=0∑n−1A[i][k]⋅B[k][j]
一句话理解：C 的第 i 行第 j 列 = A 的第 i 行 点乘 B 的第 j 列。
维度匹配规则
A: m × [n] A 的列数
B: [n] × p 必须等于 B 的行数
C: m × p 结果的大小
对应代码
Mat mult_mat_mat(const Mat& A, const Mat& B) {
size_t m = A.size(); // A 的行数
size_t n = A[0].size(); // A 的列数
size_t p = B[0].size(); // B 的列数
assert(B.size() == n); // B 的行数必须等于 A 的列数
Mat C(m, Vec(p, 0.0)); // 结果矩阵，m行p列，初始全0
for (size_t i = 0; i < m; i++) { // 遍历 C 的每一行
for (size_t j = 0; j < p; j++) { // 遍历 C 的每一列
for (size_t k = 0; k < n; k++) { // 累加求和
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
三重循环的含义
手算演示
A = | 1 2 | B = | 5 6 |
| 3 4 | | 7 8 |
C = A x B = ?
C[0][0]：A 的第0行 点乘 B 的第0列
A 第0行: [1, 2]
B 第0列: [5, 7] (竖着取)
C[0][0] = 1*5 + 2*7 = 5 + 14 = 19
C[0][1]：A 的第0行 点乘 B 的第1列
A 第0行: [1, 2]
B 第1列: [6, 8]
C[0][1] = 1*6 + 2*8 = 6 + 16 = 22
C[1][0]：A 的第1行 点乘 B 的第0列
A 第1行: [3, 4]
B 第0列: [5, 7]
C[1][0] = 3*5 + 4*7 = 15 + 28 = 43
C[1][1]：A 的第1行 点乘 B 的第1列
A 第1行: [3, 4]
B 第1列: [6, 8]
C[1][1] = 3*6 + 4*8 = 18 + 32 = 50
完整图示
B 的列
第0列 第1列
| |
v v
A [5] [6]
的 [1, 2]-->[19] [22] A第0行 分别点乘 B的第0列、第1列
行 [3, 4]-->[43] [50] A第1行 分别点乘 B的第0列、第1列
[7] [8]
结果: C = | 19 22 |
| 43 50 |
内层循环 k 的展开（以 C[1][0] 为例）
i=1, j=0:
k=0: C[1][0] += A[1][0] * B[0][0] = 3 * 5 = 15 sum=15
k=1: C[1][0] += A[1][1] * B[1][0] = 4 * 7 = 28 sum=43
A[1][0] A[1][1] B[0][0] B[1][0]
| | | |
3 4 5 7
| | | |
+---*----+ +---*----+
| |
A 的第1行 B 的第0列
| |
+--------点乘--------------+
|
3*5 + 4*7 = 43
三、矩阵转置
定义
把矩阵的行和列互换。原来的第 i i i 行第 j j j 列，变成第 j j j 行第 i i i 列。
A T [ j ] [ i ] = A [ i ] [ j ] A^T[j][i] = A[i][j] AT[j][i]=A[i][j]
m × n m \times n m×n 的矩阵转置后变成 n × m n \times m n×m。
对应代码
Mat transpose(const Mat& A) {
size_t m = A.size(); // 原来 m 行
size_t n = A[0].size(); // 原来 n 列
Mat AT(n, Vec(m)); // 转置后 n 行 m 列
for (size_t i = 0; i < m; i++) {
for (size_t j = 0; j < n; j++) {
AT[j][i] = A[i][j]; // 行列互换
}
}
return AT;
}
手算演示
原矩阵 A（2行3列）:
列0 列1 列2
行0 [ 1, 2, 3 ]
行1 [ 4, 5, 6 ]
转置后 AT（3行2列）:
列0 列1
行0 [ 1, 4 ] <-- 原来的列0变成了行0
行1 [ 2, 5 ] <-- 原来的列1变成了行1
行2 [ 3, 6 ] <-- 原来的列2变成了行2
赋值过程
A[0][0]=1 --> AT[0][0]=1 A[0][1]=2 --> AT[1][0]=2 A[0][2]=3 --> AT[2][0]=3
A[1][0]=4 --> AT[0][1]=4 A[1][1]=5 --> AT[1][1]=5 A[1][2]=6 --> AT[2][1]=6
直观理解：沿对角线翻转
原矩阵: 沿 \ 对角线翻转:
1 2 3 1 4
4 5 6 2 5
3 6
想象把矩阵写在一张透明纸上，沿左上到右下的对角线翻过去。
四、矩阵乘向量
定义
A A A 是 m × n m \times n m×n 矩阵， x ⃗ \vec{x} x 是长度 n n n 的向量，结果 b ⃗ \vec{b} b 是长度 m m m 的向量。
b [ i ] = ∑ j = 0 n − 1 A [ i ] [ j ] ⋅ x [ j ] b[i] = \sum_{j=0}^{n-1} A[i][j] \cdot x[j] b[i]=j=0∑n−1A[i][j]⋅x[j]
一句话：结果的第 i 个元素 = A 的第 i 行 点乘 x。
对应代码
Vec mult_mat_vec(const Mat& A, const Vec& x) {
size_t m = A.size(); // A 的行数
size_t n = A[0].size(); // A 的列数
assert(x.size() == n); // x 的长度必须等于 A 的列数
Vec b(m, 0.0); // 结果向量，长度 m
for (size_t i = 0; i < m; i++) { // 对 A 的每一行
for (size_t j = 0; j < n; j++) { // 逐元素相乘累加
b[i] += A[i][j] * x[j];
}
}
return b;
}
手算演示
A = | 1 2 | x = | 1 |
| 3 4 | | 2 |
b[0]：A 的第0行 点乘 x
[1, 2] · [1, 2] = 1*1 + 2*2 = 1 + 4 = 5
b[1]：A 的第1行 点乘 x
[3, 4] · [1, 2] = 3*1 + 4*2 = 3 + 8 = 11
结果: b = [5, 11]
图示
矩阵 A 向量 x 结果 b
| 1 2 | x | 1 | = | 5 | 1*1+2*2 = 5
| 3 4 | | 2 | | 11 | 3*1+4*2 = 11
--- - --
2列 长度2 长度2（=行数）
可以理解为矩阵乘法的特殊情况
把向量看成 n × 1 n \times 1 n×1 的矩阵：
| 1 2 | x | 1 | = | 5 |
| 3 4 | | 2 | | 11 |
(2x2) (2x1) (2x1)
所以矩阵乘向量其实就是矩阵乘矩阵，只不过右边的矩阵只有一列。
五、向量乘矩阵
定义
y ⃗ \vec{y} y 是长度 m m m 的向量， A A A 是 m × n m \times n m×n 矩阵，结果 b ⃗ \vec{b} b 是长度 n n n 的向量。
b [ j ] = ∑ i = 0 m − 1 y [ i ] ⋅ A [ i ] [ j ] b[j] = \sum_{i=0}^{m-1} y[i] \cdot A[i][j] b[j]=i=0∑m−1y[i]⋅A[i][j]
一句话：结果的第 j 个元素 = y 点乘 A 的第 j 列。
对应代码
Vec mult_vec_mat(const Vec& y, const Mat& A) {
size_t m = A.size(); // A 的行数
size_t n = A[0].size(); // A 的列数
assert(y.size() == m); // y 的长度必须等于 A 的行数
Vec b(n, 0.0); // 结果向量，长度 n
for (size_t j = 0; j < n; j++) { // 对 A 的每一列
for (size_t i = 0; i < m; i++) { // 逐元素相乘累加
b[j] += y[i] * A[i][j];
}
}
return b;
}
注意循环顺序
和"矩阵乘向量"对比：
矩阵 x 向量: 外层 i（遍历行），内层 j（遍历列）
b[i] += A[i][j] * x[j]
结果的每个元素 = A的一行 点乘 x
向量 x 矩阵: 外层 j（遍历列），内层 i（遍历行）
b[j] += y[i] * A[i][j]
结果的每个元素 = y 点乘 A的一列
手算演示
y = [1, 2] A = | 1 2 |
| 3 4 |
b[0]：y 点乘 A 的第0列
A 的第0列: [1, 3]
y · A的第0列 = 1*1 + 2*3 = 1 + 6 = 7
b[1]：y 点乘 A 的第1列
A 的第1列: [2, 4]
y · A的第1列 = 1*2 + 2*4 = 2 + 8 = 10
结果: b = [7, 10]
图示
矩阵 A
列0 列1
| |
向量 y v v
[1, 2] x | 1 [2] | = [7, 10]
| 3 [4] |
^ ^
| |
y·列0=7 y·列1=10
可以理解为矩阵乘法的特殊情况
把向量看成 1 × m 1 \times m 1×m 的矩阵（行向量）：
| 1 2 |
[ 1, 2 ] x | 3 4 | = [ 7, 10 ]
(1x2) (2x2) (1x2)
六、五种运算的关系
总览
+-------------------+---------------+---------------+------------------+
| 运算 | 左操作数 | 右操作数 | 结果 |
+-------------------+---------------+---------------+------------------+
| 点积 dot | 向量(n) | 向量(n) | 标量(1个数) |
| 矩阵x矩阵 | 矩阵(m x n) | 矩阵(n x p) | 矩阵(m x p) |
| 矩阵转置 | 矩阵(m x n) | 无 | 矩阵(n x m) |
| 矩阵x向量 | 矩阵(m x n) | 向量(n) | 向量(m) |
| 向量x矩阵 | 向量(m) | 矩阵(m x n) | 向量(n) |
+-------------------+---------------+---------------+------------------+
它们之间的联系
维度匹配的核心规则
左边的列数 = 右边的行数，结果取左边的行数 x 右边的列数。
(m x [n]) * ([n] x p) = (m x p)
^ ^
| |
+-必须相等-+
不满足这个条件就会触发 assert 失败。
七、代码中的 C++ 细节
using 类型别名
using Vec = std::vector<double>; // Vec 就是 vector<double>
using Mat = std::vector<std::vector<double>>; // Mat 就是二维 vector
省得每次写一长串类型名。
const 引用参数
double dot(const Vec& x, const Vec& y)
// ^^^^^ ^
// 不修改 引用（不拷贝）
const Vec& 的含义：
不加 const 和 &: void f(Vec x) --> 拷贝一份，浪费内存和时间
加 & 不加 const: void f(Vec& x) --> 不拷贝，但函数内可以修改原数据
加 const 和 &: void f(const Vec& x) --> 不拷贝，也不能修改，最安全高效
assert 断言
assert(x.size() == y.size()); // 如果条件为 false，程序立即崩溃并报错
用于捕捉编程错误（比如传入维度不匹配的矩阵）。发布版本可以用 -DNDEBUG 编译选项关闭所有断言。
size_t 类型
for (size_t i = 0; i < x.size(); i++)
size_t 是无符号整数类型，和 vector::size() 的返回类型一致。如果用 int 会产生"有符号和无符号比较"的编译警告。
八、完整运行结果
点积 [1,2,3]·[4,5,6] = 32
A x B =
19.00 22.00
43.00 50.00
转置 [[1,2,3],[4,5,6]] =
1.00 4.00
2.00 5.00
3.00 6.00
[[1,2],[3,4]] x [1,2] = [5.00, 11.00]
[1,2] x [[1,2],[3,4]] = [7.00, 10.00]
九、矩阵乘法不满足交换律
注意最后两个测试的结果不同：
矩阵 x 向量: A * x = [5, 11]
向量 x 矩阵: x * A = [7, 10]
这说明矩阵乘法不满足交换律（ A × B ≠ B × A A \times B \neq B \times A A×B=B×A）。
A * x: 每个结果元素 = A的一行 点乘 x
x * A: 每个结果元素 = x 点乘 A的一列
取的"方向"不同，结果自然不同。
1.1.34 过滤问题分析（Filtering）
思路理解
输入： N N N 个 [ 0 , 1 ) [0, 1) [0,1) 之间的实数。
问题是：哪些操作必须把所有数存下来，哪些只需固定大小的变量？
| 任务 | 是否需要存所有数 | 理由 |
|---|---|---|
| 打印最大值和最小值 | X 不需要 | 维护两个变量 max, min 即可，逐个更新 |
| 打印中位数 | √ 需要 | 中位数要知道排序后的第 N/2 个数，必须存全部 |
| 打印第 k 小的值X（k < 100） | X 不需要 | 只需维护大小为 k 的最大堆（固定大小） |
| 打印平方和 | X 不需要 | 维护累积变量 ∑ x i 2 \sum x_i^2 ∑xi2，逐个加即可 |
| 打印平均值 | X 不需要 | 维护 sum 和 count，最后 sum/count |
| 打印大于平均值的数的比例 | √ 需要 | 必须先算出平均值，再第二次扫描——需要存全部数 |
| 升序打印 | √ 需要 | 排序需要所有数据 |
| 随机顺序打印 | √ 需要 | 洗牌必须知道所有数据 |
C++ 完整代码（演示全部情况）
#include <iostream>
#include <vector>
#include <algorithm> // sort, nth_element
#include <numeric> // accumulate
#include <queue> // priority_queue
#include <cstdlib> // rand
int main() {
// 读取所有输入（实际场景下是流式读取）
std::vector<double> data;
std::cout << "请输入若干 [0,1) 之间的实数（Ctrl+D 结束）:" << std::endl;
double val;
while (std::cin >> val) {
data.push_back(val);
}
int N = (int)data.size();
if (N == 0) { std::cout << "没有输入！" << std::endl; return 0; }
// ===================================================
// 1. 打印最大值和最小值（不需要存所有数，这里演示用已有数据）
// ===================================================
double cur_max = data[0], cur_min = data[0];
for (double x : data) {
if (x > cur_max) cur_max = x;
if (x < cur_min) cur_min = x;
}
std::cout << "\n1. 最大值: " << cur_max << "，最小值: " << cur_min << std::endl;
// ===================================================
// 2. 打印中位数（需要存所有数）
// ===================================================
std::vector<double> sorted_data = data;
std::sort(sorted_data.begin(), sorted_data.end());
double median;
if (N % 2 == 1) {
median = sorted_data[N / 2];
} else {
median = (sorted_data[N / 2 - 1] + sorted_data[N / 2]) / 2.0;
}
std::cout << "2. 中位数: " << median << std::endl;
// ===================================================
// 3. 第 k 小的值（k < 100，只需固定大小的堆）
// ===================================================
int k = std::min(3, N); // 演示取第3小
// 用大小为 k 的最大堆，维护当前最小的 k 个数
std::priority_queue<double> max_heap;
for (double x : data) {
max_heap.push(x);
if ((int)max_heap.size() > k) max_heap.pop(); // 超过 k 个就踢掉最大的
}
std::cout << "3. 第" << k << "小的值: " << max_heap.top() << std::endl;
// ===================================================
// 4. 平方和（不需要存所有数）
// ===================================================
double sum_sq = 0.0;
for (double x : data) sum_sq += x * x;
std::cout << "4. 平方和: " << sum_sq << std::endl;
// ===================================================
// 5. 平均值（不需要存所有数）
// ===================================================
double sum = 0.0;
for (double x : data) sum += x;
double avg = sum / N;
std::cout << "5. 平均值: " << avg << std::endl;
// ===================================================
// 6. 大于平均值的数的比例（需要存所有数，因为先算均值再扫描）
// ===================================================
int above_avg = 0;
for (double x : data) {
if (x > avg) above_avg++;
}
std::cout << "6. 大于平均值的比例: " << (100.0 * above_avg / N) << "%" << std::endl;
// ===================================================
// 7. 升序打印（需要排序，存所有数）
// ===================================================
std::cout << "7. 升序: ";
for (double x : sorted_data) std::cout << x << " ";
std::cout << std::endl;
// ===================================================
// 8. 随机顺序打印（需要洗牌，存所有数）
// ===================================================
std::vector<double> shuffled = data;
// Fisher-Yates 洗牌算法
for (int i = N - 1; i > 0; i--) {
int j = rand() % (i + 1);
std::swap(shuffled[i], shuffled[j]);
}
std::cout << "8. 随机顺序: ";
for (double x : shuffled) std::cout << x << " ";
std::cout << std::endl;
return 0;
}
总结对照表
┌──────────┬────────────────────────────┬──────────────────────────────────┐
│ 题号 │ 核心思想 │ 关键技术点 │
├──────────┼────────────────────────────┼──────────────────────────────────┤
│ 1.1.26 │ 三次比较+交换 │ 临时变量 t，手动 swap │
│ 1.1.27 │ 记忆化消除重复递归 │ 二维 memo 数组，DP 自底向上 │
│ 1.1.28 │ 排序后去重 │ 相邻比较，跳过重复 │
│ 1.1.29 │ 二分找上下界 │ lower_bound / upper_bound 思想 │
│ 1.1.30 │ GCD 判断互质 │ 欧几里得辗转相除法 │
│ 1.1.31 │ 圆上布点+随机连线 │ 极坐标转直角坐标，随机数 │
│ 1.1.32 │ 区间统计+柱状图 │ 桶计数，ASCII 可视化 │
│ 1.1.33 │ 线性代数基本运算 │ 点积/矩阵乘法/转置 │
│ 1.1.34 │ 分析哪些需要存储所有数据 │ 流式处理 vs. 需要全局信息 │
└──────────┴────────────────────────────┴──────────────────────────────────┘
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
10
0- 0
已为社区贡献13条内容
所有评论(0)