面试题40：输出跟为指定值的连续正数序列

面试题40：输出和为指定值的连续正数序列

思路：

1. 用两个变量分别表示序列的最小值和最大值。首先把他们分别初始化为1和2，
2. 如果从最小值到最大值的序列之和大于给定值，则从序列中去掉最小值，也就是增大最小值；
3. 如果从最小值到最大值的序列之和小于给定值，则增大最大值，让序列包含更多的数字
4. 由于序列中至少有两个数字，我们一直增加最小值到(1+给定值)/2为止。

代码如下：

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

//打印满足要求的连续正数序列，nSmall和nBig分别表示序列的最小值和最大值
void PrintSequence(int nSmall, int nBig)
{
	for (int i=nSmall; i<=nBig; i++)
	{
		cout << i << " ";
	}
	cout << endl;
}

void FindContinousSequence(int nSum)
{
   if (nSum < 3)
   {
	   return;
   }

   int nSmall = 1;
   int nBig = 2;
   int nMid = (nSum + 1) >> 1;
   int nCurSum = nSmall + nBig; 

   while (nSmall < nMid)//循环终止条件
   {
	   if (nCurSum == nSum)
	   {
		   PrintSequence(nSmall, nBig);//打印序列
	   }
	   
	   while (nCurSum > nSum && nSmall < nMid)//当前和比指定值大
	   {
            nCurSum -= nSmall;//从中减掉最小值
			nSmall++;//同时增大最小值
			if (nCurSum == nSum)
			{
				PrintSequence(nSmall, nBig);
			}
	   }

	   //当前和比指定值小
	   nBig++;//增大最大值
	   nCurSum += nBig;//更新当前和
   } 
}

int _tmain(int argc, _TCHAR* argv[])
{
    FindContinousSequence(15);
	system("pause");
	return 0;
}

运行结果：