《C语言入门100例》----第02题

《C语言入门100例》----第02题

 目录

1.题目描述

错误解法：利用前n项和的公式

正解法一：循环枚举法：

正解法二：奇偶判断法

正解法三：无符号整型

正解法四：长整型

实质：

---

1.题目描述

题1：循环输入，每输入一个正整数 n ( n ≤ 65535 ) ,输出 1 + 2 + 3 + . . . + n 的值，并且多输出一个空行。当没有任何输入时，结束程序。

错误解法：利用前n项和的公式

因为当 n 取最大值 65535 时，n ∗ ( n + 1 ) = 65535 ∗ 65536 = ( 2 16 − 1 ) 2 16 = 2 32 − 2 16 而 i n t 能够表示的最大值为 2 31 − 1 2^{31}-，所以产生了溢出。就变成了负数。 

#include"stdio.h" 

int main()
{
	int n;
	
	while(scanf("%d",&n)!=EOF)
	{
		printf("%dn",n*(n+1)/2) ;//法一：前n项和公式 
		                      //存在问题：当 n nn 取最大值 65535 时， 会溢出，不推荐使用 
	}
	return 0;
	
}

正解法一：循环枚举法：

这种方法，就是普通的枚举，正确性容易保证，但是时间复杂度略高

#include "stdio.h" 

int main()
{
	int n;
	while(scanf("%d", &n) != EOF)//法二：嵌套循环法 
	{
		int ans=0;
		while(n)
		{
			ans+=n;
			n--;
		}
		printf("%dnn",ans);
	}
	return 0;
}

正解法二：奇偶判断法

根据奇偶性来决定是用 n nn 去除 2，还是 n + 1 n+1n+1 去除 2，从而避免溢出

#include "stdio.h" 

int main()
{
	int n,ans;
	while(scanf("%d",&n)!=EOF)//法二：奇偶判断法 
	{
		if(n&1)
		{
			ans = (n+1) / 2 * n;
		}
		else
		{
			ans=n / 2 * (n+1);
		}
		printf("%dnn",ans);		
	}
	return 0;
}

正解法三：无符号整型

• 由于无符号整型的范围为 [ 0, 2^{32}-1]，当 n = 65535时，有：
• n × ( n + 1 ) = 2^{32} -2^{16} −1，所以避免了溢出的问题

#include "stdio.h" 

int main()
{
	unsigned int n;
	while(scanf("%d",&n)!=EOF)	//法三：无符合整型 
	{
		printf("%d",n*(n+1)/2);
	}
	return 0;
}

正解法四：长整型

 long long 是64位长整型，范围比int大了一个平方量级，在[-2^{63}, 2^{63}-1]，所以也是能够涵盖 n 最大的情况的，从而避免了溢出

#include "stdio.h" 

int main()
{
	long long n;
	while(scanf("%d",&n)!=EOF)//法四：长整型 
	{
		printf("%lldnn",n*(n+1)/2);
	}
	return 0;
}

实质：

法二、三、四其实都是在错误解法的基础上，避免溢出的三种方法，本质上都是用了qiann项和公式，在以后使用时，也需注意是否溢出的问题