一,题目
输入一个正数n,输出所有和为n连续正数序列。
例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6和7-8。
二,思路
解法一:连续正序列,不包含n本身。所以子序列中最大元素为 n/2+1
求出到前 i个元素和保存到b数组中,然后遍历数组b ,i>j 时,求b[i] –b[j] ==n。如果等于则输出 j+1 到 I 的序列。
时间复杂度:O(n^2)
#include <iostream>
using namespace std;
void print(int a[],int j,int i)
{
for(int k=j;k<=i;++k)
cout<<a[k]<<" ";
cout<<endl;
}
int main()
{
int n=15;
int a[n];
int b[n];
for(int i=1;i<=n/2+1;++i)
a[i]=i;
b[0]=a[0]=0;
for(int i=1;i<=n/2+1;++i)
{
b[i]=b[i-1] + a[i];
}
for(int i=n/2+1;i>=0;--i)
{
for(int j=i-1;j>=0;--j)
{
if((b[i]-b[j])==n)
{
print(a,j+1,i);
}
}
}
}
解法二:
我们可用两个数small和big分别表示序列的最小值和最大值。
首先把small初始化为1,big初始化为2。
如果从small到big的序列的和大于n的话,我们向右移动small,相当于从序列中去掉较小的数字。
如果从small到big的序列的和小于n的话,我们向右移动big,相当于向序列中添加big的下一个数字。
一直到small等于(1+n)/2,因为序列至少要有两个数字。
#include <iostream>
using namespace std;
void PrintContinuousSequence(int small, int big)
{
for(int i = small; i <= big; ++ i)
printf("%d ", i);
printf("\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)
{
if(sum == n)
PrintContinuousSequence(small, big);
// if the current sum is greater than n,
// move small forward
while(sum > n)//元素偏大
{
sum -= small;
small ++;
if(sum == n)
PrintContinuousSequence(small, big);
}
// move big forward
big ++;
sum += big;
}
}
int main()
{
FindContinuousSequence(15);
}
分享到:
相关推荐
57.和为S的连续正数序列 Array 关注 58.翻转单词序列 String 58.左旋转字符串 String 59.滑动窗口的最大值 Queue 常考 60.n个骰子的点数 61.扑克牌顺子 62.孩子们的游戏 Math 63.股票的最大利润 Math 64.求1...
1.5.10. 输入一个正数 n,输出所有和为 n 连续正数序列 ................................125 1.6. 面试题集合(五) .......................................................................................126...
就在第n行之前插入后续文本,如果I后面没有跟数字,就在当前行之前插入文本,如果输入D,后面跟着m,n,一个数字n或者没有数字,就分别删除m到n行,第n行或者当前行,命令L用于显示文本; 6、 用C++编写求多项式...
16.设m.n均为自然数,m可表示为一些不超过n的自然数之和,f(m,n)为这种表示方式的数目。例f(5,3)=5, 有 5种表示方式:3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1。 ①以下是该函数的程序段,请将未完成的部分填入,...
11.6编写一个函数new,对n个字符开辟连续的存储空间,此函数应返回一个指针(地址),指向字符串开始的空间。new(n)表示分配n个字节的内存空间。 100 11.7写一函数free,将上题new函数占用的空间释放free(p)表示将p...
和为S的连续正数序列 so.42.和为S的两个数字 so.50.数组中重复的数字 so.51.构建乘积数组 so.64.滑动窗口的最大值 lc.15.三数之和 lc.41.缺失的第一个正数 lc.54.螺旋矩阵 lc.88.合并两个有序数组 1.2 链表 题目 ...
和为s的连续正数序列 10、 58-I. 翻转单词顺序 11、58-II. 左旋转字符串 12、66. 构建乘积数组 二、栈和队列 1、06. 从尾到头打印链表 2、09.用两个栈实现队列 3、30.包含min函数的栈 4、59-I. 滑动窗口 5、59-II. ...
例2.1 可以定义一个名为students的原始集,它具有成员John、Jill、Rose和Mike,属性有sex和age: sets: students/John Jill, Rose Mike/: sex, age; endsets ② 当隐式罗列成员时,不必罗列出每个集成员。可采用...
当按二、八、十六进制输出时,是按其补码形式输出,最高位是符号位(正数为0、负数为1)。 所以此法可得到一个负数的补码表示。 (1)按二进制输出 %b或%B %b等价与%B。 %b 12 = 0b1100 %b 0xffffffff = 0b1111 ...
(2) 序列“001”的输入如果直接输入“001”,系统会自动判断001为数据1,解决办法是:首先输入“'”(西文单引号),然后输入“001”。(3) 日期的输入如果要输入“4月5日”,直接输入“4/5”,再敲回车就行了。...