第一题：连续正整数（10分）

题目描述：
一个正整数有可能可以被表示为n(n>=2)个连续正整数之和，如：
15=1+2+3+4+5
15=4+5+6
15=7+8
请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。

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

输出数据：在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔。如果没有符合要求的序列，输出“NONE”。
例如，对于15，其输出结果是：
1 2 3 4 5
4 5 6
7 8
对于16，其输出结果是：
NONE
评分标准：
程序输出结果是否正确。

原题：http://hi.baidu.com/astar/blog/item/69570fb35eedeba6d9335ab5.html

我见到的C++优化最好的代码的平均运行时间（若输入10000000）为0.15秒。

我设计的优化C#代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

using System;
 
using System.Text;
 
 
 
namespace test
 
{
 
    public class test
 
    {
 
        static void Main()
 
        {
 
            bool has = false;
 
            Console.Write("Input Int:");
 
            int a;
 
            if (int.TryParse(Console.ReadLine(), out a) && a > 0)
 
            {
 
                int t = Environment.TickCount;
 
                int max = a / 2 + 1;
 
                int s = 0;
 
                StringBuilder str = new StringBuilder ();
 
                for (int i = 1; i < = max; i++)
 
                {
 
                    s = i;
 
                    for (int ii = i + 1; ii <= max; ii++)
 
                    {
 
                        s += ii;
 
                        if (s == a)
 
                        {
 
                            has = true;
 
                            for (int iii = i; iii <= ii; iii++)
 
                            {
 
                                str.Append(iii);
 
                                str.Append(" ");
 
                            }
 
                            str.Append(";rn");
 
                            break;
 
                        }
 
                        if (s > a)
 
                        {
 
                            break;
 
                        }
 
                    }
 
                }
 
                if (!has)
 
                {
 
                    Console.WriteLine("None");
 
                }
 
                t = Environment.TickCount - t;
 
                Console.WriteLine(str);
 
                Console.WriteLine("Time:{0:###.########}", (double)t/1000);
 
                GC.Collect();
 
                Main();
 
            }
 
            else
 
            {
 
                return;
 
            }
 
        }
 
    }
 
}

输入10000000用时0.25秒。说明C#在数值计算上和C++还是有差距的。

[原创 2007-08-24 10:37:43]