题目

输入一个正整数数N，输出所有和为N连续正整数序列。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。

一种运用数学规律的解法

假定有k个连续的正整数和为N，其中连续序列的第一个数为x，则有x+(x+1)+(x+2)+...+(x+k-1) = N。从而可以求得x = (N - k*(k-1)/2)  /  k。当x的值小于等于0时，则说明已经没有正整数序列的和为N了，此时循环退出。初始化k=2，表示2个连续的正整数和为N，则可以求出x的值，并判断从x开始是否存在2个连续正整数和为N，若不存在则k++，继续循环。

 bool find_sequence(int N)
 {
     bool has = false;
     int k = 2, x, m ;  //k为连续序列的数目，x为起始的值，m用于判断是否有满足条件的值。
     while (true) {
         x = (N - k*(k-1)/2) / k;  //求出k个连续正整数和为N的起始值x
         m = (N - k*(k-1)/2) % k; //m用于判断是否有满足条件的连续正整数值
         if (x <= 0) break;    //退出条件，如果x<=0，则循环退出。
         if (!m) {             //m为0，表示找到了连续子序列和为N。
             has = true;
             output(x, k);
         }
         k++;
     }
     return has;
 }

 void output(int x, int k)
 {
     for (int i=0; i<k; i++) {
         cout << x++ << " ";
     }
     cout << endl;
 }

扩展

问题：是不是所有的正整数都能分解为连续正整数序列呢？

答案：不是。并不是所有的正整数都能分解为连续的正整数和，如32就不能分解为连续正整数和。对于奇数，我们总是能写成2k+1的形式，因此可以分解为[k,k+1]，所以总是能分解成连续正整数序列。对于每一个偶数，均可以分解为质因数之积，即n = pow(2, i)*pow(3, j)*pow(5,k)...，如果除了i之外，j,k...均为0，那么n = pow(2, k)，对于这种数，其所有的因数均为偶数，是不存在连续子序列和为n的，具体证明请看参考资料2。因此除了2的幂之外，所有的正整数n >=3均可以写成一个连续的自然数之和。

另外一种解法

何海涛先生的博客上有另外一种解法，参考如下：

用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，big初始化为2。如果从small到big的序列的和大于n的话，我们向右移动small，相当于从序列中去掉较小的数字。如果从small到big的序列的和小于n的话，我们向右移动big，相当于向序列中添加big的下一个数字。一直到small等于(1+n)/2，因为序列至少要有两个数字。

更直白一点的理解就是先判定以数字2结束的连续序列和是否有等于n的，然后是以3结束的连续序列和是否有等于n的。

 /
 // Find continuous sequence, whose sum is n
 /
 void FindContinuousSequence(int n)
 {
       if(n < 3)
             return;

       int small = 1;
       int big = 2;
       int middle = (1 + n) / 2;
       int sum = small + big;

       while(small < middle)
       {
             // we are lucky and find the sequence
             if(sum == n)
                   PrintContinuousSequence(small, big);

             // if the current sum is greater than n,
             // move small forward
             while(sum > n)
             {
                   sum -= small;
                   small ++;

                   // we are lucky and find the sequence
                   if(sum == n)
                         PrintContinuousSequence(small, big);
             }

             // move big forward
             big ++;
             sum += big;
       }
 }

 /
 // Print continuous sequence between small and big
 /
 void PrintContinuousSequence(int small, int big)
 {
       for(int i = small; i <= big; ++ i)
             printf("%d ", i);

       printf("\n");
 }

参考资料

1 何海涛博客：

：