跳转至

zqiceberg.com

循环嵌套

循环嵌套¶

循环嵌套¶

循环嵌套，又称多重循环

循环结构包含循环结构，形成多重循环的结构

for (int i = 1; i <= 10; i++) {
    for (int j = 1; j <= 10; j++) cout << j << ' ';
    cout << endl;
}

打印图形¶

数字三角形

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) cout << j;
    cout << endl;
}

靠右的数字三角形

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n - i; j++) cout << ' ';

    for (int j = 1; j <= i; j++) cout << j;
    cout << endl;
}

靠右的字符三角形

    A
   AB
  ABC
 ABCD
ABCDE

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n - i; j++) cout << ' ';

    for (int j = 0; j < i; j++) cout << char('A' + j);
    cout << endl;
}

字符对称三角形

    A
   BAB
  CBABC
 DCBABCD
EDCBABCDE

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n - i; j++) cout << ' ';
    for (int j = 1; j <= 2 * i - 1; j++)   // 难点语句
        cout << char(abs(j - i) + 'A');
    cout << endl;
}

打印排列组合¶

[1, n]范围选择 3 个数字进行排列，数字可以重复使用，按字典序输出

// 三层循环枚举三个数
cin >> n;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= n; k++)
            cout << i << ' ' << j << ' ' << k << endl;

[1, n] 范围选择 3 个数字进行排列，数字不可以重复使用，按字典序输出

// 三层循环枚举三个数，if判断是否重复使用
cin >> n;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= n; k++)
            if (i != j && i != k && j != k)
                cout << i << ' ' << j << ' ' << k << endl;

[1, n] 范围选择 3 个数字进行组合，数字可以重复使用，按字典序输出

【输入】
2
【输出】
1 1 1
1 1 2
1 2 2
2 2 2

举例，对于数列123，

排列的方案包括123、132、213、231、312、321，共6种，

但都被视为同一种组合。

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
        for (int k = j; k <= n; k++)
            cout << i << ' ' << j << ' ' << k << endl;

[1, n] 范围选择 3 个数字进行组合，数字不可以重复使用，按字典序输出

【输入】
4
【输出】
1 2 3
1 2 4
1 3 4
2 3 4

// 三层循环，从 i+1 开始枚举第二个数，从 j+1 开始枚举第三个数 
for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
        for (int k = j + 1; k <= n; k++)
            cout << i << ' ' << j << ' ' << k << endl;

循环嵌套优化¶

1092：求出e的值 ¶

两层循环，\(O(n^2)\)

for (int i = 1; i <= n; i++) {
    long long t = 1;
    for (int j = 1; j <= i; j++) t *= j;  // 求i!  n!

    cout << t << endl;
}

一层循环，\(O(n)\)

ll t = 1ll;
for (int i = 1; i <= n; i++){
    t *= i;
    ret += 1.0 / t;
}

printf("%.10lf\n", ret);

2028：【例4.14】百钱买百鸡¶

三层循环，\(O(n^3)\)

for (int i = 0; i <= 100 / 5; i++)
    for (int j = 0; j <= 100 / 3; j++)
        for (int k = 0; k <= 300; k += 3)
            if (i * 5 + j * 3 + k / 3 == 100 && i + j + k == 100) 
                printf("%d %d %d\n", i, j, k);

两层循环，\(O(n^2)\)

for (int i = 0; i <= 100 / 5; i++)
    for (int j = 0; j <= 100 / 3; j++) {
        int k = 100 - i - j;
        if (i*5 + j*3 + k/3 == 100 && k % 3 == 0) printf("%d %d %d\n", i, j, k);
    }

2068：【例2.6】鸡兔同笼 ¶

两层循环枚举，\(O(n^2)\)

for (int i = 0; i <= x; i++)
    for (int j = 0; j <= min(x, y / 4); j++)
        if (i + j == x && 2 * i + 4 * j == y)
            cout << i << ' ' << j << endl;

一层循环枚举，\(O(n)\)

for (int i = 0; i <= x; i++) {
    int j = x - i;
    if (2 * i + 4 * j == y) cout << i << ' ' << j << endl;
}

列方程，\(O(1)\)

int tuzi = (y - x * 2) / 2;
int ji = x - tuzi;

cout << ji << ' ' << tuzi << '\n';