失眠网 > Raptor-一个正整数表示为n连续正整数之和

Raptor-一个正整数表示为n连续正整数之和

时间：2020-05-21 07:22:35

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 不成立，结束循环。

如何输出就不展示了，不是本问题的关键，下面直接给出流程图。