`

一步一步写算法(开篇)

 
阅读更多

http://blog.csdn.net/feixiaoxing/article/details/6835423

 

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

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

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

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

 

  1. int find(int array[], int length, int value)  
  2. {  
  3.     int index = 0;  
  4.     return index;  
  5. }  
int find(int array[], int length, int value)
{
	int index = 0;
	return index;
}

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

 

 

  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. }  
static void test1()
{
	int array[10] = {0};
	assert(FALSE == find(NULL, 10, 10));
	assert(FALSE == find(array, 0, 10));
}

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

 

 

  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. }  
int find(int array[], int length, int value)
{
	if(NULL == array || 0 == length)
		return FALSE;

	int index = 0;
	return index;
}

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

 

 

  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 < length; index++){  
  8.         if(value == array[index])  
  9.             return index;  
  10.     }  
  11.   
  12.     return FALSE;  
  13. }  
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;
}

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

 

 

  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. }  
static void test2()
{
	int array[10] = {1, 2};
	assert(0 == find(array, 10, 1));
	assert(FALSE == find(array, 10, 10));
}

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

 

 

  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 < end){  
  9.         if(value == *start)  
  10.             return ((int)start - (int)array)/(sizeof(int));  
  11.         start ++;  
  12.     }  
  13.   
  14.     return FALSE;  
  15. }  
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;
}

 

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

 

  1. template<typename type>  
  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 < end){  
  10.         if(value == *start)  
  11.             return ((int)start - (int)array)/(sizeof(type));  
  12.         start ++;  
  13.     }  
  14.   
  15.     return FALSE;  
  16. }  
template<typename type>
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;
}

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

 

 

  1. static void test1()  
  2. {  
  3.     int array[10] = {0};  
  4.     assert(FALSE == find<int>(NULL, 10, 10));  
  5.     assert(FALSE == find<int>(array, 0, 10));  
  6. }  
  7.   
  8. static void test2()  
  9. {  
  10.     int array[10] = {1, 2};  
  11.     assert(0 == find<int>(array, 10, 1));  
  12.     assert(FALSE == find<int>(array, 10, 10));  
  13. }  
static void test1()
{
	int array[10] = {0};
	assert(FALSE == find<int>(NULL, 10, 10));
	assert(FALSE == find<int>(array, 0, 10));
}

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


 

 


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

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

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

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

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

分享到:
评论

相关推荐

    算法设计第一章习题解答

    第一章作为开篇,通常会介绍算法设计的基础概念和基础方法,如分治策略、动态规划、贪心法等。 在这一章的课后习题中,我们可以期待涵盖以下几个方面的内容: 1. **基础算法思想**:习题可能会涉及如何运用基础的...

    王晓茹课件.zip北邮王晓茹老师的算法中文课件

    接着,“Algotiyhmsch04-Greedy programming.pdf”可能讲解了贪心算法,这种算法通常在每一步选择局部最优解,希望全局也能达到最优。常见的贪心算法应用有霍夫曼编码和Prim最小生成树算法。 “Algotiyhmsch05-回溯...

    《算法导论》

    例如,"lecture01.pdf"可能是课程的开篇,讲解了算法的基础概念和基础知识,而"lecture17.pdf"则可能是更高级的主题,如动态规划或者图算法。每个文件都可能涵盖了一个或多个算法主题,如排序、搜索、图论、递归、...

    哈工大算法设计课件

    引言.pdf 则可能是课程的开篇,它可能会介绍算法设计的重要性,简述历史上著名的算法和它们对科技进步的影响,比如排序算法(快速排序、归并排序)、图论中的最短路径算法(Dijkstra算法、Floyd-Warshall算法)和...

    算法设计与分析基础.pptx

    本书的开篇第一章首先介绍了算法的基本概念和定义,以及算法的复杂度和分析方法。这一章还详细介绍了算法的分类和应用领域,为读者后续的学习提供了基础。 第二章主要介绍了算法设计的基本原则和方法。这一章首先...

    amazon算法5星图书,比算法导论的评价还高

    - **第5章:贪心算法**:本章介绍了贪心算法这一类算法设计策略,它通常在每一步选择局部最优解,希望以此达到全局最优。 - **最小生成树**:通过Prim或Kruskal算法构造最小生成树。 - **霍夫曼编码**:一种数据...

    算法导论 - 第二版 - 中文版

    本章作为开篇,主要介绍了算法的基本概念,包括算法的定义、表示方法、性能度量以及算法设计与分析的重要性。同时,它还涉及到了问题求解策略,如分治法、动态规划和回溯法,为后续章节的学习奠定了基础。 **第二章...

    C语言算法和基本程序设计PPT学习教案.pptx

    开篇伊始,教案便对算法的基本概念做了精辟的阐释。它强调了“数据结构 + 算法 = 程序”这一核心公式。在这一框架下,数据是编程所要处理的原材料,可以是静态的数据集合,也可以是动态变化的数据流。数据结构则定义...

    算法导论详细答案(英文版)

    这一章是整本书的开篇,主要介绍了一些基本概念,包括算法的定义、如何表示算法以及算法的基本结构。此外,它还介绍了算法分析的重要性,包括时间复杂度和空间复杂度的概念,这是后续章节深入讨论的基础。通过本章的...

    大连理工大学软件系使用关于计算机算法系统的课件(全)

    课件的开篇,总是从算法的基本定义入手,解析算法的四项特性:可行性、确定性、有限性和输入输出。这一章对于初学者尤为重要,因为它为后续内容的学习打下了坚实的基础。在这个环节,学生们不仅能够了解算法的理论...

    Pascal算法背包问题析PPT教案.pptx

    它的核心思想是在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是最好或最优的算法。在背包问题中,贪心算法通常通过计算每个物品单位体积的价值,并按照从大到小的顺序选取物品,直至背包的...

    基于深度强化学习算法的“电网脑”及其示范工程应用.pdf

    文章开篇即指出当前电网面临的新挑战,由于可再生能源、电力电子设备的广泛使用以及高功率交直流混联电网的复杂性增加,电网的动态性、随机性和不确定性显著增强,这给电力系统的安全稳定运行带来了挑战。...

    jtmzyhjs_30609_matlab优化算法_matlab优化_

    随后,作者详细讲解了MATLAB优化工具箱的使用技巧,从设置初始值、选择优化算法到处理约束条件和调用优化函数,每一步都结合实例进行说明,让读者能够在实践中快速上手。 在深入到具体的优化方法时,作者并没有停留...

    数据结构与算法课内实验实验报告.doc

    首先,我们以实验一为开篇,探讨了“文件读取与数据处理”的过程。实验的初衷是为了分析鼠标操作者的使用效率,这一过程中涉及到了数据的采集、存储、处理等多个环节。数据的采集依赖于文本文件的读取,而数据的存储...

    老喻的人生算法课xs.docx

    发刊词作为整个课程的开篇,其核心目的在于为读者描绘出一个清晰的学习路径和框架。老喻在这里强调了一个重要概念——“人生算法”,即通过一系列经过验证的有效方法和技术来指导个人行为和决策制定。这一理念认为每...

    线性表的设计和实现_本科毕业论文模板、范本.doc

    通过动态演示,算法的每一步操作都能被清晰展示,这对于发现和改正程序中的错误,以及优化算法性能具有极大的帮助。 “结果和讨论”章节将对数据结构算法设计和实现的结果进行讨论和分析。通过对算法运行效率的评估...

    高效测试用例组织算法pairwise之Python实现方法

    #### 开篇 在软件测试领域,当面对多个参数且每个参数有多项取值时,如何有效地组织测试用例成为了一个重要的问题。传统的方法之一是**正交分析法**,这种方法通过穷举各个参数的所有可能组合来生成测试用例,虽然...

Global site tag (gtag.js) - Google Analytics