一道百度之星編程大賽算法題的隨筆聯(lián)想

編程工具(ATOM)v1.41.0免費版

• 類型：編程工具大�。�180.9M語言：中文 評分：10.0
• 標(biāo)簽：

立即下載

百度之星，是全球最大的中文搜索引擎，百度公司面向中國高校學(xué)生和編程愛好者所舉辦的高水平的程序設(shè)計大賽。他所考試的題目，全部都是算法的題目。

鄙人雖然是一個.net程序員，在工作之余，喜愛算法。 我覺得這個題目有點意思，故而分享給大家，我想到兩種方法，提供大家，希望對大家起了一個開闊思路的作用。

首先，看題目是那樣的：

請編寫程序，根據(jù)輸入的任何一個正整數(shù)，找出符合這種要求的所有連續(xù)正整數(shù)序列。

輸入數(shù)據(jù)：一個正整數(shù)，以命令行參數(shù)的形式提供給程序。

輸出數(shù)據(jù)：在標(biāo)準(zhǔn)輸出上打印出符合題目描述的全部正整數(shù)序列，每行一個序列，每個序列都從該序列的最小正整數(shù)開始、以從小到大的順序打印。如果結(jié)果有多個序列，按各序列的最小正整數(shù)的大小從小到大打印各序列。此外，序列不允許重復(fù)，序列內(nèi)的整數(shù)用一個空格分隔。如果沒有符合要求的序列，輸出“NONE”。

例如，對于15，其輸d出結(jié)果是：
1 2 3 4 5
4 5 6
7 8

對于16，其輸出結(jié)果是：
NONE

我這里提供2種算法的解法，起一個拋磚引玉的作用

方法一：可以從后往前的計算，由大到小的計算。這種計算模式有幾個思考的步驟。

①由于使 計算嗎，我可以考慮從輸入的數(shù)字的一半（奇數(shù)使其中間數(shù)）開始遍歷。于是我就有這樣一種算法。相應(yīng)偽代碼如圖所示：

相應(yīng)的源代碼如下：

1        Console.WriteLine("請你輸入一個數(shù)字");
2             int mI = int.Parse(Console.ReadLine());
3             int temp = mI;
4            //是否能夠拆成n個連續(xù)的數(shù)字的表計量
5             bool find = false;
6             int temp1 = 0;
7             //記錄最終的結(jié)果
8             List<string> strs = new List<string>();                                          
9                //憑借成最終的字符串
10              string tempstr = string.Empty;
11              //進行循環(huán)拆解
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                    //等于了有進一步做數(shù)據(jù)重置的操作
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                 //進行了循環(huán)遍歷打印最終的結(jié)果
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();

這種循環(huán)的算法固然很好，但是出現(xiàn)漏值的情況。譬如說

15=1+2+3+4+5

 15=4+5+6

  15=&+7

這里遺漏了15=1+2+3+4+5，我這個算法這么做固然很好啊，因為他的時間復(fù)雜度是O(n).但，我要明白這么一點的話他是以此循環(huán)，同樣的數(shù)字不可能遍歷2次。因此解決這個方案。必須需要兩層循環(huán)。因此，必須進行方法的重構(gòu)。偽代碼如下：

相應(yīng)源代碼如下：

1 Console.WriteLine("請你輸入一個數(shù)字");
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  清空循環(huán)
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();

運行效果如下所示：

這道題有效的考察了循環(huán)的知識及簡單算法的題目，對初學(xué)者學(xué)習(xí)算法很有好處。