一道百度之星编程大赛算法题的随笔联想

编程工具(ATOM)v1.41.0免费版

类型：编程工具大小：180.9M语言：中文评分：10.0
标签：

立即下载

百度之星，是全球最大的中文搜索引擎，百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛。他所考试的题目，全部都是算法的题目。

鄙人虽然是一个.net程序员，在工作之余，喜爱算法。我觉得这个题目有点意思，故而分享给大家，我想到两种方法，提供大家，希望对大家起了一个开阔思路的作用。

首先，看题目是那样的：

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

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

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

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

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

我这里提供2种算法的解法，起一个抛砖引玉的作用

方法一：可以从后往前的计算，由大到小的计算。这种计算模式有几个思考的步骤。

①由于使计算吗，我可以考虑从输入的数字的一半（奇数使其中间数）开始遍历。于是我就有这样一种算法。相应伪代码如图所示：

相应的源代码如下：

1        Console.WriteLine("请你输入一个数字");
2             int mI = int.Parse(Console.ReadLine());
3             int temp = mI;
4            //是否能够拆成n个连续的数字的表计量
5             bool find = false;
6             int temp1 = 0;
7             //记录最终的结果
8             List<string> strs = new List<string>();
9                //凭借成最终的字符串
10              string tempstr = string.Empty;
11              //进行循环拆解
12             for (int i = (mI - 1) / 2 + 1; i >= 1; i--)
13             {
14                 //这一元素做差了
15                 temp = temp - i;
16                 temp1 = temp;
17                 tempstr = tempstr + i.ToString()+",";
18                    //等于了有进一步做数据重置的操作
19                   if (temp == 0)
20             {
21                 tempstr = tempstr.Remove(tempstr.Length - 1);
22                 strs.Add(tempstr);
23                 find = true;
24                 tempstr = string.Empty;
25                 temp = mI;
26                 break;
27             }
28
29              }
30             //没找到可能就是空啊
31             if (!find)
32             {
33                 Console.WriteLine("None");
34             }
35             else
36             {
37                 //进行了循环遍历打印最终的结果
38                 foreach (var temps in strs)
39                 {
40                     Console.Write(mI.ToString() +
41                         "=");
42                     Console.Write(temps.Replace(",", "+"));
43                     Console.WriteLine();
44                 }
45             }
46             Console.ReadKey();

这种循环的算法固然很好，但是出现漏值的情况。譬如说

15=1+2+3+4+5

15=4+5+6

15=&+7

这里遗漏了15=1+2+3+4+5，我这个算法这么做固然很好啊，因为他的时间复杂度是O(n).但，我要明白这么一点的话他是以此循环，同样的数字不可能遍历2次。因此解决这个方案。必须需要两层循环。因此，必须进行方法的重构。伪代码如下：

相应源代码如下：

1 Console.WriteLine("请你输入一个数字");
2             int mI = int.Parse(Console.ReadLine());
3             int temp = mI;
4             bool find = false;
5             int temp1 = 0;
6             List<string> strs = new List<string>();
7
8
9             string tempstr = string.Empty;
10
11             for (int i = (mI - 1) / 2 + 1; i >= 1; i--)
12             {
13                 temp = temp - i;
14                 temp1 = temp;
15                 tempstr = tempstr + i.ToString() + ",";
16
17                 for (int j = i - 1; j >= 1; j--)
18                 {
19                     temp = temp - j;
20                     tempstr = tempstr + j.ToString() + ",";
21                     //小于0
22                     if (temp == 0)
23                     {
24                         tempstr = tempstr.Remove(tempstr.Length - 1);
25                         strs.Add(tempstr);
26                         find = true;
27                         tempstr = string.Empty;
28                         temp = mI;
29                         break;
30                     }
31
32                     if (temp < 0)
33                     {
34                         tempstr = string.Empty;
35                         temp = mI;
36                         break;
37                     }
38                     //j==1 清空循环
39                     if (j == 1)
40                     {
41                         tempstr = string.Empty;
42                         temp = mI;
43                     }
44
45                 }
46
47
48
49             }
50
51             if (!find)
52             {
53                 Console.WriteLine("None");
54             }
55             else
56             {
57                 foreach (var temps in strs)
58                 {
59                     Console.Write(mI.ToString() +
60                         "=");
61                     Console.Write(temps.Replace(",", "+"));
62                     Console.WriteLine();
63                 }
64             }
65             Console.ReadKey();