[ Javascript ] - 20140623-题目1

[ Javascript ] - 20140623-题目1

输入一个自然数 n，输出所有可能和为 n 连续正数序列。
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，
所以输出 3 个连续序列1,2,3,4,5、4,5,6 和7,8。

PS:
1. 回复时注意加上下面这句话，才会有语法高亮或格式缩进。
```javascript
// you code
```
2. 粘贴代码时请使用shift+tab，缩进前面的空白。

思路是把本题看做等差数列。
Sn = n * a1 + n * (n - 1) * d / 2
其中Sn是和，n是项数，a1是首相，d是公差（本题中d=1）。
这样，在已知和Sn的情况下，遍历n和a1就行了，算法时间复杂度为线性。
PS：@itbeihe，北河兄的算法好像错了，比如getArr(10)输出了["5,6", "1,2,3,4"]。

function subAnswer(start, count) {
    var result = [];
    while(count--) {
        result.push(start++);
    }
    return result;
}
function getSequence(sn) {
    var result = [], n, a1;
    var end = Math.ceil(sn / 2);

    for (n = 2; n <= end; n++) {
        a1 = (2 * sn - n * n + n) / (2 * n);
        if (a1 && /^\d+$/g.test(a1)) {
            result.push(subAnswer(a1, n));
        }
    }
    return result.length ? result.join("=").replace(/,/g, "+") + "=" + sn : sn;
}

alert(getSequence(15));