自动搬运

查看原文

来自洛谷，原作者为

	daiarineko 我们犯罪没得手，任你何进有先人 | 有勾 8 了

搬运于2025-08-24 21:07:41，当前版本为作者最后更新于2021-07-04 09:53:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述

求 $\sum\limits^n_{i=1} i$。

解法1

复杂度：$\Theta(n)$

题目要求的解法，使用递归。

具体讲一下 f 函数，这里 f(n) 的定义是 $\sum\limits^n_{i=1} i$。

其中 $\sum\limits^n_{i=1} i = (\sum\limits^{n-1}_{i=1} i)+n$，所以可以递归地调用 f 函数：return f(n-1)+n。

递归的结束条件：n==1，这时候 $(\sum\limits^1_{i=1}i)=1$，直接返回。

（亦可在 n==0 时返回 0）。

#include<bits/stdc++.h>
using namespace std;
int f(int n){
    if(n==1)return 1;
    return f(n-1)+n;
}
int main(){
    int n;
    cin>>n;
    cout<<f(n)<<endl;
    return 0;
}

解法2

复杂度：$\Theta(1)$

可以使用数学解法降低复杂度。

我们都知道等差数列的通项公式：（首项+末项）*项数/2。

其中首项为 $1$，末项为 $n$，项数为 $n$。

代入公式得 $\frac{(n+1)n}{2}$。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    cout<<n*(n+1)/2<<endl;
    return 0;
}

此解法在 $n$ 非常大时性能很好。