【题 目】输入一个整数，输出所有和为n的连续正数序列。例如：输入15，由于15=7+8=4+5+6=1+2+3+4+5，所以输出的序列为『1，2，3，4，5』；『4，5，6』，『7，8』三个。

【思路1】从等差数列的观点考虑：如果有一列数满足i+(i+1)+...+j=n,根据等差数列的求和公式，我们容易得到：(i+j)(j-i+1)/2=n,即(i+j)(j-i+1)=2n,由于i，j均为正整数，我们容易得到(i+j),(j-i+1)也都为正整数，所以都是2n的因子，我们就可以从2到sqrt(2n)遍历2n的所有因子，对于其中的因子k，我们有：

我们只需要保证j，i的值都为整数，并且i

1 #include

2 #include

3 #include

4 using namespace std;

5

6 void FindContinuousSequence(int n)

7 {

8 int half = (int)(sqrt(2*n));

9 for(int k = 2;k <= half;++k)

10 {

11 //找到因子k12 if((2*n) % k == 0)

13 {

14 int temp1 = 2 * n - k*k + k;

15 int temp2 = 2 * n + k*k - k;

16

17 //开始数start，结束数end都为整数18 if(temp1 % (2*k) == 0 && temp2 % (2*k) == 0)

19 {

20 int start = temp1 / (2*k);

21 int end = temp2 / (2*k);

22

23 //打印从start到end之间的所有数24 for(int i = start;i <= end;++i)

25 cout<

26

27 cout<

28 }

29 }

30 }

31 }

32

33 int main()

34 {

35 cout<

36 int number = 0;

37 cin >>number;

38

39 cout<

40 FindContinuousSequence(number);

41 return 0;

42 }

运行结果如下：

容易看出，这种算法需要遍历的范围是从２—sqrt(2n)，因而时间复杂度为O(sqrt(n))，效率还算是比较高的，然而缺点是要计算很多的乘除，乘方运算，对于n值较大输入，计算过程会相对较慢。

【思路2】我们从另一角度考虑这个问题，我们根据【算法10】中从两端想中间夹逼求解的基本思想，可以这样考虑：我们用一个small指示序列中最小值，用big指示序列中的最大值，因为和为n的序列至少需要两个数字，因而small取值从1到中点；如果small+bign，就让small前移，以此缩小sum；如果small+big==n，打印从small到big之间的所有值即可。基于这种思路的代码为：

1 #include

2 #include

3 using namespace std;

4

5 void FindContinuousNumbers(int n)

6 {

7 int small = 1;

8 int big = 2;

9 int middle = (n + 1)/2;

10 int sum = small + big;

11 while(small < middle)

12 {

13 if(sum == n)

14 {

15 for(int i = small;i <= big;++i)

16 cout<

17 cout<

18 }

19

20 while(sum > n)

21 {

22 sum -=small;

23 small++;

24

25 if(sum == n)

26 {

27 for(int i = small;i <= big;++i)

28 cout<

29

30 cout<

31 }

32

33 }

34

35 big++;

36 sum += big;

37 }

38 }

39

40 int main()

41 {

42 cout<

43 int number = 0;

44 cin>>number;

45

46 cout<

47 FindContinuousNumbers(number);

48

49 return 0;

50 }

运行结果如下图：

效率分析：small指针要从1开始遍历到middle，而big指针则对于每一个small指针一直往前遍历，不存在指指针回溯的情况，因而整个算法的时间复杂度为O(N)，效率较之前的算法的低，然而所有的操作都是简单的加减法，相比之前需要大量的乘法运算是一个优势。

References:

注：

1)本博客所有的代码环境编译均为win7+VC6。所有代码均经过博主上机调试。

2)博主python27对本博客文章享有版权，网络转载请注明出处http://www.cnblogs.com/python27/。对解题思路有任何建议，欢迎在评论中告知。