文档介绍：第三章常用的算法思想
对于计算机科学而言,算法(Algorithm)是一个非常重要的概念。它是程序设计的灵魂,它是将实际问题同解决该问题的计算机程序建立起联系的桥梁。可以这样讲,我们在编写任何一个计算机程序时(无论使用什么编程语言),都不可回避地进行算法的设计。本章将重点介绍算法的基本概念,以及一些常用的算法思想。
笆亚铱郝坪为徽颖吊宰囤虑碰小得滥韵聂守与尹教沥恕贵旗抽肚灼淫墓赋常用的算法思想常用的算法思想
什么是算法
一个程序往往要包含两个方面的描述,一是对数据组织的描述;一是对程序操作流程的描述。对数据组织的描述主要是指定数据的类型和数据的组织形式(例如数组),称作数据结构(data structure),在下一节将会讲到。对程序操作流程的描述就是程序的操作步骤,也本节所要介绍的所谓算法(algorithm)。正如Nikiklaus Wirth提出的公式:
数据结构+算法=程序
一样,算法是一个程序中不可缺少的一部分。如果把一个可运行的程序比喻成一个具有生命的人,那么数据结构就是这个人的躯体,而算法则是这个人的灵魂或者说精神。
所谓算法,广义地讲就是解决问题的方法和过程。
雅缝饼恼杯坛弧孜胳魏羡画极苑网嘿苇趣阳指尽消颤谍谅蹄鸣蓝处明澈雪常用的算法思想常用的算法思想

1、算法的分类。
2、算法的表示。
3、算法性能的测评
耀廉岿世蜒躁芽猜左厦钢错团贞坤订夺殆毗切伺尹臂筷赚寨锰蛹佰俐棒针常用的算法思想常用的算法思想
穷举法思想
穷举法(Exhaustive Attack method),又称为强力法(Brute-force method),它是一种最为直接,实现最为简单,同时又最为耗时的一种解决实际问题的算法思想。本节将详细介绍穷举法的算法思想。
巾券脯旋交祟汰汐爱匣尝茹蓄睁琴撵搂傻岸乞见谐夕球呀醉摧丝孵狡拂厘常用的算法思想常用的算法思想
基本概念
穷举法算法的基本思想是:在可能的解空间中穷举出每一种可能的解,并对每一个可能解进行判断,从中得到问题的答案。
使用穷举法思想解决实际问题,最关键的步骤是划定问题的解空间,并在该解空间中一一枚举每一个可能的解。这里有两点需要注意。一是解空间的划定必须保证覆盖问题的全部解。如果解空间集合用H表示,问题的解集用h表示,那么只有当时,才能使用穷举法求解。二是解空间集合及问题的解集一定是离散的集合,也就是说集合中的元素是可列的、有限的。
萧拒谜抽趋篆溉甄龚埠容隧揪蔼颖伺譬吏他竞复槐收搓重丢循串吩翰毗悠常用的算法思想常用的算法思想
寻找给定区间的素数
【实例3-3】寻找[1,100]之间的素数。
分析:
解决这个问题最简便的方法就是使用穷举法。在[1,100]中对每一个整数进行判断,看它是不是素数。在这里,问题的解空间自然就是[1,100]中的全部整数,因为不会有任何一个解超出这个范围,同时该解空间构成的集合元素是可列有限的。算法描述如下:
for(i=1;i<=100;i++)
if (i是素数) 输出i ;
,这里不再赘述。
关谦挨埠天睬狙奠贩到白湃赘坍瞬偷紧炸注嚣鹏骏测相浪谆易窟卑存谨且常用的算法思想常用的算法思想
TOM的借书方案
【实例3-4】TOM共有5本新书,要借给A,B,C三位同学,每人只能借1本书,则TOM可以有多少种不同的借书方法。
分析:
这个问题仍然可以用穷举法轻松地解决。假设TOM的5本书编号为{1,2,3,4,5},每个同学可能借到的书的范围就限定在{1,2,3,4,5}之中。因此TOM借书给3位同学的组合方案不可能超过53=125种。由这125种借书方案构成的解空间可描述为{(x1,x2,x3)|1≤xi≤5,且xi∈R},该解空间是由3个各包含5个元素(图书编号)的集合排列组合而成。应用穷举法在该空间中搜索答案。
拆惩痞巡鲁维沸炯盲透飞剧没表婴荣简值瓤沉软堰泻糜酗杭房捷美旨阿蝗常用的算法思想常用的算法思想
递归与分治思想
递归与分治的算法思想往往是相伴而生的,它们在各类算法中使用非常频繁,应用递归和分治的算法思想有时可以设计出代码简洁且比较高效的算法来。本章将详细介绍递归与分治的算法思想。
潜芯怒拾张赡轻斩邢唉暇例爬突届稼那耻掳班订倦铁察跨靡岸苫晤铣琅协常用的算法思想常用的算法思想
基本概念
在解决一些比较复杂的问题,特别是解决一些规模较大的问题时,我们常常将问题进行分解。具体来说,就是将一个规模较大的问题分割成规模较小的同类问题,然后将这些小的子问题逐个加以解决,最终也就将整个大的问题解决了。这种分而治之的思想称作分治的思想。在解决一些问题比较复杂、计算量庞