《《计算思维实训(2》由会员分享，可在线阅读，更多相关《《计算思维实训(2（6页珍藏版）》请在金锄头文库上搜索。
1、2013-2014学年冬季学期计算思维实训(2)(0830A031)课程报告学号12120951学院计算机工程与科学学院姓名丁家星手工签名报告题目成绩平时工作课程报告成绩完成情况(25%)进步量(25%)格式(20%)内容(30%)百分制五级分制教师评语教师签名批阅日期年 月 日注五级分制成绩为：优秀(90-100),良好(80-89),中等(70-79),及格(60-69), 不及格(0-59)。对算法的认识丁家星（12120951,计算机工程与科学学院）1算法概述1.1算法与问题求解1.1.1算法的定义算法就是为了求解问题而给出的指令序列，可以理解为由基本运算及规定的运算顺序所构成的完整的
2、 解题步骤，而程序是算法的一种实现。计算机按照程序逐步执行算法，实现对问题的求解。简单来说，算 法可以看成是按照要求设计好的有限的、确切的计算序列，并且这样的步骤和序列可以解决某一类问题。 算法设计的重点就是把人类找到的求解问题的方法、步骤，以过程化、形式化、机械化的形式表示出来， 以便让计算机执行。算法是一个十分古老的研究课题，然而计算机的出现为这个课题注入了青春和活力， 使算法的设计和分析成为计算机科学中最为活跃的研究热点之一。1967年，D.E.Knuth指出“算法是贯穿 在所有计算机程序设计中的一个基本概念”，所以，算法被誉为计算机学科的灵魂！1.1.2问题求解用计算机解决实际问题，就
3、是在计算机中建立一个解决问题的模型。在这个模型中，计算机内部的数 据表示了需要被处理的实际对象，包括其内在的性质和关系；处理这些数据的程序；模拟对象领域中的求 解过程。通过解释计算机程序的运行结果，便得到了实际问题的解。下面给出用计算机求解问题的一般步 骤。步骤分为：问题分析、数学模型的建立、算法设计、算法表示、算法分析、算法实现、程序调试、结 果整理文档编制。1.2算法的描述1.2.1 基本控制结构的描述计算机科学家已经证明只需要使用三种基本控制结构就可以构建解决任何复杂问题的算法。这三种基 本控制结构是：顺序结构、选择结构和循环结构。为了更好地领会和理解这三种基本控制结构,下面将C语 言与
4、N-S图两种描述方法对照给出。三种结构分别为顺序结构、选择结构、循环结构。1.2.2 C算法描述约定形式参数与实际参数之间信息传递的主要方式有两种：一是值传递，即将实参表达式的值依次传递给 对应的形式参数，而形参的改变不会影响到实参，通常称为单向的传值过程；二是地址传递，即将实参变 量的地址依次传递给对应的形式参数，这时对应的形参和实参就具有了相同的地址，也就是说他们共享地 址空间，因此，若形参改变，则实参必然随之改变。2算法分析2.1 算法的一些特点2.1.1 算法的评价标准1正确性：说一个算法是正确的，是指对于一切合法的输入数据，该算法经过有限时间的执行都能产 生正确的结果。正确性是算法设
5、计最基本、最重要、第一位的要求。2.可读性：可读性的含义是指算法思 想表达的清晰性、易读性、易理解性、易交流性等多个方面，甚至还包括适应性、可扩充性和可移植性等。 一个可读性好的算法常常也相对简单。3.健壮性：一个算法的健壮性是指算法思想表达的稳定性、容错性、 可靠性和环境适应性等。当出现输入数据错误、无意的操作不当或某种失误、软/硬件平台和环境变化等 故障时，能否保证正常运行，不至于出现莫名其妙的现象、难以理解的结果甚至经常瘫痪死机等。4时间 复杂度：为了分析某个算法的执行时间，可以将那些对所研究的问题来说是基本的操作或运算分离出来， 再计算基本运算的次数。一个算法的时间复杂度是指该算法所执
6、行的基本运算的次数。2.1.2 算法的时间复杂度和算法执行时间相关的因素：问题中数据存储的数据结构、算法采用的数学模型、算法设计的策略、 问题的规模、实现算法的程序设计语言、编译算法所产生的机器代码的质量、计算机执行指令的速度。算 法效率的衡量方法：1.事后统计法是先将算法用程序设计语言实现，然后度量程序的执行时间。因为很多 计算机内部又有计时功能，所以可通过一组或多组统计数据来衡量不同算法的优劣。2.事前分析估算法也 称预先计算估计法，是指在算法设计时，事前评价其时空效率问题。3贪心算法3.1 贪心算法定义贪心算法可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理
7、。也就 是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或 最优的算法。贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，通过一系列的选择来得到一个问题的 解，而它所做的每一次选择都是当前状态下某种意义的最好选择，即贪心选择。即希望通过问题的局部最 优解来求出整个问题的最优解。这种策略是一种很简洁的方法，对许多问题它能产生整体最优解，但不能 保证总是有效，因为它不是对所有问题都能得到整体最优解，只能说其解必然是最优解的很好近似值。3.2 贪心算法的基本思路与实现过程3.2.1贪心的基本思想用局部解构造全局解，即从问题的某一个初始解逐步逼近给定
8、的目标，以尽可能快地求得更好的解。当某 个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的 基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。利用贪心策略解题，需要解决两个问题：（1）该题是否适合于用贪心策略求解；（2）如何选择贪心标准，以得到问题的最优/较优解。3.2.2贪心算法的实现过程（1）应用同一规则F,将原问题变为一个相似的、但规模更小的子问题；（2）从问题的某一初始解出发：While （能朝给定目标前进一步）求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。3.2.3贪心算法的核心贪心算法的核心问题是选择能
9、产生问题最优解的最优度量标准，即具体的贪心策略。贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值（或较优解）的一种解题方法。 其实，从“贪心策略” 一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心 策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性 决定了该题运用贪心策略可以得到最优解或较优解。3.2.4贪心算法的特点贪心算法的最大特点就是快，通常是线性二次式，不需要多少额外的内存。一般二次方级的存储要浪费额 外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且 更快执行
10、。如果有正确贪心性质存在，那么一定要采用。因为它容易编写，容易调试，速度极快，并且节 约空间。几乎可以说，此时它是所有算法中最好的。但是应该注意，贪心算法有两大难点：(1) 如何贪心怎样用一个小规模的解构造更大规模的解呢？总体上，这与问题本身有关。但是大部分都是有规律的。正 因为贪心有如此性质，它才能比其他算法快。具有应当采用贪心算法的问题，当“贪心序列”中的每项互异且当问题没有重叠性时，看起来总能通过贪 心算法取得(近似)最优解的。或者，总有一种直觉在引导我们对一些问题采用贪心算法。其中“找零钱” 这个问题就是一个例子。题中给出的硬币面值事实上具有特殊性，如果面值发生变化，可能贪心算法就不
11、能返回最优解了。但是，值得指出的是，当一个问题具有多个最优解时，贪心算法并不能求出所有最优解。 另外，我们经过实践发现，单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后 即时输出的。(2) 贪心的正确性要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间 有联系，往往靠贪心算法生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。对某 些问题贪心性质也许是错的，即使它在大部分数据中都是可行的，但还必须考虑到所有可能出现的特殊情 况，并证明该贪心性质在这些特殊情况中仍然正确。而这样容易陷入证明不正确贪心性质的泥塘中无法自 拔
12、，因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他 算法会比它要保险。4算法举例 输入n个元素，输出其和为m的全部整数对。答：首先对n个元素按升序排序，对排好序元素设置首尾两个指针low,high,当lowhigh时进行如下运算： 如果 Elow+Ehigh=m,则；low+;high,输出数对如果 Elow+Ehighm, low+如果 Elow+Ehighm, high当Low=high时，程序结束。 输入n个元素，输出其包含的最长等差数列。定义三元组e(d力，其中i、j为元素标号且ij, d为第j个元素与第i个元素的差。计数器max=0记录当前最长
13、等差数列的长度，数组result将保存最长等差数列的值。将输入的n个元素按照升序排序，对于所有1 - l max,则max二” +1并将丿：保存到result中。之后，置e_start二t。查找ee(dstart e,istart estartj ), e (d , ie _ starte _ ende _ end e _ endje_en中“最长链”方法如下:数组nextn, nexti初始值为T,最终记录元素i应该链接的下一个元素的标号;数组labeln, labeli初始为false，记录每一个元素是否已经被访问过。顺序遍历Ek中的每一个元组7 (dk, lt, jt)，如果neXtit为-1,则neXtit T ；否则，继续遍历下一 个三元组。从当前未被遍历的最小下标s开始遍历，直到所有元素都被遍历过，执行操作: 如果nexts是-1，那么labels= true，记录下整数对(s,1)；否则执行start 二s,cou nt er=1；执行操作 labels= true, s=nexts, cou
