21.1 序列问题的嵌套循环解法

“序列问题是编程中的常见问题类型，”我微笑着解释道，”通过嵌套循环，我们可以高效地处理复杂的序列计算和模式识别。”

21.1.1金币问题

题目描述：国王将金币作为工资，发放给忠诚的骑士。第1天，骑士收到一枚金币；之后两天(第2天和第3天)里，每天收到两枚金币；之后三天(第4、5、6天)里，每天收到三枚金币；之后四天(第7、8、9、10天)里，每天收到四枚金币……这种工资发放模式会一直这样延续下去：当连续n天每天收到n枚金币后，骑士会在之后的连续n+1天里，每天收到n+1枚金币(n为任意正整数)。你需要编写一个程序，确定从第一天开始的给定天数内，骑士一共获得了多少金币。

样例输入：

10

样例输出：

30

代码实现（方法一：直角三角形模型）：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;  // 输入总天数
    int sum = 0;  // 初始化金币总和为0
    int cnt = 0;  // 初始化计数器，记录已经过去的天数
    for(int i = 1; ; i++) {  // 无限循环，i表示每天发放的金币数
        for(int j = 1; j <= i; j++) {  // 内循环控制连续i天每天发i个金币
            sum += i;  // 累加金币数
            cnt++;  // 天数计数器加1
            if(cnt == n) {  // 如果达到指定天数
                cout << sum;  // 输出结果
                return 0;  // 结束程序
            }
        }
    }
    return 0;
}

代码实现（方法二：单循环计数）：

#include <iostream>
using namespace std;

int main() {
    int n, sum = 0, jb = 1, cnt = 0;  // n为总天数，sum为金币总和，jb为当前每天金币数，cnt为当前阶段的天数计数
    cin >> n;
    for(int i = 1; i <= n; i++) {  // 循环n天
        sum += jb;  // 当天获得的金币加入总和
        cnt++;  // 当前阶段计数器加1
        if(cnt == jb) {  // 如果当前阶段已经完成（连续jb天每天发jb个金币）
            jb++;  // 每天金币数增加1
            cnt = 0;  // 重置当前阶段的天数计数器
        }
    }
    cout << sum;  // 输出金币总和
    return 0;
}

思考：

• 方法一使用嵌套循环，外循环控制金币数量，内循环控制相同金币数量的连续天数
• 方法二使用单循环配合计数器，当计数器达到当前金币数时，增加金币数并重置计数器
• 两种方法都能得到正确结果，但方法二的代码更加简洁，时间复杂度更低

21.1.2 阶乘和

题目描述：求 S=1!+2!+3!+….+n!。

样例输入：

5

样例输出：

153

代码实现（方法一：直角三角形模型）：

#include <iostream>
using namespace std;

int main() {
    int n, sum = 0;  // n为输入值，sum为阶乘和
    cin >> n;
    for(int i = 1; i <= n; i++) {  // 外循环遍历1到n的每个数
        int jc = 1;  // 每次计算新的阶乘时，初始化阶乘值为1
        for(int j = 1; j <= i; j++) {  // 内循环计算i的阶乘
            jc *= j;  // 累乘计算阶乘
        }
        sum += jc;  // 将当前阶乘加入总和
    }
    cout << sum;  // 输出阶乘和
    return 0;
}

代码实现（方法二：累积阶乘）：

#include <iostream>
using namespace std;

int main() {
    int n, sum = 0, jc = 1;  // n为输入值，sum为阶乘和，jc为当前阶乘值
    cin >> n;
    for(int i = 1; i <= n; i++) {  // 循环遍历1到n的每个数
        jc *= i;  // 利用前一个阶乘值计算当前阶乘：i! = (i-1)! * i
        sum += jc;  // 将当前阶乘加入总和
    }
    cout << sum;  // 输出阶乘和
    return 0;
}

思考：

• 方法一使用嵌套循环，外循环遍历1到n，内循环计算每个数的阶乘
• 方法二利用阶乘的递推性质：n! = (n-1)! × n，避免了重复计算
• 方法二的时间复杂度为O(n)，而方法一的时间复杂度为O(n²)，方法二更高效