稀奇古怪的坑爹算法1 等差数列求和问题

雨点打透心脏的1/2处 2023-06-18 07:59 42阅读 0赞

### 最近在做某学校的oj，遇到了这么一个问题，原本是很简单的问题，但是却怎么都不能Accept，最后才找到了解决方案 ###

###### 问题如下:![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2thaW15Yw_size_16_color_FFFFFF_t_70] ######

就是很简单的一个数列求和问题，运用到n\*(1+n)/2公式，答主在做题的时候还在想，是否会出现除法的问题，但是n\*(1+n)一定是一个偶数(证明过程过于简单，就不在这里列举出来了)，所以最后求得的解一定是一个整数，所以，答主最先开始的答案为:

#include<stdio.h>
    int main()
    { 
    int a;
    while(scanf("%d",&a)!=EOF)
    { 
    	printf("%d\n\n",(1+a)*a/2);
    }
    return 0;
    }

后来结果都知道的啦，那就是wronganswer，当时答主还在想，是不是空格啥的出现了问题,后来无论如何的换换行都不行，答主就换了另外一种答案，成功accept。

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

为了区分二者的区别，特意写了一个测试代码，来测试二者的区别，代码里面的65535仅是一个测试值

#include<stdio.h>
    int f1(int n)
    { 
    	if(n%2==0)
    	return n/2*(n+1);
    	else
    	return (n+1)/2*n;
    }
    int f(int n)
    { 
    	return n*(n+1)/2;
    }
    int main()
    { 
    	int i;
    	for(i=0;i<65535;i++)
    	if(f1(i)!=f(i))
    	{ 
    		break;
    	}
    	printf("%d",i);
    }

运行结果如下:  
![在这里插入图片描述][20191201135124915.png]  
这里我们有了新的发现，当i等于46341的时候，两个函数的值的结果是不一样的，这显然不符合我们的意想，我们对46341进行运算，当使用f1时，能够产生正确的结果，当时用f时，不会产生正确的结果。由这个地方我们可以猜测，可能产生了内存溢出的情况。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2thaW15Yw_size_16_color_FFFFFF_t_70 1]

我们知道int类型的最大取值为2147483647(2^31-1)，当我们使用f函数时，  
![在这里插入图片描述][20191201135523938.png]  
发现产生的值为2147534622，超过了int类型所能够表示的最大值，这样会造成内存溢出，产生错误的结果。当我们取值为46340时:![在这里插入图片描述][20191201135629423.png]  
产生的结果为2147441940，刚好在内存范围内，也表示了46341为一个界限值，表示的是当大于等于这个值时，内存会发生溢出，从而产生错误的答案。所以，这也是第一种写法为啥会给wronganswer而不是accept的原因。

### 总结: ###

### 在写类似的算法题的时候，一定要考虑到数字太大导致的内存溢出的情况的发生。可能采用其他的算法，不会导致内存溢出，我们所采用的算法应该尽可能能够适应更大的数。 ###

#### 码字不易，点个赞再走呗。 ####

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2thaW15Yw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191201133040250.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2thaW15Yw==,size_16,color_FFFFFF,t_70
[20191201135124915.png]: https://img-blog.csdnimg.cn/20191201135124915.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2thaW15Yw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191201135958119.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2thaW15Yw==,size_16,color_FFFFFF,t_70
[20191201135523938.png]: https://img-blog.csdnimg.cn/20191201135523938.png
[20191201135629423.png]: https://img-blog.csdnimg.cn/20191201135629423.png