学步园

51.和为 n 连续正数序列。
题目：输入一个正数 n，输出所有和为 n  连续正数序列。

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

/*
51.和为 n 连续正数序列。
题目：输入一个正数 n，输出所有和为 n  连续正数序列。
例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。

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

但是对于n比较大的 是不切实际的。 

方法2
假设：n=i+(i+1)+...+(j-1)+j, 所以： n = (i+j)(j-i+1)/2 = (j*j-i*i+i+j)/2
=> j^2+j+(i-i^2-2n)=0   => j=sqrt(i^2-i+1/4+2n)-1/2 
1<=i<j<=n/2+1
So for each i in [1, n/2], do this arithmetic to check if there is a integer answer.
*/ 
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

void findConsecutiveSequence2(int n) 
{
	
		for (int i=1;i<=n/2;i++) 
		{
			double j2=sqrt(4*i*i+8*n-4*i+1)-1;//求出是2j 
			if (j2==0) continue;
			if ((j2-int(j2))==0)//如果2j是整数 
			{
				for(int k=i;k<=j2/2;k++)
					printf("%d ",k);
				cout<<endl;
			}
		}
}

void findConsecutiveSequence(int n)
{
	if(n<3)
		return;

	int nSmall=1;
	int nBig=2;
	int nMiddle=(n+1)/2;
	int nSum=nSmall+nBig;

	while(nSmall<nMiddle)
	{
		if(nSum==n)
		{
			for(int i=nSmall;i<=nBig;i++)
			{
				cout<<i<< " ";
			}
			cout<< endl;
		}

		while(nSum>n)//大于n，减去左边的，直到小于n 
		{
			nSum-=nSmall;
			nSmall++;

			if(nSum==n)
			{
				for(int i=nSmall;i<= nBig;i++)
				{
					cout<<i<<" ";
				}
				cout<<endl;
			}
		}

		nBig++;
		nSum+=nBig;
	}
}

int main()  
{  

	cout<<"和为15的连续正数序列为（方法1）："<<endl;
    findConsecutiveSequence2(15); 
    cout<<"和为15的连续正数序列为（方法2）："<<endl;
	findConsecutiveSequence(15);  
	
	cout<<"********************************************"<<endl;
	cout<<"和为30的连续正数序列为（方法1）："<<endl;
    findConsecutiveSequence2(30); 
    cout<<"和为30的连续正数序列为（方法2）："<<endl;
	findConsecutiveSequence(30); 
    return 0;  
}