剑指Offer——输入正整数S,打印出所有和为S的连续正数序列（至少含有两个正数）

180 阅读 0 评论 119 点赞

我是靠谱客的博主激昂饼干，这篇文章主要介绍剑指Offer——输入正整数S,打印出所有和为S的连续正数序列（至少含有两个正数），现在分享给大家，希望可以做个参考。

主要思路：

定义两个数从1，2开始增长，求这两个数之间所有数的和，如果等于S则打印输出，如果大于则让小的数增长，否则让大的数增长，增长后重现判断和是否等于S,在循环中执行直到小的数大于等于（1+S）/2。用到了一个小小的技巧，就是求两个数中间的数之和时，保存了上一次的值，新的值只需要减去小的数，或者加上大的数即可。

以下代码在VS2015中调试通过：

#include "stdafx.h"
#include<iostream>
using namespace std;

void PrintContinuousSequence(int small, int big)
{
	printf("the nums is:n");
	for (int j = small; j <= big; ++j)
	{
		printf("%d	", j);
	}
	printf("n");
}


bool  FindContinuousSequence(int sum)
{
	if (sum<3)
		return false;
	int small = 1;
	int big   = 2;
	int middle = (1 + sum)/2;
	int curSum = small + big;
	while (small < middle)
	{
		if (curSum == sum)
			PrintContinuousSequence(small, big);
		while (curSum > sum && small < middle)
		{
			curSum -= small;
			small++;
			if(curSum == sum)
				PrintContinuousSequence(small, big);
		}
		big++;
		curSum += big;
	}
	return true;
}

int main()
{
	int sum = 0;
	cin >> sum;
	if (!(FindContinuousSequence(sum)))
		printf("can't find!");
	while (1);
	return 0;
}