第5章问题求解与算法设计
第5章问题求解与算法设计问题求解过程01用计算机求解问题的方法02算法与程序0304本讲提纲Raptor可视化算法流程图设计
5.1问题求解过程问题求解过程问题求解的一般过程：明确问题→理解问题→方案设计→方案选择→解决步骤→方案评价问题求解的计算机处理过程：问题描述问题抽象建立模型设计与实现调试与测试
5.1问题求解过程问题求解的计算机处理过程开始x←0x=352*x+4*(35-x)=94输出答案Xx←x+1结束NYNY鸡兔同笼2x+4（35-x）=94设鸡有x只，则x的可能取值是0至35搜索参数:答案符合的条件:——穷举法今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？——《孙子算经》，成书约在4~5世纪
计算机求解问题的方法5.2使用计算机求解问题的方法（1）使用计算机软件进行问题求解使用已有软件解决问题，这是计算机应用的典型方式。（2）编写计算机程序进行问题求解抽象分析与建模，设计与实现，调试与测试（3）构建系统进行问题求解要特别注意组成系统的各部分之间的相互约束、依赖和控制关系。
5.3算法与程序结构●程序编写的关键是什么？●什么是算法，如何表示算法？●如何设计适合的算法来进行问题的求解？瑞士著名的计算机科学家尼古拉斯·沃斯（NiklausWirth）曾提出一个著名的公式：程序=算法+数据结构。这说明，程序的核心是算法和数据结构。
算法5.3算法与程序结构一、算法的概念算法（Algorithm）就是指为解决一个具体问题而采取的方法和步骤的集合。算法是程序设计的灵魂。生活中的算法——算法无处不在：?超市收银?旅程安排（时间、里程、花费）?手机话费省钱方案?如何合理安排学习和生活时间才能让学习效率最高
算法5.3算法与程序结构算法的基本特征1.有零个或多个输入：需要从外界获取必要的信息2.有一个或多个输出：需要把求得得解进行输出3.确定性：每一步必须明确4.有穷性：算法要包含有限的步骤5.可行性：算法描述的所有操作都可以通过已经实现的基本运算的有限次执行来实现
算法的表示5.3算法与程序结构自然语言表示法伪代码表示法流程图表示法N-S图PAD图伪代码表示法判断一个年份是否为闰年的算法：BEGIN（算法开始）输入年份yIFy能被4整除THENIFy不能被100整除THEN输出“y是闰年”ELSEIFy能被400整除THEN输出“y是闰年”ELSE输出“y不是闰年”ENDIFENDIFELSE输出“y不是闰年”ENDIFEND（算法结束）
算法的表示5.3算法与程序结构流程图是一种采用程序框、流程线及简要文字说明来表示算法的有效方法。其中，程序框图用于表示算法中的具体步骤，流程线表示算法的执行顺序。
算法的表示5.3算法与程序结构流程图表示法判断一个年份是否为闰年的算法：Y输出Y是闰年NNYN400能整除yY100能整除y4能整除y输入年份y输出Y不是闰年输出Y是闰年输出Y不是闰年结束开始
5.3算法与程序结构典型算法思维及策略枚举法按照问题的特性，一一列举出该问题所有可能的解，并一个不漏地进行检验，从中找出符合要求的答案。百鸡百钱鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？分析：?设鸡翁、母、雏分别为x,y,z，有x+y+z=100?买百鸡要百钱，有5x+3y+z/3=100?x、y、z取值范围?x:?y:?z:0-200~330~100?x?y?z?100??5x?3y?z/3?100
5.3算法与程序结构递归递归是计算机科学中的一种重要思维方式，递归算法是程序设计中的一种重要算法。例如：阶乘问题典型算法思维及策略自己调用自己
5.3算法与程序结构分治把一个复杂的问题分成两个或更多的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一堆金币中快速找出掺入的一枚铜币典型算法思维及策略
5.3算法与程序结构动态规划法动态规划的求解过程是一个多阶段决策过程，每步求解的问题是后面阶段求解问题的子问题，每步决策将依赖于前阶段决策的结果，根据每一步所选决策的不同会引起状态的转移，最后在变化的状态中获取到一个决策序列。典型算法思维及策略
5.3算法与程序结构贪心法在对问题求解时，总