杭电OJ1001 C

杭电OJ1001

杭电1001题，计算从1加到n,一个等差数列。题目如下：

• 有两种算法，一种是从1加到n，每次循环之后sum要记得清空，赋值为0，我就在这一点上出错了,输出的值总是差一点。

  代码如下：

#include<stdio.h>
int main (void)
{
	int i=0,sum=0,n;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
		{
			sum+=i;
		}
		printf("%d\n\n",sum);
		sum=0;
	}

	return 0;
}       
           

• 第二种算法，就是上小学时听的那个关于高斯的故事：

高斯7岁那年开始上学。10岁的时候，他进入了学习数学的班级，这是一个首次创办的班，孩子们在这之前都没有听说过算术这么一门课程。数学教师是布特纳，他对高斯的成长也起了一定作用。

一天，老师布置了一道题，1+2+3······这样从1一直加到100等于多少。

高斯很快就算出了答案，起初高斯的老师布特纳并不相信高斯算出了正确答案："你一定是算错了，回去再算算。”高斯非常坚定，说出答案就是5050。高斯是这样算的：1+100=101，2+99=101······50+51=101。从1加到100有50组这样的数，所以50X101=5050。

布特纳对他刮目相看。他特意从汉堡买了最好的算术书送给高斯，说：“你已经超过了我，我没有什么东西可以教你了。”接着，高斯与布特纳的助手巴特尔斯建立了真诚的友谊，直到巴特尔斯逝世。他们一起学习，互相帮助，高斯由此开始了真正的数学研究。

也就是正常人算这种题的算法：首尾相加乘以个数除以二。但是不能直接用等差数列求和公式，因为题中有这么一句：

You may assume the result will be in the range of 32-bit signed integer.

要求数据不能超过三十二位，那么n很大的时候n*(n+1)会溢出，造成Wrong Answer。我就是在本地运行的好好的，结果上OJ就WA，后来才发现是这么个问题。

先判断奇偶，然后把n和n+1中偶数的一方除以二，再相乘，这样就不会溢出了，顺利AC。

代码如下：

#include<stdio.h>
int main (void)
{
	int sum,n;
	while(scanf("%d",&n)!=EOF)
	{
		if(n%2==0)
		{
			sum=n/2*(n+1);
		}else
		{
			sum=(n+1)/2*n;
		}
		//sum = (1 + n) * n / 2;会溢出
		printf("%d\n\n",sum);
		sum=0;
	}

	return 0;
}