算法设计基础.doc

算法设计基础

本章讨论如何评价一个算法，常见的基本的算法设计方法。算法在C语言程序设计中具有如此重要的位置，以至于我们不得不用单独一章来讨论算法。仅仅掌握C语言程序设计语法规则并不能保证写出一个好的程序。好与坏的标准在计算机科学中有特定的含义，它是程序的执行过程花费的时间代价和空间代价的少与多的度量。好的算法给我们带来经济上的好处，可以使得我们设计出更优秀的操作系统，提高计算机的运行效率；或者使得我们可以提高机密数据的安全性，不被别人窃取；或者可以提供给我们更好的影音效果，让我们能享受生活的乐趣；或者使得我们在有哪些信誉好的足球投注网站引擎上更快的有哪些信誉好的足球投注网站到需要的数据。好的算法能在有限时间和有限空间条件下得到问题的解，而不好的算法可能终生都得不到解。历史上有许多著名科学家都提出了针对特定问题的著名算法。伟大的智者——DonE.Knuth(1938-)，他是算法和程序设计技术的先驱者。Knuth的经典著作《计算机程序设计艺术》更是被誉为算法教材中“真正”的圣经。BillGates说：“如果能作对书里所有的习题，就直接来微软上班吧！”。首席算法官UdiManber——世界上还有如此奇特的职位？但是对于Amazon乃至Google来说，这一点也不奇怪。UdiManber，这位前Amazon的“首席算法官”，现在是Google负责工程事务的副总裁。Udi还因为他所著《IntroductiontoAlgorithms——ACreativeApproach》而被大家称道。谦逊的长者——EdsgerWybeDijkstra，1930年出生于荷兰阿姆斯特丹，2002年逝世于荷兰纽南。他在祖国荷兰获得数据和物理学学士，理论物理博士学位，2000年退休前一直是美国Texas大学的计算机科学和数学教授。因他发现了图论中的最短路径算法（Dijkstra算法）而闻名于世，1972年因发明ALGOL第二代编程语言而获得图灵奖。运筹学大师——GeorgeDantizig，在大学时代就解决了两个统计学悬而未决的难题。George后来在运筹学建树极高，获得了包括“冯诺伊曼理论奖”在内的诸多奖项。他在《Linearprogrammingandextensions》一书中研究了线性编程模型，为计算机语言的发展做出了不可磨灭的贡献。推动时代前进的人—JamesCooley(1926-)是美国数学家，哥伦比亚大学的数学博士，因为发明快速傅立叶变换(FFT)而著名。FFT的数学意义不光在于使大家明白了傅立叶(Fourier)变换计算起来是多么容易，而且使得数字信号处理技术取得了突破性的进展，对于现在的网络通信，图形图像处理等等领域的发展与前进奠定了基础。FORTRAN之父——JohnBackus。在IBM，Backus的才华得到了施展，发明了人类历史上前所未有第一个高级语言——FORTRAN，对计算机科学计算和程序语言做出了杰出贡献。1977年JohnBackus被授予图灵奖。实践探索先锋——JonBentley。他的著作中，最著名的莫过于涵盖从算法理论到软件工程各种主题的《ProgrammingPearls》(编程珠玑)，这其实是他发表过的论文的合集。在这些文章里，Jon从工程实现的角度出发，为程序员们提供了一个个艰难问题的解决方案，犹如一颗颗闪闪发亮的珍珠。Bentley的珍珠超出了可靠工程学的范畴，利用他的洞察力和创造力为那些恼人的算法问题提供了巧妙解决方案。Pascal之父——NicklausWirth，如果说有一个人因为一句话而著名，那么这个人就是NicklausWirth，这句话就是他提出的著名公式“算法+数据结构=程序”。他创建与实现了Pascal语言——当时世界上最受欢迎的语言之一。算法的讲解者——RobertSedgewick是普林斯顿大学的计算机科学教授。他还是AdobeSystems的一名主管，也曾作为访问学者在XeroxPARC、IDA和INRIA工作。他在斯坦福大学获得博士学位。他的著作包括《AlgorithminC》、《AlgorithminC++》、《AlgorithminJava》等系列书籍，这些都再版多次。计算机领域的爵士——TonyHoare，1934年出生于英国，1959年博士毕业于俄罗斯莫斯科国立大学，获得语言机器翻译专业学士学位。1960年发布了使他闻名于世的快速排序算法（QuickSort），这个算法也是当前世界上使用最广泛的算法之一。中国历史上也有著名算法，如圆周率PI的计算方法。近代诞生的遗传算法对处理相当广泛的大规模问题有突出效果。这些算法都是人类智慧的结晶。要写出好的程序，应该向这些优秀的算法学习，阅读大师的著