微软100题第51题:和为n连续正数序列
2023-09-11 14:20:59 时间
题目:输入一个正数n,输出全部和为n连续正数序列。比如输入15,因为1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6和7-8。
方法一:记录序列长度。推断首项是否满足条件就可以
首先联想到的就是等差数列,并且方差为1的正数等差数列,我们仅仅须要记录一个序列长度,依据等差数列公式sum = na1+n(n-1)*d/2;我们能够得到na1 = sum - n(n-1)/2;仅仅需推断a1大于0就可以。当中n是我们记录的序列长度。
详细的程序例如以下:
void continuesum(int sum) { int n = 2, na1 = 0; while( n*(n+1) <= 2*sum) { na1 = sum - ((n-1)*n/2); if(na1/ n > 0 && na1 % n==0 ) { int t = na1/n; cout << t << "-" << t+n-1 << endl; } n++; } }方法二:维护序列的首位两个元素值。以及当前序列和
我们还能够採用第二种方法,借鉴点击打开链接。原文中程序存在的问题被解决掉了。其详细做法是基于第一个元素肯定不能大于sum/2。并且最后一个元素不能大于sum的。当当前序列和大于sum时,减去首项,然后首项加一,(就是从序列中去掉第一个元素),当当前序列和小于sum时,尾项加一。即加入元素。
void continuesumother(int sum) { int start=1, ends=2, mid = sum/2, cursum = 3; while(start <= mid && ends < sum) { if(cursum == sum) { cout<<start<<"-"<<ends<<endl; } while(cursum> sum && start < mid) { cursum-=start; start++; if(cursum == sum) { cout<<start<<"-"<<ends<<endl; } } ends++; cursum+=ends; } return ; }
相关文章
- hdu 3308 线段树,单点更新 求最长连续上升序列长度
- Java实现 LeetCode 300 最长上升子序列
- Java实现子序列问题
- (动态规划)最长回文子序列、回文子序列个数
- Python编程:利用python编程实现对基于时间序列的数据(dataframe格式)按照指定时间范围进行单方向关联,不存在的日期补充为默认的NaN
- 【MATLAB】详解时间序列插值计算、日期转换成秒数、获取当前日期
- 【华为云技术分享】序列特征的处理方法之二:基于卷积神经网络方法
- 剑指 Offer II 095. 最长公共子序列-动态规划算法
- 【数字信号处理】线性时不变系统 LTI “ 输入 “ 与 “ 输出 “ 之间的关系 ( 线性卷积起点定理 | 左边序列概念 | 推理 )
- 【数字信号处理】傅里叶变换性质 ( 序列傅里叶变换共轭对称性质 | x(n) 分解为实部序列与虚部序列 | 实部傅里叶变换 | 虚部傅里叶变换 | 共轭对称傅里叶变换 | 共轭反对称傅里叶变换 )
- 求先序序列
- 检测用户命令序列异常——使用LSTM分类算法【使用朴素贝叶斯,类似垃圾邮件分类的做法也可以,将命令序列看成是垃圾邮件】
- 循环神经网络(RNN, Recurrent Neural Networks)——无非引入了环,解决时间序列问题
- 07 串行数据流特定序列循环检测器的设计与功能验证(附源码)