DBSCAN
基于DBSCAN聚类算法的研究综述
学号：12013120116 李余芳
摘要
随着数据挖掘研究领域技术的发展，DBSCAN算法作为数据挖掘主要方法之一的聚类算法，在许多领域得到广泛应用，也越来越受到人们的关注。虽然传统的DBSCAN算法有自己的局限性，但是目前改进的DBSCAN算法已有很多，在生活、生产的不少领域得到了广泛的应用。
关键词：DBSCAN算法密度聚类簇DTBC算法
Abstract
With the development of data mining technology, DBSCAN algorithm is one of the main methods of data mining in clustering algorithm, it has been widely applied in many fields, people are becoming to pay more and more attention to it. Although the traditional DBSCAN algorithm have its limitations, but the existing DBSCAN algorithm has improved a lot, it has been widely used in many areas of our life and production.
Keywords: DBSCAN algorithm density cluster DTBC algorithm
一、引言
数据挖掘( Data Mining) , 也称知识发现( KDD)，是从数据库中便捷地抽取出以前未知的、隐含的、有用的信息，所挖掘出来的知识可应用于信息管理、决策支持、过程控制和其它许多应用。随着数据挖掘研究领域技术的发展，作为数据挖掘主要方法之一的聚类算法，在许多领域得到广泛应用，也越来越受到人们的关注。近年来已经出现了很多的DBSCAN改进算法，比较著名的是OPTICS算法。周水庚等人[1]提出了基于数据分区的PDBSCAN算法，PDBSCAN算法有效解决了密度不均匀问题，但是当类之间存在包含和交叉关系的时候，比如互相缠绕的螺旋状类和互相包含的环状类时，PDBSCAN方法难以见效。孙凌燕等人[2]
基于相对密度的快速聚类算法，不仅解决了传统的基于密度聚类算法所存在的高密度聚类结果被包含在相连的低密度聚类结果中的问题，同时减少了区域查询的次数，从而减少了聚类时间和I/ O 开销。由于DBSCAN算法使用了全局性的参数Eps，因此当各个类的密度不均匀，或者类间的距离相差很大时，聚类的质量较差。文献[3]提出了一种密度标记的聚类算法DTBC，DTBC算法对所输入的参数不敏感，比较适合处理密度不均匀的聚类问题。文献中[4]算法根据基于网格与基于密度的聚类算法间的等效规则计算各个密度层次的密度阈值，解决了DBSCAN算法参数选取困难和难以发现密度相差较大的簇的问题。文献中[5, 6]提出了“分而治之”和高效的并行方法改进DBSCAN算法，使聚类效果明显改善。
二、传统的DBSCAN算法
2.1 DBSCAN的原理[7]
DBSCAN是聚类分析中一种简单的、基于密度的聚类算法。DBSCAN 算法利用类的高密度连通性，快速发现任意形状的类。其基本思想是：对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目。DBSCAN使用阈值和MinPts来控制簇的生成, 先从数据库对象集D中找到任意一对象P，并查找D中关于Eps和MinPts的从P密度可达的所有对象( 其中Eps为半径, MinPts为最小对象数)。如果P是核心对象，也就是说。半径为Eps的P的领域中包含的对象不少于MinPts，则根据算法，可以找到一个关于参数Eps和MinPts的类。如果P 是一个边界点，则半径为Eps的P领域包含的对象数小于MinPts即没有对象从P 密度可达，P被暂时标注为噪声点。然后，DBSCAN 反复地寻找从这些核心对象直接密度可达的对象并将其加入到该簇，直到没有新的点可以被添加，该过程结束。
DBSCAN算法：
任意两个足够靠近( 相互之间的距离在E之内)的核心点放在同一个簇中，任何与核心点足够靠近的边界点也放到与核心点相同的簇中，噪声点被丢弃。
( 1) 将所有点标记为核心点、边界点或噪声点；
( 2) 删除噪声点；
( 3) 为距离在E之内的所有核心点之间赋予一条边；
( 4) 每组连通的核心点形成一个簇；
( 5) 将每个边界点指派到一个与之关联的核心点的簇中。
2.2 DBSCAN算法的时间复杂度和空间复杂度分析
DBSCAN的基本时间复杂度是O ( m 找出E邻域中的点所需要的时间)，其中m 是点的个数。在最坏情况，时间复杂度是O ( )。然而，在低维空间，有一些数据结构，如kd 树，使得可以有效地检索特定点给定距离内的所有点，时间复杂度可以降低到O( m log m) . 即便对于高维数据，DBSCAN的空间复杂度也是O ( m )，因为对每个点，它只需要维持少量数据，即簇标号和每个点是核心点、边界点还是噪声点的标识。
2.3 DBSCAN算法的参数选择
DBSCAN算法的关键是参数E和MinPts的确定，主要基于观察点到它的k 个最邻近点的距离( k -距离) 的特性。对于属于某个簇的点，如果k 不大于簇的大小，则k - 距离将很小。需注意：尽管k -距离因簇密度和点的随机分布不同会有一些变化，只要簇密度的差异不极端，在平均情况下k - 距离的变化不会太大。然而，对于不在簇中的点( 如噪声点)，k - 距离将相对较大，因此，如果对于某个k值，计算所有点的k - 距离，并递增排序，然后绘制排序后的值，则会看到k- 距离的急剧变化。对应于合适的Eps值如果选取该距离为Eps参数，取k值为MinPts 参数，则k - 距离小于E的点将被标记为核心点，而其他点将被标记为噪声或者边界点。
2.4 DBSCAN算法存在的问题
因为DBSCAN使用簇的基于密度的定义，因此它是相对抗噪声的，并且能够处理任意形状和大小的簇。这样，DBSCAN可以发现使用K均值不能发现的许多簇。然而，当簇的密度变化太大时，DBSCAN就会有麻烦。对于高维数据，它也有问题，因为对于这样的数据，密度定义更困难。最后，当近邻计算需要计算所有的点对近邻度时，DBSCAN可能是开销很大的。
三、目前改进的DBSCAN算法
针对传统DBSCAN算法的一些缺点与不足，许多学者已经研究了有很多种改进的DBSCAN算法：快速聚类的算法、基于相对密度的聚类算法、基于相对密度的快速聚类算法和基于密度标记的聚类DTBC算法等等，使得聚类的效果
比传统的DBSCAN算法要更好。
3.1 快速聚类的算法
快速DBSCAN 算法是对DBSCAN 的一个改进，选择核心对象邻域中的部分代表对象，而不是选择所有对象作为种子对象用于类的扩展。这样大大减少了查询次数，加快了聚类速度。选择代表对象其实就是选择一些能够近似地表征所在邻域的形状的对象。在文献[4]中设定对于二维空间数据,选代表对象数为4,选择4 个代表对象,不仅丢失对象少,且聚类速度提高明显。对于三维空间数据,选择6个代表对象，依次类推，在n维空间中，选择2n个代表对象。也就是说，在每一维空间上，选择两个对象作为代表对象用于类的扩展。
其选择代表种子对象的基本思想是：首先选出一个与核心对象最远的对象作为第1个代表对象；随后则选出离所有已被选出的代表对象最远的对象作为下一个代表对象，直到选出所需的全部代表对象为止。
3.2 基于相对密度的聚类算法
基于相对密度的聚类算法首先在数据集D中找到任意一个核心对象p，求出p 的核心集合。得到初始类C：然后由初始类C 开始进行类的扩展直至没有任何对象可以归入该类；重新在D 中寻找任意一个未归类的核心对象q，重复上述过程，直至没有任何对象可以归入任何类算法结束。由初始类C 的扩展过程分两步进行：（1）对p 的核心集合进行扩展，得到类C 的扩展核心集合；（2）根据关于扩展核心集合中核心对象的密度可达这一条件，对类C 进行扩展。基于相对密度的聚类算法在一定程度上解决了参数值过于敏感以及聚类密度不均匀时产生错误结果的问题。但聚类耗时过大的问题还是没有处理，因此文中在相对密度算法中引入快速聚类算法FDBSCAN 的思想。
3.3 基于相对密度的快速聚类算法
基于相对密度的快速聚类算法FRDBC是在基于相对密度的聚类算法基础上，进行类扩展时不选核心领域中的所有点作为种子对象，而是采用快速聚类算法中的部分代表对象作为种子点的方法，这样不仅解决了DBSCAN 算法全局参数的问题，在一定程度上也加快了聚类速度. 具体算法如下：
基于相对密度的快速聚类算法FRDBC 伪码描述：
FRDBC( Set Seto fpoint, int k, real )
BEGIN
REPEAT
po int = GetCorePoint ( Setofpoint, k, ) ;
IF point （）NULL THEN
Cor eset = GetCor eSet ( Setofpoint, point, k, ) ;
Cluster Id = GetCluster I d ( ) ;
C = Get I nitCluster ( Setofpoint, point, CoreSet,
k, cluster ID) ;
ExpandCluster ( Setofpo int, C, Cor eSet, k, ) ;
END IF
UNTIL END
3.4 基于密度标记的聚类DTBC算法
DTBC算法就是依照上面的研究思路进行聚类。DTBC首先根据所有数据点与其k近邻的距离来动态确定针对数据点的子聚类半径Eps，针对每个数据点以:为半径构建子聚类，得到n个子聚类，每个子聚类都包含一定的数据点数俩”)。其次，将n个子聚类中包含的数据点数(MinPts)划分到多个段中，使得在同一段内的MinPts接近，不同段间的MinPts差别大。然后，根据划分结果使用L Method 方法来确定密度标记个数并为每个段加上密度标记，密度标记标用来标识划分到该段中的子聚类的密度信息。密度标记值越大，则被该密度标记所标识的子聚类的密度越大。最后，按照密度标记由大到小的顺序对数据集进行聚类。DTBC算法分为3个阶段:子聚类生成与密度分析阶段，子聚类密度标记确定阶段，聚类生成阶段。
1）第1个阶段:子聚类生成与密度分析阶段
此阶段对每个数据集中的数据点以;为半径构建子聚类，并对得到的所有(n 个)子聚类的密度信息进行分析。
对于具有相同半径Eps的n个子聚类来说，子聚类中包含的MinPts反映了子聚类的密度高低。MinPts越高，该子聚类的密度越高;反之，则密度越低。如果两个子聚类包含的MinPts大致相同，则它们的密度应该基本相同。进一步，所有的MinPts被划分到多个段(区间)中，使得在同一段内的MinPts接近，不同段间的MinPts差别大。也就是说包含的MinPts大致相同的子聚类应该划分到同
一个段内，即密度大致相同的子聚类划分到同一个段中。这些段在后期处理中被唯一的标记(即密度标记)所标识，每个段对应一个密度标记，段内的子聚类就具有相同的密度标记。密度标记用来标识划分到该段中的子聚类的密度信息，这样就可以得到整个数据集的密度信息，接下来就可以根据数据集的密度信息对数据集进行聚类。
2）第2个阶段: 子聚类密度标记确定阶段
此阶段首先确定密度标记数量，然后执行具体的标记操作。在子聚类生成与密度分析阶段，将子聚类包含的MinPts划分到多个段中，这个过程最终产生多个二元组((S），D(S))，其中，S表示段数，D(S)表示段数为S时的总体方差，一个S值对应一种划分方案，因此需要确定一种最合理的划分方案，即确定段数S 的取值。为此，DTBC首先生成针对MinPts划分方案的评价图，利用评价图来评价划分方案的合理性，然后使用L Method方法确定最合理的划分方案，即寻找评价图中曲线的拐点，并以此来确定密度标记的数量。
3）第3个阶段: 聚类生成阶段
此阶段根据密度标记对数据集进行聚类。经过确定子聚类密度标记阶段，所有的子聚类都具有了密度标记，即子聚类中的数据点具有密度标记。此阶段首先建立c个队列与c个不同的密度标记相对应，并将密度标记相同的数据点插入到同一个队列中。然后，按照密度标记值由高到低的顺序对所有数据点进行聚类，也就是说数据集中的数据点是按照密度由高到低的顺序进行聚类。由本文对聚类的定义可知，某个类中的数据点必定属于一个具有最高或次高密度标记的子聚类，注意，这里最高或次高密度标记是指该类中的数据点所具有的，而并不是数据集中的所有密度标记。最终，将未加类标记的数据点视为噪点。
四、DBSCAN算法的应用
DBSCAN是一种经典的基于密度的聚类算法，可以在带有噪声的环境下发现任意形状的类，所以在图像处理[8]、遗传思想进行数据划格[9]、桥梁健康监测、城市网格化管理与规划、调制识别、医疗图像分割和对交通事故多发点段进行排查[10]等许多领域已有了应用，此算法给人们的生活提供了更多的便捷。
参考文献
[1] 一种基于密度的快速聚类算法_周水庚[J].
[2] 一种基于相对密度的快速聚类算法[J].
[3] 基于密度聚类算法的改进方法研究_高昇[J].
[4] 多密度阈值的DBSCAN改进算法_谭颖[J].
[5] D BSCAN聚类算法的研究与改进_冯少荣[J].
[6] 一种改进的DBSCAN算法及其应用_李双庆[J].
[7] 基于DBSCAN聚类算法的研究与实现_荣秋生[J].
[8] 一种改进的DBSCAN密度算法_于亚飞[J].
[9] 一种改进的基于密度的DBSCAN聚类算法_王翠茹[J].
[10] 基于密度的DBSCAN聚类算法的研究及应用_冯少荣[J].
算法分析与设计复习题及参考答案
网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311.
骆驼祥子简答题
《骆驼祥子》简答题 1.请问小说的题目“骆驼祥子”主要包含哪些含义？ 答案：以“骆驼祥子”来命名有三层含义：（1）点明小说的主人公——祥子；（2）概括著作的一个主要情节——骆驼祥子称号的得来。（3）揭示主人公的性格——像骆驼一样吃苦耐劳、 沉默憨厚。 2. 请简单介绍小说围绕祥子主要讲述了哪些故事？ 答案：三起三落 （1）奋斗三年挣钱买了车→被十几个大兵抢了车； （2）卖骆驼又攒了买车钱→被孙侦探抢了买车钱； （3）结婚后靠虎妞买了车→最后下葬虎妞卖了车。 3、试结合祥子的相关事例分析其形象性格前后有着怎样的变化？ 答案：由人变“兽”，人生道路上的三部曲： （1）在自食其力的劳动中充满自信与好强； （2）在畸形结合的家庭中痛苦无奈地挣扎； （3）在极度绝望中扭曲了灵魂堕落成走兽。 4、请用简洁的语言概括发生在祥子身上的一件事。 答案：祥子一次送曹先生去看电影。在茶馆里碰见了饿晕倒在地的老马和他的孙儿小马。老马是一个有自己车的车夫，他的悲惨遭遇给祥最大的希望蒙上了一层阴影。他隐约地感到即 使自己买上车仍然没有好日子过。 5、《骆驼祥子》中的祥子在曹太太家的生活怎样? 答案：吃得饱、有间宽绰的屋子、饭食不苦、主人对他很客气 6、有人说：假如曹先生能及时回京，虎妞不死，小福子不死，祥子就不会走向堕落。你同 意吗？请结合小说谈谈自己的理解感受。 答案：不同意，《骆驼祥子》中的祥子代表的是祥子这一类生活在社会底层受迫害的人， 即使这一个祥子凭借如此的巧合未堕落，只要现实未改变他终究不幸，更何况一定会有其他 祥子一类的人堕落下去，这是大多数那个时代的“祥子”的命运 7、祥子前后有什么变化?你认为造成祥子这种变化的原因是什么? 答案：祥子开始是“体面的，要强的，好梦想的，利己的，个人的，健壮的，伟大的”，而后来变成了“堕落的，自私的，不幸的”，这是由封建社会黑暗腐朽的社会制度造成的。 8.请结合《骆驼祥子》的背景，总结小说的思想主旨。 20-30 年代正是中国现代史上最黑暗、最混乱的多灾多难的年代。新旧军阀不断的争权 夺势的混战，再加上各种自然灾害的横行，使得中国农村迅速走向破产。而成批破产的农民，为了谋求生路便纷纷涌入城市。祥子就是这些涌入城市的破产农民中的一个典型。 明确：小说主要讲述了人力车夫祥子人生中三起三落,由人堕落为“兽”的悲惨遭遇， 表达了作者对当时黑暗社会的批判, 对像祥子一样社会最底层的劳动者苦难命运的同情和 关怀。 9、请结合小说内容简单介绍《骆驼祥子》在语言表达上有哪些特色？ 明确：京味、幽默 “京味”如：写祥子从军阀部队逃出来以后喝馄饨时，“热汤像股线似的一直通到腹部，打 了两个响嗝，他知道自己又有了命”。完全用北京市民的口语，口中含汤的细节，热汤传身 的感觉，引起了祥子生命存在的心理体验。 “幽默”如：祥子的外貌和祥子给曹先生送东西的情节。 10.除了祥子之外，你还同情小说中的那一个人物？为什么？示例：小福子。尽管她一步
计算机算法与设计论文
中国传媒大学2011 学年第一学期计算机算法设计与分析课程 计算机算法设计与分析 题目回溯法解决n色方柱问题的算法设计与分析 学生姓名 学号 班级 学院 任课教师
回溯法解决n色方柱问题的算法设计与分析 摘要： 对于计算机科学来说，算法（Algorithm）的概念是至关重要的。算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。为了充分理解算法分析的思想，利用算法思想解决实际问题，所以用回溯法解决书上P181习题5—7 n色方柱问题。 关键字： 计算机算法回溯法 n色方柱 回溯法背景： 回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。 回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。 1、问题描述： 设有n立方体，每个立方体的每个面用红、黄、蓝、绿等n种颜色之一染色。要把这n个立方体叠成一个方形柱体，使得柱体的4个侧面的每一侧均有n种不同的颜色。试设计一个回溯算法，计算出n个立方体的一种满足要求的叠置方案。 例如：第一行有1个正整数n，0 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） 1．(2012淮安市)如图1-12所示为人和一些动物的发声频率、听觉频率的范围信息，试归纳出上述信息的共性特征，井简述其合理性． 图1-12 1.答：根据题干的图中信息得到：狗的发声范围：452～1800赫兹，猫的发声范围是：760～1500赫兹，而蝙蝠是10000～120000赫兹，海豚的是7000～120000赫兹．狗的听觉范围是：15～50000赫兹，猫的听觉范围是：60～65000赫兹，而蝙蝠是1000～120000赫兹，海豚的是150～150000赫兹．所以狗的发声的频率范围最小．听觉频率范围最大的动物是海豚． 2.(2012梅州)放电影时银幕上发生的反射属于什么反射？简述银幕做成白色的原因。 答案：放电影时银幕上发生的反射属于漫反射。银幕做成白色的原因是白色的银幕能反射各种色光（或不同频率、波长的光）（评分说明：每一问各2分，共4分） 3.（2011宁波）临近毕业，承承所在班级拍摄毕业照是，摄影师看到两边有些同学没有进入镜头，他及时进行了调整，顺利完成了拍照，请你说说摄影师是怎样进行调整的？ 将镜头离同学远一点，同时将暗箱的长度缩短一点。 4.（2012大连市）从冰箱冷冻室拿出的冻鱼，放在一盆冷水中，过一段时间将鱼从水中拿出，发现鱼的表面出现了一层较厚的冰。剥开这层冰，发现鱼已经完全“解冻”。请分析说明鱼表面这层较厚的冰是如何形成的。（“解冻”过程中，鱼的温度始终低于0℃） 从冷冻室拿出的鱼，温度远低于0℃.当将其放入水中时，它和水之间存在温度差，于是发生热传递。鱼吸收热量温度升高，水放出热量温度降低。当水温达到0℃时，由于鱼的温度还是低于0℃，所以水继续放热，于是凝固形成了冰。 5．（2011泉州市）1夏天，扇扇子为什么会感到凉快? 答：扇扇子时气流加快，使汗液蒸发加快，从而加快了蒸发时从身体吸热，所以感到凉快。 理工学院课程论文 论文题目贪心法的应用 课程名称算法设计与分析 姓名学号 专业计算机科学与技术年级 学院计算机日期（2014年4月10日） 课程论文评价标准 贪心法的应用 摘要：在解决问题的过程中，通过逐步获得最优解从而获得整体最优解的策略就是贪心策略，在已经学会在解的围可以确定的情况下，可以采用枚举或递归策略，一一比较它们最后找到最优解；但当解的围非常大时，枚举和递归的效率会非常低。这时就可以考虑用贪心策略。贪心算法没有固定的框架，算法设计的关键是贪心策略的选择，贪心策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略的影响。当一个问题有好几种解决方法时，贪心法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路以及贪心算法在实例中的应用。 关键词：贪心算法；删数问题；最小生成树 一、引言 在平时解决问题的过程中，当一个问题就有无后向性和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下就有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化解为一个更小的与原问题具有相同形式的子问题。尽管贪心算法对于很多问题不能总是产生整体最优解，但对于最短路径、最小生成树问题，以及删数问题等却可以获得整体最优解，而且所给出的算法一般比动态规划算法更为简单、直观和高效。 二、贪心算法的含义和特点 （一）贪心算法的含义 贪心算法是通过一系列的选择来得到问题解的过程。贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最有的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。 （二）贪心算法的特点 问答题示例 1.画出低碳钢受拉是的应力应变曲线，并解释钢材的屈服强度和极极限强度的意义与 作用。或问：各参数及屈服比，对选用钢材有何意义？ 2.碳素结构钢的牌号有哪几种类型。试说明依牌号的变化，碳素钢将做什么样的变化？ 为神魔土木工程中主要用Q235钢? 3.大理石一般仅限室内墙面柱面及磨损小的地面装饰，为什么？ 4.从水化硬化过程说明建筑石膏有哪些特点？ 5.为什么石膏制品适用于室内而不适用于室外？ 6.现有甲乙两种水泥厂生产的水泥熟料，其矿物成分如下：若用上述熟料分别制成水 泥，是估计他们的强度发展速度，水保养28天的强度有何差异？ 7.硅酸盐水泥强度发展规律？影响水泥凝结硬化的主要因素？ 8.什么叫水泥的体积安定性？水泥的体积安定性不良的原因是什么？如何解决安定 性不良？ 9.叙述矿渣水泥的定义，水化特点，技术性能。 10.混合材料参量高的通用硅酸盐水泥有哪些特性？ 11.什么是混凝土的和易性？和易性包括那几方面内容如何测定？影响因素有哪些？ 12.为什么不宜用高强水泥配低强混凝土？为什么不宜用低强水泥配高强混凝土？ 13.什么叫混凝土的耐久性？提高混凝土的耐久性的一般措施有哪些方面？ 14.简述引气剂加入混凝土中，混凝土性能的变化？ 15.试述砂石含泥量对混凝土性能的影响？ 计算 1.一块标准的普通粘土砖，其尺寸240 115 240 mm,已知密度为 2.7g/cm3 ,干燥时 质量为2500g，吸水饱和为2900g。求：（1）材料的表观密度（2）材料的孔隙率 （3）材料的体积吸水率。 2.已知某砌块的外观尺寸为240mm 240mm 115mm ，孔隙率为37%，单块砌块干 燥时质量为2487g,进水饱和后质量为2984g,试计算：（1）该砌块的表观密度。（2） 质量吸水率与体积吸水率（3）开口孔隙率与体积吸水率 3.已知某混凝土搅拌站的混凝土实验室配合比为C：Ｓ：Ｇ＝１：１.９２：３.９ ７，Ｗ／Ｃ＝０.５６，１立方米混凝土水泥用量为３００Ｋｇ，试计算：（１） 若搅拌站的砂和石的含水率为５％和１％，则配制８立方米混凝土各材料实际用 量为多少？（２）若采用水泥强度等级为４２.５的普通水泥，试估计水泥２８ 天强度。 4.某混凝土工程，其配合比为Ｃ：Ｓ：Ｇ＝１：１.９８：３.９０，Ｗ／Ｃ＝０.６ ４，混凝土拌合物的体积密度为２４００ｋｇ／ｍ３，试计算：１立方米混凝土 用量为多少。若采用水泥强度等级为４２.５的普通水泥，试估计水泥２８天强度。 5.计算某 以下为CPP源文件代码，工程建立参见《VC指导》 示例1：设备打开和关闭 #include 示例2：读取AI单通道采样值 #include 第一章简答题 1．试述混凝土棱柱体试件在单向受压短期加载时应力一应变曲线的特点。在结构计算中，峰值应变和极限压应变各在什么时候采用? 2．什么是混凝土的徐变?影响混凝土徐变的主要因素有哪些?徐变会对结构造成哪些影响? 3．画出软钢和硬钢的受拉应力一应变曲线?并说明两种钢材应力一应变发展阶段和各自特点。 4．混凝土结构对钢筋的性能有哪些要求? 1．图1-1 是一次短期加载下混凝土的应力-应变曲线。oa段，ζc-εc关系接近直线，主要是骨料和结晶体受里产生的弹性变形。ab段，ζc大约在（0.3～0.8）cf之间，混凝土呈现明显的塑性，应变的增长快与应力的增长。bc段，应变增长更快，直到峰值应变0，应力此时达到最大值----棱柱体抗压强度fc。cd段，混凝土压应力逐渐下降，当应变达εcu时，应力下降趋缓，逐渐稳定。峰值应变ε0，是均匀受压钩件承载力计算的应变依据，一般为0.002左右。极限压应变，是混凝土非均匀受压时承载力计算的应变依据，一般取0.0033左右。 2．在不变的应力长期持续作用下，混凝土的变形岁时间的增长而徐徐增长的现象称为徐变。徐变主要与应力大小、内部组成和环境几个因素有关。所施加的应力越大，徐变越大；水泥用量越多，水灰比越大，则徐变越大；骨料越坚硬，徐变越小；振捣条件好，养护及工作环境湿度大，养护时间长，则徐变小。徐变会使构件变形增加，是构件的应力发生重分布。在预应力混凝土结构中徐变会造成预应力损失。在混凝土超静定结构中，徐变会引起内力重分布 3．图1-2 是软钢（有明显流 幅的钢筋）的应力-应变曲线。在A点（比例极限）之前，应力与应变成比例变化；过A点后，应变较应力增长快，到达B’点（屈服上限）钢筋开始塑流；B点（屈服下限）之后，钢筋进入流幅，应力基本不增加，而应变剧增，应力-应变成水平线；过C点后，应力又继续上升，到达D点（极限强度）；过D点后钢筋出现颈缩，应变迅速增加，应力随之下降，在E点钢筋被拉断。图1-3是硬钢（无明显流幅的钢筋）的应力-应变曲线。钢筋应力在大约0.65倍的极限抗拉强度之前，应力-应变按直线变化，之后，应力-应变成曲线发展，但直到钢筋应力达到极限抗拉强度，没有明显的屈服点和流幅。超过极限抗拉强度后，由于颈缩出现下降段，最后被拉断。 4．（1）要求钢筋强度高，可节省钢材。 （2）要求钢筋的塑性好，使结构在破坏之前有明显的预兆。 （3）要求钢筋的可焊性好，使钢筋焊接后不产生裂纹及过大变形。 （4）要求钢筋与混凝土的粘接锚固性能好，使钢筋与混凝土能有效的共同工作。 第二章简答题 1．何谓结构上的作用、作用效应及结构的抗力? 2．荷载和作用有什么区别? 3．何谓结构的功能要求，它包括哪些内容?可靠度和可靠性的关系是什么? 4．我国不同类型建筑结构的设计使用年限是如何划分的? 5．结构的设计基准期和设计使用年限有何不同? 6．规范如何划分结构的安全等级? 7．何谓结构的极限状态?它包括哪两方面内容? 8．结构的功能函数和极限状态方程如何表达? 1.结构上的作用是指施加在结构上的集中力或分布，以及硬气结构外加变形或约束变形的原因。按其性质可分为直接作用或间接作用，以力的形式作用于结构上，称为直接作用，习惯上称荷载；以变形的形式出现在结构上，称为间接作用。按其随时间的变异分为永久作用，可变作用，偶然作用。 （1）永久作用：为在设计基准期内量值不随时间变化或变化与平均值相比可以忽略不计的作用，特点是统计规律与时间参数无关，例如结构自重，土压力等； （2）可变作用：在设计基准期内，有时出现有时不出现其量值随时间变化，且变化与平均值相比不可忽略，特点是统计规律与时间参数有关，例如风荷载，雪荷载，楼面活荷载；（3）偶然作用：在设计基准期内不一定出现，但一旦出现，往往数值大，持续时间短，例如爆炸，撞击，目前对一些偶然作用，国内尚未有比较成熟的确定的方法。 直接作用或间接作用与结构构件上，在结构构件内产生的内力或变形称为作用效应，例如梁中的弯矩，剪力，柱中的轴力，板的挠度以及变形裂缝等都属于作用效应。当为直接作用（荷载）时，其效应也称荷载效应。结构或结构件承受内力或变形的能力称为结构抗力，亦即结构承受作用效应的能力，如构件的受弯承载力，构件的刚度等。抗力与结构的形式，截面尺寸，材料等因素有关。 2.通常能使结构产生效应的原因，多数可归结为直接作用在结构上的力集（包括集中力和分布力），因此习惯上都将结构上的各种作用统称为荷载。但是有些情况下，比如温度变化，地基变形，地面运动等现象，这类作用不是以力集的形式出现，称为荷载并不合适，就像地震时，结构由于地面运动而产生惯性力，此力是结构对地震的反应，并非是力直接作用在结构上，应该叫“地震作用”。因此，通常认为作用的含义较全面，而荷载只是作用的一种形式。 3.结构在规定的设计使用年限内应满足的功能要求包括安全性、实用性和耐久性，具体包括： 算法设计与分析论文 题目0-1背包问题的算法设计策略对比与分析专业 班级 学号 姓名 引言 对于计算机科学来说，算法（Algorithm）的概念是至关重要的。算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。 一个算法应该具有以下五个重要的特征： 有穷性：一个算法必须保证执行有限步之后结束； 确切性：算法的每一步骤必须有确切的定义； 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。 计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》，可见算法在计算机科学界与计算机应用界的地位。 1 算法复杂性分析的方法介绍 算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。 不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 关于算法的复杂性，有两个问题要弄清楚：用怎样的一个量来表达一个算法的复杂性；对于给定的一个算法，怎样具体计算它的复杂性。 让我们从比较两对具体算法的效率开始。 1.1比较两对算法的效率 考虑问题1：已知不重复且已经按从小到大排好的m个整数的数组A[1..m]（为简单起见。还设m=2 k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标i，使得A[i]=c；若找不到，则返回一个0。 问题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A的第i个分量，经检测满足A[i]=c；或者扫到A的最后一个分量，经检测仍不满足A[i]=c。我们用一个函数Search来表达这个算法： Function Search (c:integer):integer; Var J:integer; Begin J:=1; {初始化} {在还没有到达A的最后一个分量且等于c的分量还没有找到时， 查找下一个分量并且进行检测} While (A[i] 8279键盘和显示程序 Z8279 EQU 08701H //8279状态/命令口地址 D8279 EQU 08700H //8279 数据口地址 LEDMOD EQU 10H //左端输入八位字符显示 //外部译码键扫描方式，双键互锁 LEDFEQ EQU 38H //扫描速率 LEDCLS EQU 0D1H //清除 LEDWR0 EQU 80H //设定的将要写入的显示RAM地 址 ORG 0000H AJMP START ORG 0040H START： MOV SP，#60H LCALL INIT8279 //初始化8279 W AIT： MOV DPTR，#Z8279 MOVX A，@DPTR ANL A，#0FH JZ WAIT MOV A，#40H MOVX @DPTR，A MOV DPTR，#D8279 MOVX A，@DPTR ANL A，#3FH MOV R4，#00H MOV R5，A LCALL DISLED SJMP W AIT INIT8279： //8279初始化子程序 PUSH DPH //保存现场 PUSH DPL PUSH ACC LCALL DELAY //延时 MOV DPTR ，#Z8279 MOV A，#LEDMOD //置8279工作方式 MOVX @DPTR，A MOV A，#LEDFEQ //置键盘扫描速率 MOVX @DPTR，A MOV A，#LEDCLS //清除 LED 显示 MOVX @DPTR，A LCALL DELAY //延时 MOV DPTR，#Z8279 MOV A，#90H MOV DPTR，#D8279 MOV A， #40H MOVX @DPTR，A MOV A，#40H MOVX @DPTR，A MOV A，#0H MOVX @DPTR，A MOV A，#0H MOVX @DPTR，A MOV A， #0EFH MOVX @DPTR，A MOV A，#27H MOVX @DPTR，A MOV A，#5BH MOVX @DPTR，A MOV A， #7FH MOVX @DPTR，A POP ACC //恢复现场 POP DPL POP DPH RET 显示字符子程序 输入：R4，位置：R5 DISLED： PUSH DPH //保存现场 PUSH DPL PUSH ACC MOV A，#LEDWR0 //置显示起始地址 ADD A，R4 //加位置偏移量 MOV DPTR，#Z8279 中考物理常考简答题示例及答案 1、在游泳池边向池底看去，感觉池水并不深，下水后才知道不是这么回事，试分析：为什么池水深度看起来比实际的浅? 答：光从一种介质斜射入另一种介质时要发生折射，人从空气看河底，实际看到的是河底的虚像，虚像的位置比实际河底的位置浅。 2、通常皮鞋的表面有许多毛孔，不是很光滑。当有灰尘附着在表面时，皮鞋就失去光泽，涂上鞋油仔细用布擦一擦，皮鞋就变得又亮又好看了，为什么? 答：因为皮鞋的表面不光滑有灰尘，光射向鞋面后发生漫反射，这样皮鞋就失去了光泽，涂上鞋油后，鞋油的微小颗粒能填充到鞋的毛孔中，用布仔细擦试，使鞋油涂抹得更均匀，鞋面就变得十分光滑，光射向鞋面后会发生镜面反射，皮鞋看起来就更光亮更好看了。 3、当往玻璃杯中倒入半杯开水时，你会发现杯子的上半部模糊不清，请你用初中物理知识解释这种现象。 答：往玻璃杯中倒入半杯开水时，开水蒸发产生水蒸气。高温水蒸气遇到温度较低的玻璃壁就液化成小水珠，并附在玻璃壁上，所以杯子的上半部模糊不清。 4、仔细观察，你会发现烧开水时，在最靠近壶嘴的地方反而不出现“白气”想一想，为什么? 答：那是因为靠近壶嘴的地方温度高，从壶嘴出来的是水蒸气，而水蒸气是肉眼看不到的。而那些看得到的"白气"是水蒸气遇冷而液化了，成了液态的小水珠，所以看得见。 5、在沙漠中的仙人掌的叶子呈针状有什么作用? 答：沙漠中的仙人掌的针状叶子减小了表面积,可防止体水分蒸发过快,有利于仙人掌在沙漠中的生存. 6、煨炖食物时，有经验的人总是先用大火将食物烧开，然后改用小火，试说明其中的道理。 答：先用大火可以将水迅速烧开，达到相对最高的温度沸点，继续加热水的温度不变，但是要保持水持续沸腾，要持续加热，调小火，是为了维持水沸腾，让水温保持最高，及可以使食物熟得快，也可以节能。 7、医生给病人检查时，常把一把小镜子在酒精灯上烧一烧，然后再放入病人的口腔，为什么? 答：这样做的目的是提高小镜子的温度,避免口腔中的水蒸气在镜面上遇冷而液化成小水珠附着在镜面上,使平面镜成像模糊. 算法设计与分析课程论文 1．引言 算法设计与分析是数据结构的有力补充，从中可以了解到算法设计的奥妙以及对数据结构中的数据存储结构更深层次的运用。计算机算法设计与分析是面向设计的、处于核心地位的一门学科。算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。算法设计是一件非常困难的工作，常用的算法设计方法有：分治法、贪心方法、动态规划、回溯法、分枝－限界法、基本检索与周游方法、遗传算法等。 本文主要对算法设计与分析中的递归算法以及动态规划算法进行了总结、分析以及对具体问题的编程实现。 2．递归算法分析 2.1递归算法简介与特点 递归就是在函数或子过程的内部，直接或间接地调用自己的算法；递归算法是从下往上进行思维，需要对问题有全局的了解；在使用递归算法时，必须至少测试一个可以终止递归的条件，并且还必须对在合理的递归调用次数内未满足此类条件的情况进行处理，如果没有一个在正常情况下可以满足的条件，则过程将陷入执行无限循环的高度危险之中；递归算法的描述非常简洁而易于理解，但因重复计算和较大的堆栈消耗使递归算法的解题的运行效率较低；并不是所有的语言都支持递归，在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢出等不利编程的因素，所以一般不提倡用递归算法设计程序。 2.2递归过程 递归过程是直接调用自己或通过一系列的过程调用语句间接调用自己的过程。在一个过程的运行期间调用另一个过程时，在执行被调用过程之前，系统要先把所有的实在参数返回地址等信息传递给被调用的过程保存，为被调用过程的局部变量分配存储空间，将控制转移到被调用入口。接下来从被调过程返回调用过程要保存被调用过程的计算结果，释放被调用过程的数据区，依照被调过程保存的返回地址将控制转移到调用过程。该过程服从后调用先返回的原则。 Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) 24个汇编小程序 题目列表： 逆序输出字符串“BASED ADDRESSING” 从键盘上输入两个数，分别放到x，y单元，求出它们的和 试编写一段程序，要求在长度为10h的数组中，找出大于42h的无符号数的个数并存入地址为up开始区域，找出小于42h的无符号数的个数并存入地址为down的开始区域 键盘输入一段字符串，其中小写字母以大写字母输出，其他字符不变输出 从键盘上就收一个小写字母，找出它的前导字符和后续字符，在顺序显示这三个字符 把一个包含20个数据的数组M分成两组：正整数组P和负整数组N，分别把这两个数组中的数据的个数显示出来 求出首地址为data的100个字数组中的最小偶数，并把它放在ax中 输入两船字符串string1和string2，并比较两个字符串是否相等，相等就显示“match”，否则显示“no match” 从键盘接收一个四位的十六进制数，并在终端显示与它等值的二进制数 从键盘输入一系列以$为结束符的字符串，然后对其中的非数字字符计数，并显示计数结果 有一个首地址为mem的100个字的数组，试编程序删除数组中所有为零的项，并将后续项向前压缩，最后将数组的剩余部分补上零 从键盘上输入一串字符（用回车键结束，使用10号功能调用）放在string中，是编制一个程序测试字符串中是否存在数字。如有，则把cl的第五位置1，否则将该位置置0 在首地址为data的字数组中，存放了100h的16位字数据，试编写一个程序，求出平均值放在ax寄存器中，并求出数组中有多少个数小于此平均值，将结果放在bx寄存器中(f分别考虑有符号数、无符号数情况) 一直数组A包含15个互不相等的整数，数组B包含20个互不相等的整数。试编制一个程序，把既在A中又在B中出现的整数存放于数组C中 设在A、B和D单元中分别存放着三个数。若三个数都不是0，则求出三个数的和并存放在S 单元，若其中有一个数为0，则把其它两个单元也清零。请编写此程序 计算机算法设计与分析小论文 摘要： 算法是一个系列解决问题的清晰指令,即在有限时间内能够对一定规范的输入,能够得到所需要的输出。如果一个算法本身是有缺陷的!那么他往往不是这个问题的最佳解决方法,可见一个算法的优劣是通过一定的准则来规定的。通过这学期的对《计算机算法分析设计》这门课程的学习让我们充分的了解到了计算机算法的多样性和复杂性，让我们更加细心和耐心的去对待这门课程。例如甲某要去某个地方旅游,他有很多种方案到旅游地,但是不见的每种方案都是合理最优的!这时就是需要考虑透过一定的算法来得到自己的最优路线。所以可见算法就是以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件，必须遵循软件工程的原则，设计出高效率的程序。一个高效的程序不仅需要编程技巧，更需要合理的数据组织和清晰高效的算法。目前我们将进行常见的算法分析设计策略介绍： 1.递归算法 1.1递归算法介绍: 直接或间接的调用自身的算法称为递归算法。或者说就是用自己来定义自己,不断调用自己的某一种状态。 1.2递归算法满足的条件 （1）递归满足2个条件： 1）有反复执行的过程（调用自身） 2）有跳出反复执行过程的条件（递归出口） 1.3递归例子 递归例子：阶乘问题 n! = n * (n-1) * (n-2) * ...* 1(n>0) //阶乘 intresult(int i) { int sum = 0; if (0 == i) return (1); else sum = i * result(i-1); return sum; } 可见一个递归算法都有一个比较特殊的特点,那就是要先处理一些比较特殊的情况再处理递归关系。如上例中如果是0!的话！那么他的阶乘就是1，所以先处理0!这个特殊情况，然后再调用其他的递归关系得到自己想要的阶乘。比如当我们想要求出4!的结果那么我们就需要调用result(3)的结果而result(3)又要调用result(2)的结果！就这样直到得出答案为止。 在我们日常,递归算法的出现可以帮助我们解决很多问题,正因为它的：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 2.分治算法 2.1分治算法介绍: 一个分治算法把问题实例划分成若干子实例（多数情况是分成两个），并分别递归地解决每个子实例，然后把这些子实例的解组合起来，得到原问题实例的解。 2.2 分治算法的特性 1）规模小，则很容易解决 2）大问题可以分为若干规模小的相同问题 3）利用子问题的解可以合并成该问题的解 2.3分治算法的遇到问题 为了阐明这个方法，考虑这样一问题：在一个整数组A[1...n]中，同时寻找最大值和最小值。下面我们来看一下用分治策略：将数组分割成两半，A[1...n/2]和A[(n/2)+1...n]，在每一半中找到最大值和最小值，并返回这两个最小值中的最小值及这两个最大值中的最大值。 过程 Min-Max ⅰ输入 n个整数元素的数组A[1...n]n为2的幂 ⅱ输出 (x,y), A中的最大元素和最小元素 3的阶乘： predicates factorial(unsigned,real) clauses factorial(1,1):-!. factorial(X,FactX):- Y=X-1, factorial(Y,FactY), FactX = X*FactY. goal X=3, factorial(X,Y). 输出表 domains list = integer* predicates write_a_list(list) clauses write_a_list([]). write_a_list([H|T]):- write(H),nl, write_a_list(T). goal write_a_list([1,2,3]). 统计表元素个数 domains list = integer* predicates length_of(list,integer) clauses length_of([], 0). length_of([_|T],L):- length_of(T,TailLength), L = TailLength + 1. goal length_of([1,2,3],L). 每个元素加1 domains list = integer* predicates add1(list,list) clauses add1([], []). add1([Head|Tail],[Head1|Tail1]):- Head1= Head+1, add1(Tail,Tail1). goal add1([1,2,3,4],NewList). 删除整数表中的负数 domains list = integer* predicates discard_negatives(list,list) clauses discard_negatives([],[]). discard_negatives([H|T],ProcessedTail):- H < 0,!, discard_negatives(T, ProcessedTail). discard_negatives([H|T],[H|ProcessedTail]):- discard_negatives(T, ProcessedTail). goal discard_negatives([2,-45,3,468],X). 判断表成员 domains namelist = name* name = symbol predicates member(name,namelist) clauses member(Name,[Name|_]). member(Name,[_|Tail]):- member(Name,Tail). goal member(susan,[ian,susan,john]). 合并表 domains integerlist = integer* predicates append(integerlist,integerlist,integerlist) clauses append([],List,List). append([H|L1],List2,[H|L3]):- append(L1,List2,L3). goal append([1,2,3],[5,6],L). 输出表中元素 domains integerlist = integer* namelist = symbol* predicates算法设计与分析复习题目及答案
简答题专项复习(有答案)
算法设计和分析课程论文
问答题示例
实例程序
混凝土简答题.上
算法分析与设计论文[精品文档]
8279示例程序
物理中学考试简答题示例及问题详解80个
算法设计与分析课程论文
算法设计与分析基础课后习题答案
24个汇编实例小程序文件
计算机算法设计与分析小论文
Prolog 程序范例