分组作业 02：级数求和算法设计与实现#

本报告记录了小组关于双重嵌套累加级数求和问题的数学简化推导、算法设计与 C++/Raptor 实现。

---

一、 课程作业基本信息#

项目名称	详细信息
课程名称	计算机科学导论
小组名称	败犬女组
组长姓名	八奈见杏菜
小组成员	Kisara,Kaguya
题目名称	分组作业2：级数求和计算
指导教师	张瑾
提交日期	2023年11月06日

---

二、 题目描述#

计算如下双重累加级数的和： $S = 1 + (1+2) + (1+2+3) + \dots + (1+2+3+\dots+n)$

其中，$n$ 的值由键盘输入（正整数）。

---

三、 解题思路与数学推导#

求解该级数有两种核心方法：

1. 迭代循环法（$O(n)$ 时间复杂度）#

定义前缀和 currentSum 记录第 $k$ 项前 $k$ 个自然数的和，总和 total 进行累加：

• 初始值：total = 0, currentSum = 0；
• 循环 $i$ 从 $1$ 到 $n$：
  • currentSum = currentSum + i
  • total = total + currentSum

2. 数学公式法（$O(1)$ 时间复杂度）#

第 $k$ 个括号内的和为前 $k$ 个自然数的和： $S_k = \frac{k(k+1)}{2}$

整个级数和转化为求和公式： $S = \sum_{k=1}^{n} \frac{k(k+1)}{2} = \frac{1}{2} \left[ \sum_{k=1}^{n} k^2 + \sum_{k=1}^{n} k \right]$

利用平方和公式 $\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$ 和等差数列求和公式 $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ 展开化简： $S = \frac{1}{2} \left[ \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} \right] = \frac{n(n+1)(n+2)}{6}$

直接利用该公式可在 $O(1)$ 常数时间得到精确解。

---

四、 代码与流程图实现#

1. C++ 代码实现#

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入正整数 n 的值: ";
    if (!(cin >> n) || n <= 0) {
        cout << "输入无效，请输入正整数！" << endl;
        return 1;
    }

    // 方法 1：循环累加法 O(n)
    long long totalLoop = 0;
    long long currentSum = 0;
    for (int i = 1; i <= n; i++) {
        currentSum += i;
        totalLoop += currentSum;
    }

    // 方法 2：数学公式法 O(1)
    long long totalFormula = (long long)n * (n + 1) * (n + 2) / 6;

    cout << "循环累加结果: " << totalLoop << endl;
    cout << "公式推导结果: " << totalFormula << endl;

    return 0;
}

2. Raptor 流程图逻辑#

输入 n
total := 0
currentSum := 0
i := 1
循环 i <= n
    currentSum := currentSum + i
    total := total + currentSum
    i := i + 1
结束循环
输出 "计算结果为：" + total

---

五、 成员分工#

• Kisara：C++ 代码编写、数学公式简化推导与性能测试；
• Kaguya：Raptor 算法流程图绘制与演算逻辑核对；
• 八奈见杏菜：解题思路整理、边界条件分析；
• Golden Darkness：文档撰写与格式排版校对；
• 椎名真昼：题目推导过程复核。