“二重循环” 的第一个例子

for (int i = 0; i < 5; i++) {
  for (int j = 0; j <= i; j++) {
    cout << "*";
  }
  cout << endl;
}

*
**
***
****
*****

其实有一个 “通用” 版本

auto f = [](int i, int j) { return j <= i; };
// 可以是任意的 “判定”

for (int i = 0; i < 5; i++) {
  for (int j = 0; j < 5; j++) {
    cout << (f(i, j) ? '*' : ' '); // 注意括号
  }
  cout << endl;
}

*
**
***
****
*****

“万能二重循环” 可以做什么？

auto f = [](int i, int j) {
  double x = ((j * 2) / 15.0 - 3) / 2;
  double y = (i * 2) / 15.0 - 2;
  return pow(pow(x, 2) + pow(y, 2) - 1, 3) + \
             pow(x, 2) * pow(y, 3) < 0;
};

for (int i = 5; i < 25; i++) {
  for (int j = 0; j < 50; j++) {
    cout << (f(i, j) ? '*' : ' ');
  }
  cout << endl;
}

试一试：print.cc

我们在数学里似乎也用过这样的循环？

$$ \begin{array}{rcl} \displaystyle \sum_{1 \le i \le 100} & = & 1 + 2 + \ldots + 100 \\ & = & \displaystyle \sum_{1 \le i \le 50} (i + 100 - i + 1) \\ & = & \displaystyle \sum_{1 \le i \le 50} 101 \\ & = & 5050 \end{array} $$

其实我们是在做程序的 “优化” (“简化”)

for (int i = 1; i <= 100; i++) sum += i;
for (int i = 1; i <= 50; i++)  sum += i + (101 - i);

求和的基本形式

$$ \sum_{k \in K\ (一个可枚举的集合)} a_k $$

$$ \begin{array}{rcl} \displaystyle \sum_{1 \le k \le 100} k^2 & = & 1^2 + 2^2 + \ldots + 100^2 \\ \displaystyle \sum_{ \begin{matrix} 1 \le k \le n\\ k \text{是奇数}\end{matrix}} k^2 & = & 1^2 \cdot [ 1 \bmod 2 = 0 ] + \ldots + n^2 \cdot [ n \bmod 2 = 0 ] \\ \displaystyle \sum_{ \begin{matrix} 1 \le p \le n\\ p \text{是素数}\end{matrix}} \frac1p & = & \displaystyle \frac12 + \frac13 + \frac15 + \ldots \end{array} $$

求解和式：程序的改写和优化

分配律

$$ \sum_{k\in K} c \cdot a_k = c \cdot \sum_{k\in K} a_k $$

结合律

$$ \sum_{k\in K} (a_k + b_k) = \sum_{k\in K} a_k + \sum_{k\in K} b_k $$

换元法 ($p$ 是整数集合上的一个排列)

$$ \sum_{k\in K} a_k = \sum_{p(k) \in K} a_{p(k)} $$

二重循环来啦

“数星星”

$$ \sum_{1\le i \le n}\sum_{1\le j \le n} [f(i,j) = \text{true}] $$

这是什么？

$$ \sum_{1\le i \le n}\sum_{1\le j \le n} a_i b_j $$

• 让我们来做编译优化吧 (sum.cc)

二重循环的变化

交换循环次序求和不变

$$ \sum_{i \in I}\sum_{j \in J} a_{i,j} = \sum_{j \in J}\sum_{i \in I} a_{i,j} $$

多重循环总是可以写成 “条件” 形式 (print.cc)

$$ \sum_{i \in I}\sum_{j \in J_i} a_{i,j} = \sum_i \sum_j a_{i,j} [i \in I \land j \in J_i] $$

一个似乎不太好处理的例子：

$$ \sum_{1 \le k < n} \lfloor k \rfloor $$

Euler $\phi$ 函数

$$ \phi(n) = \sum_{1 \le k \le n} [n\perp k] $$

有趣的积性

$$\phi(n_1) \cdot \phi(n_2) = \phi(n_1 \cdot n_2)$$

哪些函数拥有积性？

• $f(n) = n$
• $f(n) = [n=1]$
• $\sigma_k(n) = \sum_{d|n} d^k$

$\phi$ 的有趣性质

$$ \sum_{d | n} \phi(d) = n $$

这竟然不是巧合

• $\phi$ 是 $f(n) = n$ 在约数求和上的 “分解”
• 我们可以 “分解” 任何一个积性函数

$$\sum_{d | n} \mu(d) = [n=1]$$

“Möbius Inversion”: 积性函数总是 “成对出现”

$$f(n) = \sum_{ d | n } g(d) \ \Leftrightarrow \ g(n) = \sum_{ d | n } \mu(d) f(n/d)$$

例子：一系列求和问题

一维的

$$\sum_{1 \le k \le n} \gcd(k, n)$$

二维的

$$\sum_{1 \le i \le n} \sum_{1 \le j \le n} \gcd(i, j) \quad \sum_{1 \le i \le n} \sum_{1 \le j \le m} \gcd(i, j)$$

前缀和

$$ \sum_{1 \le k \le n}\phi(k) $$

$\Sigma$: 一个 “数学编程语言”

理解 “求和”

$$ \sum_{i \in I}\sum_{j \in J} a_{i,j} $$

sum = 0;
for (i: I)
  for (j : J)
    sum += f(i, j);

求解和式

• “程序的改写和优化”