天天看点

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

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 的等差数列。题目的一般规律有了,我们借助等差数列的特点来分析本题目。

记这个等差数列为 

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

,这里面的 n 待定,这个等差数列的和就是 num。利用等差数列求和公式可以进行如下表述:

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

等差数列的首项

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

首先,

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

要是个正数

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

同时

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

也要是个整数

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

上式中的 mod 表示求余,如果能整除 2*n,那么就满足了整数条件。

对于 n,可以设置一个初值为 2 每次递增 1 的一个循环, 直到不满足上面的正数条件。每个满足条件的 n 记录在数组 a 中,这样方便进行输出。输出时,我们可以根据 n 值和公式 (1)直接确定

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

,再利用

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

依次输出就好了。

我们按照上面的流程进行手动测试,假如 num = 15,则有如下步骤:

  • 当 n = 2 时,公式(2)fenzi = 2*15 - 2 = 28; 公式(3)fenzi mod (2*2) == 0 成立。这时根据公式 (1),有 
    Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果
    ;公式(4),有
    Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果
  • 当 n = 3 时,公式(2)fenzi = 2*15 - 6 = 24; 公式(3)fenzi mod (2*3) == 0 成立。这时根据公式 (1),有 
    Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果
    ;公式(4),有
    Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图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),有 
    Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果
    ;公式(4),有
    Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果
  • 当 n = 6 时,公式(2)fenzi = 2*15 - 30 > 0 不成立,结束循环。

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

3. 流程图

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

4. 测试结果

  • num = 15
Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果
  • num = 16
Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果
  • num = 30
Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果
  • num = 100
Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

如果对怎么不换行输出或换行输出不了解,可以参考我之前发布的一篇博客 Raptor-输出换行与不换行设置

原创不易,敲公式敲的我头皮发麻,这个公式编辑器的语法跟 Latex 还有些不兼容,所以有的是用公式编辑器,有的直接在正文里敲的,但是应该不影响阅读,体会思想就好。如果觉得有帮助,可以进行打赏,苍蝇再小也是肉,也能鼓舞我的创作积极性,谢谢啦!

Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果
Raptor-一个正整数表示为n连续正整数之和1. 问题描述2. 算法分析3. 流程图4. 测试结果

继续阅读