程序设计思想算法设计

1、程序设计第二课堂算法设计思想纪一鹏课程内容算法算法定义描述一个算法为什么要学算法怎么设计一个算法像计算机一样去思考结构化程序设计算法分析综合举例什么是算法算法（Algorithm）是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，能够得出所要求或期望的终止状态或输出数据。什么是算法以下是Donald Knuth在他的著作The Art of Computer Programming里对算法下的定义：输入：一个算法必须有零个或以上输入量。输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地符合要求或期望，

2、通常要求实际运行结果是确定的。什么是算法有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。简单描述一个算法电灯不亮了怎么办？（1）判断是否接通电源（2）如果没有，把电源接上（3）如果是，判断灯泡是否烧坏（4）如果烧坏了，换一个灯泡（5）如果没烧坏，还是送去修吧简单描述一个算法程序流程图伪代码LAMP_DOESNOT_WORK()1 if LAMP_PLUGGED_IN

3、2 if BULB_BURNED3 Replace Bulb4 else Repair Lamp5 else Plug In Lamp为什么要学算法具备从自然世界中提取出抽象模型，并通过系统化的方法解决。真正的会编程！课程内容算法算法定义描述一个算法为什么要学算法怎么设计一个算法像计算机一样去思考结构化程序设计可用的工具算法分析综合举例像计算机一样去思考你能找出最大的数吗？133ln (10)251635172212321248e55173417516516516516516516516516516516516516516484848484848481231231231231231231231

4、23123像计算机一样思考找出最大的数（1）在给定的数里面任选一个数X（2）用X与其他所有的数比较（3）如果存在一个数Y比X大，则令X=Y（4）全部比较结束后，X的值即为给定集合中最大的数。像计算机一样去思考随着问题规模的增加，人脑的直观性思维逐渐难以应对，我们需要每秒能进行数亿次计算的计算机来帮助人类。像计算机一样去思考计算机很笨！一种用于高速计算的电子计算机器，可以进行数值计算，又可以进行逻辑计算，还具有存储记忆功能。不能像人一样思考（暂时），远远不够智能。接受人的命令！像计算机一样去思考计算机工作原理机器语言汇编语言高级/脚本语言自然语言？像计算机一样去思考我们要做的：（1）设计正确高效

5、的算法（2）用编程语言实现（3）让计算机忙活去吧！结构化程序设计结构化程序设计（structured programming）是进行以模块功能和处理过程设计为主的详细设计的基本原则。其概念最早由E.W.Dijikstra在1965年提出的，是软件发展的一个重要的里程碑。它的主要观点是采用自顶向下、逐步求精的程序设计方法；使用三种基本控制结构构造程序，任何程序都可由顺序、选择、循环三种基本控制结构构造 。结构化程序设计自顶向下，逐步求精全目标局模块1问题1问题2模块2问题1程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设

6、计，逐步使问题具体化。PRECEGURE（） Input（）Initialize（）Work（）Output（）结构化程序设计顺序结构步骤1步骤2步骤n结构化程序设计选择结构IF （条件） THEN ELSEIF （条件）ELSE 结构化程序设计循环结构34512FOR i=1 TO N DO WHILE （终止条件） DO 结束循环结束条件注意死循环！可用的工具变量：整数、浮点数、字符、指针、布尔型容器：数组、字符串、表三种逻辑结构函数，过程对象什么是好算法不同的算法可能用不同的时间、空间或效率来完成同样的任务。时间复杂度算法的时间复杂度是指算法需要消耗的时间资源。时间复杂度越低越好？空间复

7、杂度算法的空间复杂度是指算法需要消耗的空间资源。空间复杂度越低越好？牺牲时间换空间牺牲空间换时间算法分析对正确算法质量优劣的评价除正确性外，通常从三个方面评价一个算法：依据算法编写的程序在计算机中运行时间多少的度量，称之为时间复杂度 依据算法编写的程序在计算机中占存储空间多少的度量，称之为空间复杂度其他方面。如算法的可读性、可移植性以及易测试性的好坏。 反映算法运行的快慢反映算法需要额外空间的多少时空效率高的算法才是一个好的算法，它常常是不懈努力和反复修正的结果算法分析时间复杂度一个程序在计算机中运行时间的多少与诸多因素有关，其中主要有： 问题的规模。编译程序功能的强弱以及所产生的机器代码质量

8、的优劣。 机器执行一条指令的时间长短。 程序中那些基本语句的执行次数。 几乎所有的算法时间效率都与规模有关算法分析给定n个数的序列A=a1,a2,an输出该序列的一个重排列A=a1,a2,an，使得a1=a2=an算法分析设序列A初始时为空（1）从A中取元素ai。（2）从左到右与A中已有的元素比较，直至找到一个j，使得aj=ai=0)的灯。例如：1,4,7.给出按开关的次数C和彩灯的初始状态，给出最后灯的所有可能情况。Party Lamps(IOI98)若单纯枚举所有情况，因为有4个开关可以按，一共按了C次，所以时间复杂度为O(4C)，复杂度过高无法解决。条件中暗藏玄机！Party Lamps

9、（IOI98）开关1123456789开关213579开关32468开关4147简化条件1：无论如何按开关，相隔为6的灯的状态总同时改变。简化条件2：同一个开关，只有按奇数次和按偶数次两种区别。枚举次数变为24=32，且只需记录前六个彩灯的状态即可。复杂度为O(n）！算法举例枚举枚举法是利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检验，从中找出符合要求的答案，因此枚举法是通过牺牲时间来换取答案的全面性。枚举的优化深度优先搜索，广度优先搜索，分支定界汉诺塔（Hanoi Tower）有n个圆盘的汉诺塔需要多少次移动？汉诺塔（Hanoi Tower）要把n个圆盘移

10、动到第三个柱子上（1）把n - 1个圆盘移动到第二个柱子上（2）把最大的圆盘移动到第三个柱子上（3）把n - 1个圆盘从第二个柱子移动到第三个柱子上设n个圆盘的汉诺塔要移动F（n)次则F（n) = 2*F(n-1) + 1汉诺塔（Hanoi Tower）HANOI_TOWER()F1 = 1FOR i=2 TO n DOFi = 2*Fi-1 + 1PRINT Fn (N)算法举例递推给定一个数的序列H0,H1,Hn,若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0in)联系起来，这样的式子就叫做递推关系。Fibonacci数，Stirling数，Ca

11、talan数，组合数贪心算法，动态规划归并排序给定n个数a1,a2,an输出序列的一个重排列a1,a2,an，使得a1 a2an归并排序如果已知两个不下降序列，A=a1,a2,an,B=b1,b2,bm， 如何将它们合并成一个下降序列C？再举扑克牌的例子。假设有两堆扑克牌面朝上的在桌上，每一堆都是已排序的，最小的牌在最上面。在两堆拍中，选取顶上两张中较小的一张，将其取出后（它所在堆的顶端又会露出一张新的牌）放到输出堆中。重复这个步骤，知道某一堆为空时停止。这时，把剩下的一堆直接放到要合并的堆上即可。归并排序如果已知两个不下降序列，A=a1,a2,an,B=b1,b2,bm， 如何将它们合并成一

12、个下降序列C？每次比较A，B序列中最小的数a和b，若ab，则把b放入序列C中，并从序列B中删除b。重复上述过程，直到序列A，B都空为止。共需要m+n次操作。1351317252524510182427归并排序分解：将n个元素分成各含n/2个元素的子序列。解决：用合并排序法对两个子序列递归的排序。合并：合并两个已排序的子序列以得到排序结果。归并排序用归并排序处理A=5,2,4,7,1,3,2,6524713262 54 71 32 62 4 5 71 3 2 61 2 2 3 4 5 6 7归并排序归并排序的时间复杂度？T(n)=O(1)若n=1 =2*T(n/2)+O（n）若n1最终时间复杂度为O（nlogn）算法举例分治将原