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

1.思路

尊崇以下策略：

(1)对于固定的left.当前sum值小于目标Sum，则right一直后移

(2).sum==Sum。则输出序列，且将right后移

(3)对于固定的right.,sum>Sum时，始终将left左移动

2.代码

void print(const int& left,const int& right){

	static int flag=0;//局部静态变量，仅仅初始化1次

	cout<<"NO:"<<++flag<<"--";

        for(int i=left;i<=right;i++)

		cout<<i<<" ";

	cout<<endl;

}

void findSequence(const int& Sum){

       int left=1,right=1,sum=1;

	   while(left<=Sum/2){

			if(sum==Sum){

			    print(left,right);

			    right++;

				sum+=right;

			}

			else if(sum>Sum){

				sum-=left;

				left++;

			}

			else{

				right++;

				sum+=right;

			}

	   }

}

或者更加简短的，写作：

void findSequence(int Sum){

	int left=1,right=1,sum=1;

	while(left<=Sum/2){

		while(sum>Sum){

		    sum-=left;

		    left++;

		}

		if(sum==Sum)

			   print(left,right);

		right++;

		sum+=right;

	}

}

即每一次大循环中都将right后移，在循环体内，若sum>Sum则将left左移动。相等时则输出。

3.特殊情况

题目：输入两个整数n和m，从数列1,2,3...n中随意取几个数，使其和等于m，要求列出所有的组合。

分析。这里，从最大的数开始，对于每一个数，无非存在两种形式。即参与查找和不参与查找。使用递归即可。参与查找时，对应的n减小且和也减小。不参与查找时，只有n减小，和不变化。

#include <iostream>

#include <list>

using namespace std;

list<int> list1;

void find_factor(int sum,int n)

{

    //递归出口

    if(n<=0||sum<0)

        return;

    //输出找到的数

    if(sum==n)

    {

        list1.reverse();

        for(list<int>::iterator iter=list1.begin();iter!=list1.end();iter++)

            cout<<*iter<<"+";

        cout<<n<<endl;

        list1.reverse();

    }

    list1.push_front(n);

    find_factor(sum-n,n-1);//n参与查找

    list1.pop_front();

    find_factor(sum,n-1);//n不参与查找

}  

int main(void)

{

    int sum,n;

    cin>>sum>>n;

    cout<<"所有可能的序列，如下："<<endl;

    find_factor(sum,n);

    return 0;

}

巴特西

每天一道算法题(12)——和为n的连续正数序列或者随机数

1.思路

2.代码

3.特殊情况

最新文章

热门文章