C++序列求和

问题描述

求1+2+3+4+...+n的和

数据规模与约定

n >= 1 && n <= 1,000,000,000

解题思路

• 本题最直观的方法就是用一个for循坏求出结果，但是注意这里的数据规模很大，用for循坏运算时间长，所以for循坏并不是最优解
• 利用等差数列求和的公式比for循坏执行的时间更短
• 第三个方法就是递归，但递归会保存大量临时数据和重复数据，太多的话会造成栈溢出，程序崩溃

方法一：循环累加法

#include<iostream>
using namespace std;

int main()
{
	long long int s,count = 0;

	cin>>s;

	for(;s >= 1;s--)
	{
		count += s;
	}

	cout<<count<<endl;

	system("pause");
	cin.get();
	return 0;
}

方法二：公式求和法

等差数列求和公式：S=[项数 *（首项 + 尾项）] / 2

#include<iostream>
using namespace std;

int main()
{
	long long int s;

	cin>>s;
	cout<<s*(1+ s)/2<<endl;

	system("pause");
	return 0;
}

方法三：递归法

#include<iostream>
using namespace std;

long long int fun(long long  int s)
{
	if(s > 0)
	{
		return s + fun(s - 1);
	}
	else
		return 0;
}

int main(int argc, char const *argv[])
{
	long long int s,count;

	cin>>s;
	count = fun(s);
	cout<<count<<endl;

	return 0;
}

序列求和