题解 B2142 【求 sum(1..n)】

daiarineko · 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 非常大时性能很好。