c++实例研究

从0开始

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  104 随笔 :: 0 文章 :: 20 评论 :: 0 Trackbacks
算法,包含的问题很多。解决一个算法的过程,是一个工程的过程。不仅需要从数学角度,获得抽象,获得问题可解性,以及复杂度的相关估计,还需要用语言,库,系统调用将其实现,这就需要一些积累的经验。两者共同决定着一个算法问题的解决是否有效,是否优雅,是否可维护,是否易扩展。下面就从两个方面说说算法问题的解决。也为自己整理一下思路。
第0是仔细看题,常常几个字的差别,题目的意思是完全不一样的,要知道,NP问题其实和多项式问题,就差了几个字哦。这点我深有体会,经常看了结题报告才发现原来题目没有想象中的那么难。囧。审题可以从以下几个方面入手:1 数据范围 2 给的case 手动理解答案
第一是数学角度。数学抽象是所有问题的第一步,从一个实际的模型,获得一个解的模型,其实属于数学建模的范畴。好在一般算法题都是从抽象问题转化而来,给出的条件常常很特殊,相信有一定做题量以后就能很快的进行建模。建模,首先必须有个初步的模型,才能在脑海中建立起适合问题的模型。这就需要算法经验。在这方面,将基础题一种一种过一遍是很好的方法。这使得你的脑海中起码知道一些基本的模型。举例来说,求最优解问题时候,就会自觉的想到最优解的几种模型,是贪心的,还是动态规划的,或是NP难的,在看到配对,关系的问题时,想到是否可以用有向图,无向图,树形图来表示关系,然后用并查集,最短路,最大流等经典算法。当求问题可能解时,是否用回溯模型,或者用递归。抽象是开始一个问题时,是我最头疼的一步,因为本身没有定法。我做题往往将问题抽象不够,最后得到的算法又臭又长。这也是我喜欢模拟题的原因,单从建模方面,很简单,只要足够细心,一定能得到结果。 判断一个抽象优劣的标准就是问题能否变得简单。这里的简单分为两个方面:能并入现有问题的,能将问题简单化的。第一点,算法常常是某个或某几个问题的特例,套用前人的算法,证明都省了,而后者就需要自己分析问题了。这和解一道数学题的过程是一样的,从已知推到未知,从复杂化简。思路当然有几个方面,常用的有:1 改变条件:去掉限制条件,或者加上特例条件,这样常常可以获得解的直观印象, 也可以区分一些贪心和dp问题。2 分治 这是通用的思路,一个问题可以分为几个子问题,子问题是否也是主问题的一种,子问题的最优解是否是主问题最优解。 完成以后,就可以开始考虑复杂度了。通常是先给出一种可解方案,再改进复杂度。
第二就是工程问题了。这直接决定你的代码是否清晰,可读,易懂。现在算法往往采用全局变量的声明方法避免过多的参数传递,变量也简短概括,颇有数学表达式的气势。况且有程序设计实践中提到的,在局部作用域名字应该简短的条款,那就大胆的采用最简单的变量吧。工程中最重要的其实是数据结构。开始做bfs经常用到队列,而数据结构中的队列实现不然用链表,不然就搞的复杂无比,这导致了很多需要用队列的题目我拿到以后很是害怕。最后,发现在算法中,基本没人用new delete这样的操作符,取而代之的是超大数组来实现链表。大家的理念是,用完就用下一个。这确实让很多问题简单化了。但是,随着问题越来越复杂,需要的数据结构往往也随着复杂了。看看算法导论里面那几章,从二叉索引树,到红黑树,到B树,二项堆,斐波那契堆,这几章到现在我还没理解。这些数据结构都优化了数据操作,但是实现复杂,这时候就需要库出现了。algorithm头文件的出现,让coder少写了不少经典算法,stl也将数据结构的春风吹到了算法圈。而boost库,则是在实用工程中可以看做stl一样重要的库。有了库的帮助,就算你不怎么会数据结构,也能写出很高效的程序来。
不管怎么说,实践还是需要实践。最简单的方法,就是你的纸和笔。没有IDE智能提醒,你能写出多离谱的程序来。一个好的程序员,必须聪明,写高效,整齐的代码。这几个字,需要你用时间去磨练。
Good Luck!
posted on 2010-10-31 20:53 elprup 阅读(438) 评论(0)  编辑 收藏 引用 所属分类: 杂谈

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理