循环嵌套

一个循环的循环体中包含另一个循环，称为循环嵌套。

九九乘法表

for (int i = 1; i <= 9; i++)
{
    for (int j = 1; j <= i; j++)
    {
        cout << j << "*" << i << "=" << i * j << " ";
    }
    cout << "";
}

冒泡排序

for (int i = 1; i <= n - 1; i++)
    for (int j = 1; j <= n - 1; j++)
        if (a[j] > a[j + 1])
            swap(a[j], a[j + 1]);

选择排序

for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
        if (a[j] < a[i])
            swap(a[j], a[i]);

打印矩形

// 打印 n 行 m 列的星号矩形
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
        cout << "*";
    cout << "";
}

综合例题

水仙花数

一个三位数，其各位数字的立方和等于该数本身。求所有的水仙花数。

for (int i = 100; i <= 999; i++)
{
    int a = i / 100;          // 百位
    int b = i / 10 % 10;      // 十位
    int c = i % 10;           // 个位
    if (a * a * a + b * b * b + c * c * c == i)
        cout << i << "";
}

百钱买百鸡

公鸡 $5$ 元一只，母鸡 $3$ 元一只，小鸡 $1$ 元三只。用 $100$ 元买 $100$ 只鸡，求所有方案。

for (int i = 0; i <= 20; i++)          // 公鸡最多 20 只
    for (int j = 0; j <= 33; j++)      // 母鸡最多 33 只
    {
        int k = 100 - i - j;            // 小鸡数量
        if (k % 3 == 0 && 5 * i + 3 * j + k / 3 == 100)
            cout << i << " " << j << " " << k << "";
    }

复杂度分析

• 单层循环：$O(n)$
• 双层循环嵌套：$O(n^2)$
• 三层循环嵌套：$O(n^3)$

一般评测机 $1$ 秒大约能执行 $10^8$ 次基本运算。当 $n\leq 5000$ 时 $O(n^2)$ 可行，当 $n\leq 500$ 时 $O(n^3)$ 可行。