序列求和
问题描述
求1+2+3+4+...+n的值。
输入格式
输入包括一个整数n。
输出格式
输出一行,包括一个整数,表示1+2+3+4+...+n的值。
思路
求从1加到n的值,使用C++语言编写,先要弄清输入与输出值的类型,要避免当n的数值过大时产生数据溢出,int型数据的范围为-2147483648~2147483647(-231~231-1),long long数据类型的范围为-9223372036854775808~9223372036854775807 (-263~263-1),为避免数据规模过大,使用long long 型作为输入输出的类型。然后是计算结果的思路,这里列出3种,第一种循环累加这里使用for循环累加;第二种数学公式计算,这里为等差数列,等差数列求和公式为an=(a1+an)*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;
}
当数值在一定数值范围内计算效果最优,但超过一定数值计算效果公式法优。