一步一步寫算法（之開篇）

 算法是計算機的生命。沒有算法，就沒有軟體，計算機也就成了一個冰冷的機器，沒有什麼實用價值。很多人認為，算法是數學的内容，學起來特别麻煩。我們不能認為這種觀點是錯誤的。但是我們也知道，軟體是一種複合的技術，如果一個人隻知道算法，但是不能用程式設計語言很好地實作，那麼再優秀的算法也不能發揮作用。一個人隻有有了很好的計算機知識和數學知識，才能在算法的學習上不斷進步。不管算法都麼簡單，都要自己親手實踐，隻有不斷認識錯誤、不斷發現錯誤，才能不斷提高自己的程式設計能力，不斷提高自己的業務水準。

    這裡取名一步一步寫算法的目的主要有兩個：第一，保證我們的算法都是大家可以學得會，看的懂的；第二，保證我們的算法是健壯的、可以測試的。是以在編寫的過程中，我們的算法開發過程是伴随着測試用例增加的，沒有測試用例保證的代碼隻是一段無序的字元而已，沒有什麼價值。

    其實任何算法都有自己的應用環境和應用場景，沒有算法可以适用于所有的場景。這一點希望大家明白。同時，我們也要清楚複雜的算法都是由普通的算法構成的，沒有普通的算法就沒有複雜的算法可言，是以複雜變簡單，由大化小，這就是算法分治遞歸的基本思想。

    我們可以下面一個數組查找的函數說起。一句一句寫起，首先我們開始從最簡單的函數構造開始：

[cpp] view plaincopy

01.int find(int array[], int length, int value) 

02.{ 

03.    int index = 0; 

04.    return index; 

05.} 

    這裡看到，查找函數隻是一個普通的函數，那麼首先需要判斷的就是參數的合法性：

[cpp] view plaincopy

01.static void test1() 

02.{ 

03.    int array[10] = {0}; 

04.    assert(FALSE == find(NULL, 10, 10)); 

05.    assert(FALSE == find(array, 0, 10)); 

06.} 

    這裡可以看到，我們沒有判斷參數的合法性，那麼原來的查找函數應該怎麼修改呢？

[cpp] view plaincopy

01.int find(int array[], int length, int value) 

02.{ 

03.    if(NULL == array || 0 == length) 

04.        return FALSE; 

05. 

06.    int index = 0; 

07.    return index; 

08.} 

    看到上面的代碼，說明我們的已經對入口參數進行判斷了。那麼下面就要開始寫代碼了。

[cpp] view plaincopy

01.int find(int array[], int length, int value) 

02.{ 

03.    if(NULL == array || 0 == length) 

04.        return FALSE; 

05. 

06.    int index = 0; 

07.    for(; index < length; index++){ 

08.        if(value == array[index]) 

09.            return index; 

10.    } 

11. 

12.    return FALSE; 

13.} 

    上面的代碼已經接近完整了，那麼測試用例又該怎麼編寫呢？

[cpp] view plaincopy

01.static void test2() 

02.{ 

03.    int array[10] = {1, 2}; 

04.    assert(0 == find(array, 10, 1)); 

05.    assert(FALSE == find(array, 10, 10)); 

06.} 

    運作完所有的測試用例後，我們看看對原來的代碼有沒有什麼可以優化的地方。其實，我們可以把數組轉變成指針。

[cpp] view plaincopy

01.int find(int array[], int length, int value) 

02.{ 

03.    if(NULL == array || 0 == length) 

04.        return FALSE; 

05. 

06.    int* start = array; 

07.    int* end = array + length; 

08.    while(start < end){ 

09.        if(value == *start) 

10.            return ((int)start - (int)array)/(sizeof(int)); 

11.        start ++; 

12.    } 

13. 

14.    return FALSE; 

15.} 

    如果上面的代碼參數必須是通用的資料類型呢？

[cpp] view plaincopy

01.template<typename type> 

02.int find(type array[], int length, type value) 

03.{ 

04.    if(NULL == array || 0 == length) 

05.        return FALSE; 

06. 

07.    type* start = array; 

08.    type* end = array + length; 

09.    while(start < end){ 

10.        if(value == *start) 

11.            return ((int)start - (int)array)/(sizeof(type)); 

12.        start ++; 

13.    } 

14. 

15.    return FALSE; 

16.} 

    此時，測試用例是不是也需要重新修改呢？

[cpp] view plaincopy

01.static void test1() 

02.{ 

03.    int array[10] = {0}; 

04.    assert(FALSE == find<int>(NULL, 10, 10)); 

05.    assert(FALSE == find<int>(array, 0, 10)); 

06.} 

07. 

08.static void test2() 

09.{ 

10.    int array[10] = {1, 2}; 

11.    assert(0 == find<int>(array, 10, 1)); 

12.    assert(FALSE == find<int>(array, 10, 10)); 

13.} 

是以，下面我們總結一下：

    （1）我們的算法需要測試用例的驗證

    （2）任何的優化都要建立在測試的基礎之上

    （3）測試和代碼的編寫要同步進行

    （4）算法的成功運作時一步一步進行得，每一步的成功必須确立在原有的成功之上