[编程题] 翻转数列--附详细分析思路

今天逛博客看到这样一道题

翻转数列

小Q定义了一种数列称为翻转数列: 给定整数n和m, 满足n能被2m整除。对于一串连续递增整数数列1, 2, 3, 4..., 每隔m个符号翻转一次, 最初符号为'-';。 例如n = 8, m = 2, 数列就是: -1, -2, +3, +4, -5, -6, +7, +8. 而n = 4, m = 1, 数列就是: -1, +2, -3, + 4. 小Q现在希望你能帮他算算前n项和为多少。

输入描述:

输入包括两个整数n和m(2 <= n <= 109, 1 <= m), 并且满足n能被2m整除。

输出描述:

输出一个整数, 表示前n项和。

输入例子1:

8 2

输出例子1:

8

通过读题不难发现:在一个数列中求前n项的和与m,n的关系

我们先来分析一下数组,递增的,连续.每过m个数,符号翻转一次,前n项翻转 n/m 次 即是说我们把n分成了n/m段

仔细分析每次翻转,我们可以发现 我们可以将"连续的-"号和"+"号的二段合并一下求值 那么前n项就被分成了n/2m

那么我们来看一下 一段"连续的-"号和"+" 的和是多少 拿第一个加号值加上第一个减号值,差值刚好是m,在这一段数字中 恰好有m个m

以 n = 8, m = 2, 数列是: -1, -2, +3, +4, -5, -6, +7, +8.为例

将数组看成-1, -2, +3, +4 和-5, -6, +7, +8组合而成

前一部分3-1+4-2=4

后一部分7-5+8-6=4

(8/(2*2))*2*2 = 8

于是得出公式

前n项的和为 (n/2m)*mm