一步一步写算法

后一篇:
作者信息: feixiaoxing
作者链接: http://blog.csdn.net/feixiaoxing

算法是计算机的生命。没有算法,就没有软件,计算机也就成了一个冰冷的机器,没有什么实用价值。很多人认为,算法是数学的内容,学起来特别麻烦。我们不能认为这种观点是错误的。但是我们也知道,软件是一种复合的技术,如果一个人只知道算法,但是不能用编程语言很好地实现,那么再优秀的算法也不能发挥作用。一个人只有有了很好的计算机知识和数学知识,才能在算法的学习上不断进步。不管算法多么简单,都要自己亲手实践,只有不断认识错误、不断发现错误,才能不断提高自己的编程能力,不断提高自己的业务水平。

这里取名一步一步写算法的目的主要有两个:第一,保证我们的算法都是大家可以学得会,看的懂的;第二,保证我们的算法是健壮的、可以测试的。所以在编写的过程中,我们的算法开发过程是伴随着测试用例增加的,没有测试用例保证的代码只是一段无序的字符而已,没有什么价值。

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

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

int find(int array[], int length, int value)
{
    int index = 0;
    return index;
}

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

static void test1()
{
    int array[10] = {0};
    assert(FALSE == find(NULL, 10, 10));
    assert(FALSE == find(array, 0, 10));
}

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

int find(int array[], int length, int value)
{
    if(NULL == array || 0 == length)
        return FALSE;

    int index = 0;
    return index;
}

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

int find(int array[], int length, int value)
{
    if(NULL == array || 0 == length)
        return FALSE;

    int index = 0;
    for(; index < length; index++){
        if(value == array[index])
            return index;
    }

    return FALSE;
}

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

static void test2()
{
    int array[10] = {1, 2};
    assert(0 == find(array, 10, 1));
    assert(FALSE == find(array, 10, 10));
}

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

int find(int array[], int length, int value)
{
    if(NULL == array || 0 == length)
        return FALSE;

    int* start = array;
    int* end = array + length;
    while(start < end){
        if(value == *start)
            return ((int)start - (int)array)/(sizeof(int));
        start ++;
    }

    return FALSE;
}

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

template
int find(type array[], int length, type value)
{
    if(NULL == array || 0 == length)
        return FALSE;

    type* start = array;
    type* end = array + length;
    while(start < end){
        if(value == *start)
            return ((int)start - (int)array)/(sizeof(type));
        start ++;
    }

    return FALSE;
}

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

static void test1()
{
    int array[10] = {0};
    assert(FALSE == find(NULL, 10, 10));
    assert(FALSE == find(array, 0, 10));
}

static void test2()
{
    int array[10] = {1, 2};
    assert(0 == find(array, 10, 1));
    assert(FALSE == find(array, 10, 10));
}

所以,下面我们总结一下:

(1)我们的算法需要测试用例的验证

(2)任何的优化都要建立在测试的基础之上

(3)测试和代码的编写要同步进行

(4)算法的成功运行时一步一步进行得,每一步的成功必须确立在原有的成功之上

致谢
内容撰写:http://blog.csdn.net/feixiaoxing

更新日期 更新内容
2015-06-4 一步一步写算法
后一篇: