输入一个正数n,输出所有和为n的连续正数序列

时间:2022-08-23 08:32:09

题目:输入一个正数n,输出所有和为n的连续正数序列

举例:输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1,2,3,4,5;4,5,6;7,8。

解法一:开辟一个大小为n/2 + 1(n为奇数,n为偶数则大小为n/2 - 1)的数组,值从1到n。两个指针p1指向1,p2指向p1的下一个。然后循环,如果p1和p2之间的元素和小于n,p2++;大于n,p1++;等于n,则输出之后p1,p2同时后移。直到p2走完数组,循环结束。这种方法时间复杂度为O(n),空间复杂度为O(n)。

答:

输入一个正数n,输出所有和为n的连续正数序列
#include "stdafx.h"
#include
<iostream>

using namespace std;

//求和为n的连续正数序列
void FindSequenceNumber(int n)
{
if (n <= 0)
{
return;
}
int first = 1;
int last = 2;
int end = (n + 1) / 2;
int sum = 1;
while (first <= end) //序列必定有两个及以上
{
if (sum == n)
{
for (int i = first; i < last; i++)
{
cout
<<i<<" ";
}
cout
<<endl;
sum
-= first;
first
++;
}
else if (sum < n)
{
sum
+= last;
last
++;
}
else if (sum > n)
{
sum
-= first;
first
++;
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
FindSequenceNumber(
15);
return 0;
}
输入一个正数n,输出所有和为n的连续正数序列

运行界面如下: