序列求和

问题描述

---

求1+2+3+4+...+n的值。

---

输入格式

---

输入包括一个整数n。

输出格式

---

输出一行，包括一个整数，表示1+2+3+4+...+n的值。

思路

---

求从1加到n的值，使用C++语言编写，先要弄清输入与输出值的类型，要避免当n的数值过大时产生数据溢出，int型数据的范围为-2147483648~2147483647(-2³¹~2³¹-1),long long数据类型的范围为-9223372036854775808~9223372036854775807 (-2⁶³~2⁶³-1)，为避免数据规模过大，使用long long 型作为输入输出的类型。然后是计算结果的思路，这里列出3种，第一种循环累加这里使用for循环累加;第二种数学公式计算，这里为等差数列，等差数列求和公式为a_n=(a₁+a_n)*n/2;第三种是递归求和方法。

代码

---

for循环累加法

#include<iostream>
#include<time.h>
using namespace std;
int main()
{
	long long n,sum=0;
	clock_t start, end;
	double time;
	cin >> n;
	start = clock();
	for (; n > 0;n--)
	{
		sum += n;
	}
	cout << sum<<endl;
	end = clock();
	time = (double)(end-start);
	cout << time << "ms";
	return 0;
}

这里使用了C库函数中的<time.h>，clock_t clock(void)返回程序执行起（一般为程序的开头），处理器时间钟所使用的时间。time=(double)(end-start)得到代码计算出结果所耗费时间。
使用for循环累加时要注意，当数据规模过大时，这种方法往往会导致超时，资源占用率高。

---

等差数列公式法

#include <iostream>
#include <time.h>
using namespace std;
int main() 
{
	long long int n;
	clock_t start, end;
	double time;
	cin >> n;
	start = clock();
	cout <<	(1 + n)* n / 2<<endl;
	end = clock();
	time =(double)(end - start);
	cout << time<<"ms";
	return 0;
}

直接使用公式计算，所耗时间短，占用计算少，数据规模过大时也能进行很好计算。

---

递归求和法

#include<iostream>
#include<time.h>
using namespace std;
long long int fun(long long int n)
{
	if (n >= 1)
	{
		return n+fun(n - 1);
	}
	else
	{
		return 0;
	}
}
int main()
{
	clock_t start, end;
	double time;
	long long int n, sum;
	cin >> n;
	start = clock();
	sum = fun(n);
	cout << sum << endl;
	end = clock();
	time = (double)(end - start);
	cout << time;
	return 0;
}

当数值在一定数值范围内计算效果最优，但超过一定数值计算效果公式法优。