蓝桥杯算法训练 - 连续正整数的和 78这个数可以表示为连续正整数的和，1+2+3，18+19+20+21，25+26+27。　　输入一个正整数 n(＜=10000) 　　输出 m 行(n有m

客官°小女子只卖身不卖艺 2022-12-13 00:44 100阅读 0赞

## 问题描述 ##

78这个数可以表示为连续正整数的和，1+2+3，18+19+20+21，25+26+27。  
　　输入一个正整数 n(<=10000)  
　　输出 m 行(n有m种表示法)，每行是两个正整数a，b，表示a+(a+1)+…+b=n。  
　　对于多种表示法，a小的方案先输出。  
**例子**

**样例输入**  
78  
**样例输出**  
1 12  
18 21  
25 27  
**数据规模与限制**

时间限制：1.0s 内存限制：256.0MB  
**提示**

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0  
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。  
注意: 所有依赖的函数必须明确地在源文件中 \#include ， 不能通过工程设置而省略常用头文件。  
提交时，注意选择所期望的编译器类型。

## 思路： ##

只需要用两个循环找出两个数，然后再用一个循环判断这两个数之间的数相加等不等于n就行了。  
不过有趣的是，如果不加一些条件，输出结果时就会超时。  
在下面会用3段代码举例子。  
1）超时代码：

#include <stdio.h>
    int main ()
    { 
    	int n;
    	scanf("%d",&n);
    	
    	int i,j,k,sum;
    	
    	for(i=1;i<n;i++)
    	{ 
    		
    		for(j=i+1;j<n;j++)
    		{ 
    			sum=0;
    			for(k=i;k<=j;k++)
    			{ 
    				sum+=k;
    			}
    			if(sum == n)
    			{ 
    				printf("%d %d\n",i,j);
    				break;
    			}
    		}
    	}
    	return 0;
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70_pic_center]  
可以看到基本都超时了。

2）不超时的AC代码：

#include <stdio.h>
    int main ()
    { 
    	int n;
    	scanf("%d",&n);
    	
    	int i,j,k,sum;
    	
    	for(i=1;i<n;i++)
    	{ 
    		
    		for(j=i+1;j<n;j++)
    		{ 
    			sum=0;
    			for(k=i;k<=j;k++)
    			{ 
    				sum+=k;
    				if(sum>n)//如果发现大于n了，那么后面的一定都大于n，break；
    					break;
    			}
    			if(sum == n)
    			{ 
    				printf("%d %d\n",i,j);
    				break;
    			}
    		}
    	}
    	return 0;
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70_pic_center 1]  
发现基本都大于100ms，能不能更快呢？  
3）比较高效率的代码

#include <stdio.h>
    int main ()
    { 
    	int n;
    	scanf("%d",&n);
    	
    	int i,j,k,sum;
    	int flag=0;
    	for(i=1;i<n;i++)
    	{ 
    		flag=0;
    		for(j=i+1;j<n;j++)
    		{ 
    			sum=0;
    			for(k=i;k<=j;k++)
    			{ 
    				sum+=k;
    				if(sum>n)
    				{ 
    					flag = 1;//如果超过了，那么下一层循环肯定也会超过，做出标记，在下一层循环也直接break；
    					break;
    				}
    			}
    			if(flag==1)//如果发现标记了，就break；
    				break;
    			if(sum == n)
    			{ 
    				printf("%d %d\n",i,j);
    				break;
    			}
    		}
    	}
    	return 0;
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70_pic_center 2]  
可以看到基本都在1ms了，一个简单的优化就可以节约约百毫秒，还挺有趣的…

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/04093417b4f842828a334c8afe1cf6ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/54998617530244a2bb0b0a049d83a5c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/cbec28abb5924764b9c691868a045905.png