专栏名称: 电子工程专辑
电子工程专辑是中国创建较早的电子工程类网站,是《电子工程专辑》杂志的有力补充。专注为工程师提供最新技术及实用方法的专业平台。包括:16个热门技术栏目在内的,新品信息和新闻报道、专题报道以及厂商应用报告、行业重要新闻的信息速递。
目录
相关文章推荐
超级数学建模  ·  不到4折!KAYANO ... ·  10 小时前  
超级数学建模  ·  埃里森放话“48小时AI定制癌症疫苗”:是颠 ... ·  昨天  
超级数学建模  ·  男人的内裤,怎么这样了? ·  昨天  
超级数学建模  ·  限时领 | 国家地理Look ... ·  5 天前  
巴比特资讯  ·  第一批DeepSeek开发者,已经开始逃离了 ·  3 天前  
51好读  ›  专栏  ›  电子工程专辑

所谓的算法,有时候几十行代码就能搞定!

电子工程专辑  · 公众号  ·  · 2017-08-02 11:59

正文

很多人认为,算法是数学的内容,学起来特别麻烦。我们不能认为这种观点是错误的。但是我们也知道,软件是一种复合的技术,如果一个人只知道算法,但是不能用编程语言很好地实现,那么再优秀的算法也不能发挥作用。

有一次,一个人问我:“你写的都是小儿科的东西,几十行代码就能搞定,能不能整一点高深的算法?”

我反问他什么是他所理解的高深的算法,他答复说:“像遗传算法、蚁群算法之类的。”于是我给了他一个遗传算法求解0-1背包问题的例子,并告诉他,这也就是几十行代码的算法,怎么理解成是高深的算法?他刚开始不承认这是遗传算法,直到我给了他Denis Cormier公开在北卡罗来纳州立大学服务器上的遗传算法的源代码后,他才相信他一直认为深不可测的遗传算法的原理原来是这么简单。

还有一个人直言“用三个水桶等分8升水”之类的问题根本就称不上算法,他认为像“阿法狗”那样的人工智能才算是算法。我告诉他计算机下棋的基本理论就是博弈树,或者再加一个专家系统。但是他认为博弈树也是很高深的算法,于是我给了他一个井字棋游戏,并告诉他,这就是博弈树搜索算法,非常智能,你绝对战胜不了它(因为井字棋游戏很简单,这个算法会把所有的状态都搜索完)。我相信他一定很震惊,因为这个算法也不超过100行代码。

对于上面提到的例子,我觉得主要原因在于大家对算法的理解有差异,很多人对算法的理解太片面,很多人觉得只有名字里包含“XX算法”之类的东西才是算法。而我认为算法的本质是解决问题,只要是能解决问题的代码就是算法。

一个人只有有了很好的计算机知识和数学知识,才能在算法的学习上不断进步。不管算法都么简单,都要自己亲手实践,只有不断认识错误、不断发现错误,才能不断提高自己的编程能力,不断提高自己的业务水平。

其实任何算法都有自己的应用环境和应用场景,没有算法可以适用于所有的场景。这一点希望大家明白。同时,我们也要清楚复杂的算法都是由普通的算法构成的,没有普通的算法就没有复杂的算法可言,所以复杂变简单,由大化小,这就是算法分治递归的基本思想。

我们可以下面一个数组查找的函数说起。一句一句讲起,首先我们开始从最简单的函数构造开始:



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

2. {

3.     int index = 0;

4.     return index;

5. }




这里看到,查找函数只是一个普通的函数,那么首先需要判断的就是参数的合法性:

1. static void test1()

2. {

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

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

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

6. }

这里可以看到,我们没有判断参数的合法性,那么原来的查找函数应该怎么修改呢?

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

2. {

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

4.         return FALSE;

5.

6.     int index = 0;

7.     return index;

8. }

看到上面的代码,说明我们的已经对入口参数进行判断了。那么下面就要开始写代码了。

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

2. {

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

4.         return FALSE;

5.

6.     int index = 0;

7.     for(; index

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

9.             return index;

10.     }

11.

12.     return FALSE;

13. }

上面的代码已经接近完整了,那么测试用例又该怎么编写呢?

1. static void test2()

2. {

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

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

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

6. }

运行完所有的测试用例后,我们看看对原来的代码有没有什么可以优化的地方。其实,我们可以把数组转变成指针。

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

2. {

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

4.         return FALSE;

5.

6.     int* start = array;

7.     int* end = array + length;

8.     while(start

9.         if(value == *start)

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

11.         start ++;

12.     }

13.

14.     return FALSE;

15. }

如果上面的代码参数必须是通用的数据类型呢?

1. template

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

3. {

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

5.         return FALSE;

6.

7.     type* start = array;

8.     type* end = array + length;

9.     while(start

10.         if(value == *start)

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

12.         start ++;

13.     }

14.

15.     return FALSE;

16. }

此时,测试用例是不是也需要重新修改呢?

1. static void test1()







请到「今天看啥」查看全文