查看“︁02-选择与循环/05-循环嵌套与综合”︁的源代码


== 循环嵌套 ==

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

=== 九九乘法表 ===

<syntaxhighlight lang="cpp">
for (int i = 1; i <= 9; i++)
{
    for (int j = 1; j <= i; j++)
    {
        cout << j << "*" << i << "=" << i * j << " ";
    }
    cout << "\n";
}
</syntaxhighlight>

=== 冒泡排序 ===

<syntaxhighlight lang="cpp">
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]);
</syntaxhighlight>

=== 选择排序 ===

<syntaxhighlight lang="cpp">
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]);
</syntaxhighlight>

=== 打印矩形 ===

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

== 综合例题 ==

=== 水仙花数 ===

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

<syntaxhighlight lang="cpp">
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";
}
</syntaxhighlight>

=== 百钱买百鸡 ===

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

<syntaxhighlight lang="cpp">
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";
    }
</syntaxhighlight>

=== 复杂度分析 ===

- 单层循环：<math>O(n)</math>
- 双层循环嵌套：<math>O(n^2)</math>
- 三层循环嵌套：<math>O(n^3)</math>

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


[[Category:选择与循环]]
[[Category:三三文档]]