循环结构——连续正整数

【问题描述】

一个正整数有可能可以被表示为n(n>=2)个连续正整数之和，如：
15=1+2+3+4+5
15=4+5+6
15=7+8
请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。

【输入形式】

从控制台输入一个正整数（小于等于10000）。

【输出形式】

在标准输出上输出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔，每个序列最后一个整数后要有一个空格。如果没有符合要求的序列，输出“none”。

【输入样例1】

15

【输出样例1】

1 2 3 4 5
4 5 6
7 8

【输入样例2】

16

【输出样例2】

none

【样例说明】

样例1输入的是15，其连续正整数序列有3个，分别输出。样例2输入的是16，没有连续的正整数序列之和为16，所以输出字符串：none。

解析：
思路应该比较容易想到，就是从定义i从1开始往后循环，定义j从i开始往后面的数找，定义sum和num分别记录j循环找到某一个数的时候从i到j一串数字之和和有几个数字。
需要注意的是，sum和num在每次i开始新一轮循环的时候要清零。
那么还有一个问题：怎么判断是否存在符合条件的连续若干个正整数？
这时候，需要bool类型变量帮忙。
bool类型变量只占一个字节，相比于int等其他数据类型，bool说占用的程序空间是比较小的（不过计算机发展到现在基本不存在空间不够用的程序）。bool类型的变量只允许存在true或false（也可以写作1或0），像一盏灯，只有亮或者不亮两种状态。
比方说：
bool b=true（也可以写成bool b=1）好比灯亮着
bool c=false（也可以写成bool c=0）就像灯灭了

那么运用到这个程序上面，我们就可以先初始化灯是灭的，即定义一个bool类型的变量bool b=0，然后开始执行程序。当找到一串符合条件的连续正整数的时候，就把灯点亮，即赋值b=1。等所有循环结束，如果灯还没亮，即b=0，那么久代表不存在符合条件的连续正整数，输出"none"。

AC代码如下：

#include
using namespace std;
int main()
{
	int n,sum,num;//sum用来计连续数字的和，num记录是连续几个数字 
	bool b=0;//记录是否存在，若存在则改b=true 
	cin>>n;
	for(int i=1;i<n;i++)
	{
		sum=0;//每次循环要初始化清零 
		num=0;//每次循环要初始化清零 
		for(int j=i;j<=n;j++)
		{
			sum+=j;
			num++;
			if(sum==n)
			{
				b=1;//存在条件，不要输出none 
				for(int k=j-num+1;k<=j;k++)//开始输出num个数 
					cout<<k<<" ";
				cout<<endl;
			}
		}
	}
	if(!b) cout<<"none"<<endl;
}

程序优化

以上思路应该不难想到。可是程序运行除了保证结果正确以外，还要尽可能让运行时间短。试想一下，如果你打一个很高级很好玩的游戏，却总是卡机，恐怕你心态都崩了吧？
程序怎么优化呢？就循环结构而言，要尽可能减少循环次数；换句话说，可以删掉一些不必要的循环或者当条件满足没必要继续循环的时候主动跳出循环，即break和continue的使用。
对于这道题而言，可以怎么优化呢？
我们不妨逐个循环进行分析。
i循环，也就是开始找符合条件连续正整数中的第一个数字，它一定不可能大于n/2（整除），例如55=27+28, 27<=55/2（整除）。
所以：i循环中变量i的范围就是[1,n/2（整除）]。这样一来，工作效率增加一一倍。
接下来我们看看j循环，也就是从i开始往后面找数相加的循环。虽然不确定要找多少个，但是j一定不会大于(n+1)/2（整除）。就好比55=27+28，不可能存在i=27时，j还找到29，所以变量j的变化范围就是[i,(n+1)/2（整除）]。这样一来，是不是程序运行效率又提升许多？
当然，我们还可以进一步优化。
举个例子：当我们输入11且i循环执行到i=3，j=5的时候，此时sum=3+4+5=12>11了，可是j循环还没有结束——j<=(n+1)/2（整除）即j<=6，那么我们还有必要继续找下去吗？此时，就应该用break主动跳出循环了。或者当输入15，已经找到15=1+2+3+4+5+6，在输出完成之后j循环也没有必要执行到j=8了，也主动break跳出循环。
经过三次优化，程序运行效率是大大提高了的，运行时间也非常短。
就这道题目而言，其实优不优化都能过且不会超时。但是最好有优化程序的思想，等到后面学到深搜dfs的时候剪枝（一种优化程序的方法）就非常重要了。顺便提一句，剪枝（优化）不能剪去含有正确答案的枝条，不然剪枝是没有任何意义的。

经过优化的代码如下：

#include
using namespace std;
int main()
{
	int n,sum,num;//sum用来计连续数字的和，num记录是连续几个数字 
	bool b=0;//记录是否存在，若存在则改b=true 
	cin>>n;
	for(int i=1;i<=n/2;i++)
	{
		sum=0;//每次循环要初始化清零 
		num=0;//每次循环要初始化清零 
		for(int j=i;j<=(n+1)/2;j++)
		{
			sum+=j;
			num++;
			if(sum>n) break;//不符合条件了，没必要再循环下去 
			if(sum==n)
			{
				b=1;//存在条件，不要输出none 
				for(int k=j-num+1;k<=j;k++)//开始输出num个数 
					cout<<k<<" ";
				cout<<endl;
				break;
			}
		}
	}
	if(!b) cout<<"none"<<endl;
}

循环结构尾声
作为循环结构的最后一题，我认真地就目前浅薄的知识储备来写下这篇文章。
对比一下两个程序的运行时间

未优化	优化
0.00515s	0.00420s

不就是0.001秒的差别吗？不！ 天壤之别！这一点点时间计算机可以处理很多条指令、进行很多次运算！优化对于这道题目而言可能就是时间的差别，可是等学到深搜dfs的时候剪不剪枝就是满分和部分分的区别了——可能不剪枝程序运行的结果也是对的，但是没拿到分——因为超时运行了。

手敲文字不易，麻烦各位看官点个赞关注我一下，谢谢！
关注我，可以看到更多内容哦！