一路百度算法比赛题

一道百度算法比赛题
请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。

输入数据：一个正整数，以命令行参数的形式提供给程序。

输出数据：在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔。如果没有符合要求的序列，输出“NONE”。

例如，对于15，其输d出结果是：
1 2 3 4 5
4 5 6
7 8

对于16，其输出结果是：
NONE

求各路高手贴代码，记得写注释！
[解决办法]

引用:

4楼的点子非常好，通过组合数量count来遍历，效率非常高。（每个组合都是连加的，所以每个组合数量只会对应一种情况）

我在这里，就4楼的基础，修改一下，通过数学的简化，来提高遍历效率
思路：
1、上面所述，通过组合数量count来遍历；
2、那count什么时候结束呢？原来是【count> value/2】。但试想，每次都是从value/2从两边分别找元素，所以，只要【value/2 - count/2 = 0】，证明小的那边已经到头了。
所以结束条件可以写成：【value/count - (count/2) >= 0】，这样能减少30%的遍历次数。
3、对连加的组合，value/count为中间值，value*2/count为组合一头一尾的和，而且为正整数。
所以，符合要求的都有【value*2 % count == 0】，就是说两头加起来的和为正整数。
这样能快速定位哪些组合符合要求，原是每个组合都for求和。
4、由于value*2/count为两头和，所以-count+1后再除以2，就是组合中的最小值min 。

具体见下面代码：      (已经很简洁了吧)

    public static void main(String[] args) {
        int inputNum = 21;  
        getPlus_3();
    }
    /**
     * 通过数学方法来提高效率
     */
    public static void getPlus_3() {
        int value = 21;
        for (int count = 2; value / count - (count / 2) >= 0; count++) {
            if (value * 2 % count == 0) {
                int min = (value * 2 / count - count + 1) / 2;
                if (min > 0) {
                    int max = min + count - 1;
                    System.out.println(getStr(min, max));
                }
            }
        }
    }
    /**
     * 从begin到end，打印序列
     */
    public static String getStr(int begin, int end) {
        StringBuffer sb = new StringBuffer();
        for (int i = begin; i <= end; i++) {
            sb.append(i + " ");
        } 
 
        return sb.toString();
    }

[解决办法]

private static Map<Integer, Integer> getList(int X) {
        Map<Integer, Integer> result = new TreeMap<Integer, Integer>();
        for (int m = 2; m < Math.sqrt(X+X); m++) {
            int n = (2 * X / m - m + 1) / 2;
            if ((n + n + m - 1) * (m) / 2 == X) {
                result.put(n, m);
            }
        }
        return result;
    }

算法循环部分优化了一下

查看更多 下一篇