1. 问题描述
一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,如:
15=1+2+3+4+5,15=4+5+6,15=7+8
请写出算法,根据输入的任何一个正整数,输出符合这种要求的所有连续正整数序列,每个序列都按从小到大的顺序输出。如果没有符合要求的序列,输出“NONE”。
2. 算法分析
我们记这个正整数是 num,题目中的 “一个正整数有可能可以被表示为n(n>=2)个连续正整数之和” 是什么意思呢?如果我们学过等差数列,我们知道,这表示一个正整数可以表示为一个长度为n,公差 d=1 的等差数列。题目的一般规律有了,我们借助等差数列的特点来分析本题目。
记这个等差数列为,这里面的 n 待定,这个等差数列的和就是 num。利用等差数列求和公式可以进行如下表述:
等差数列的首项
首先, 要是个正数
同时 也要是个整数
上式中的 mod 表示求余,如果能整除 2*n,那么就满足了整数条件。
对于 n,可以设置一个初值为2 每次递增 1 的一个循环, 直到不满足上面的正数条件。每个满足条件的 n 记录在数组 a 中,这样方便进行输出。输出时,我们可以根据 n 值和公式 (1)直接确定 ,再利用
依次输出就好了。
我们按照上面的流程进行手动测试,假如 num = 15,则有如下步骤:
当 n = 2时,公式(2)fenzi = 2*15 - 2 = 28; 公式(3)fenzi mod (2*2) == 0 成立。这时根据公式(1),有;公式(4),有 。当 n = 3时,公式(2)fenzi = 2*15 - 6 = 24; 公式(3)fenzi mod (2*3) == 0 成立。这时根据公式(1),有;公式(4),有 。当 n = 4时,公式(2)fenzi = 2*15 - 12 = 18; 公式(3)fenzi mod (2*4) == 0 不成立,跳过。当 n = 5 时,公式(2)fenzi = 2*15 - 20= 10; 公式(3)fenzi mod (2*5) == 0 成立。这时根据公式(1),有;公式(4),有 。当 n = 6 时,公式(2)fenzi = 2*15 - 30 > 0 不成立,结束循环。
如何输出就不展示了,不是本问题的关键,下面直接给出流程图。
3. 流程图
4. 测试结果
num = 15num = 16num = 30num = 100如果对怎么不换行输出或换行输出不了解,可以参考我之前发布的一篇博客Raptor-输出换行与不换行设置
原创不易,敲公式敲的我头皮发麻,这个公式编辑器的语法跟 Latex 还有些不兼容,所以有的是用公式编辑器,有的直接在正文里敲的,但是应该不影响阅读,体会思想就好。如果觉得有帮助,可以进行打赏,苍蝇再小也是肉,也能鼓舞我的创作积极性,谢谢啦!
如果觉得《Raptor-一个正整数表示为n连续正整数之和》对你有帮助,请点赞、收藏,并留下你的观点哦!