02-选择与循环/05-循环嵌套与综合

循环嵌套

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

九九乘法表

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

冒泡排序

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 << "\n";
}

综合例题

水仙花数

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

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 << "\n";
}

百钱买百鸡

公鸡 [math]\displaystyle{ 5 }[/math] 元一只，母鸡 [math]\displaystyle{ 3 }[/math] 元一只，小鸡 [math]\displaystyle{ 1 }[/math] 元三只。用 [math]\displaystyle{ 100 }[/math] 元买 [math]\displaystyle{ 100 }[/math] 只鸡，求所有方案。

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 << "\n";
    }

复杂度分析

- 单层循环：[math]\displaystyle{ O(n) }[/math] - 双层循环嵌套：[math]\displaystyle{ O(n^2) }[/math] - 三层循环嵌套：[math]\displaystyle{ O(n^3) }[/math]

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