资源预览内容
第1页 / 共21页
第2页 / 共21页
第3页 / 共21页
第4页 / 共21页
第5页 / 共21页
第6页 / 共21页
第7页 / 共21页
第8页 / 共21页
第9页 / 共21页
第10页 / 共21页
亲,该文档总共21页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第1章 问题解决与程序设计,问题分析与算法设计 程序设计,1.1 程序解决实际问题的步骤,软件工作原理 一个问题的求解是通过构造其算法(程序)来解决。 软件开发过程 问题的定义 设计解决方案 编码 测试 运行及维护,1.2 算法设计,算法是解决某类特定问题的方法和步骤。 为解决一类特定问题而采取的确定的有限的操作步骤称为算法。 算法是一系列解决问题的清晰指令,能够对一定规范的输入,在有限的时间获得要求的输出。 计算机算法分为:数值运算算法和非数值运算算法。,1.2.1 算法设计中常用的思维方法,枚举法 基本思想是:首先根据问题的部分条件预估答案的范围,然后在此范围内对所有可能的情况进行逐一验证,直到全部情况均通过了验证为止。若某个情况使验证符合题目的全部条件,则该情况为本题的一个答案;若全部情况验证结果均不符合题目的全部条件,则说明该题无答案。 【例1-1】 今有鸡兔同笼,上有三十五头,下有九十四足,问鸡兔各几何?,对于计算机而言,可以使用枚举法来解决该问题。 据题意可知,鸡与兔的范围一定是0到35之间的正整数,那么,最简单的解题方法是:假设一组x、y的值,直接带入方程组求解,即在各个变量的取值范围内不断变化x、y的值,穷举x、y全部可能的组合,若满足方程组则是一组解。这样即可得到问题的全部解。 这个算法中需要不断循环x、y全部可能的组合。,1.2.1 算法设计中常用的思维方法,枚举法解题需要以下步骤: (1) 分析题目,确定答案的大致范围。 (2) 确定列举方法。常用的列举方法有:顺序列举,排列列举和组合列举。 (3) 作试验,直到遍历所有情况。 (4) 试验完后可能找到与题目要求完全一致的一组或多组答案,也可能没找到答案,即证明题目无答案。,1.2.1 算法设计中常用的思维方法,枚举法的特点 算法简单,容易理解,但运算量较大。 枚举法的应用 可确定取值范围但又找不到其它更好的算法时,可以用枚举法。 通常枚举法用来解决“有几种组合“、“是否存在“、求解不定方程等类型的问题。 利用枚举法设计算法大多以循环控制结构实现 。 拓展训练:谁说了假话,1.2.1 算法设计中常用的思维方法,迭代法 迭代法是一种数值近似求解的方法,在科学计算领域中,许多问题需要用这种方法解决。 迭代法的特点是:把一个复杂问题的求解过程转化为相对简单的迭代算式,然后重复执行这个简单的算式,直到得到最终解。 【例1-2】 计算S=1+2+3+4+100,1.2.1 算法设计中常用的思维方法,递归法 递归是设计和描述算法的一种有力的工具,在复杂算法的描述中被经常采用。 例如著名的斐波那契数列,由于数列的未知项与已知项之间存在着一定关系,借助于已知项和这一关系,就可逐项求出未知项。 【例1-3】 求n!,n=15。,1.2.1 算法设计中常用的思维方法,分治法 在求解复杂问题时,尽可能地把这个问题分解为较小部分,找出各部分的解,然后再把各部分的解组合成整个问题的解,这就是所谓的分治法。 分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 分治策略是对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,然后将各子问题的解合并得到原问题解。,1.2.1 算法设计中常用的思维方法,分治法的思维过程: 分-将问题分解为规模更小的子问题; 治-将这些规模更小的子问题逐个击破; 合-将已解决的子问题合并,最终得出“母”问题的解; 分治法所能解决的问题一般具有以下几个特征: (1)该问题的规模缩小到一定的程度就可以容易地解决。 (2)该问题可以分解为若干个规模较小的相同问题。 (3)利用该问题的子问题的解可以合并为该问题的解。 (4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。,1.2.1 算法设计中常用的思维方法,1.2.2 算法的表示,算法可以用任何形式的语言和符号来描述 自然语言 程序语言 流程图 N-S图 PAD图 伪代码 其他,1顺序结构,1.2.3 算法中的控制结构,2选择结构,1.2.3 算法中的控制结构,3循环结构,1.2.3 算法中的控制结构,1容错处理 设计再精确的算法在执行过程中也难免会出现一些故障,这些故障可能是算法本身不严谨所致,也可能是由于运行环境改变所致。因此,算法设计过程中,必须进行一定的容错处理,当出现问题时,应该能很快做出恰当的处理。 2并行处理 算法的执行效率也是算法的一个重要指标,并行处理是提高算法效率的一个有效途径。多进程、多线程技术,充分利用这些软硬件支持,设计一些并行算法可提高算法效率。,1.2.4 算法设计过程中需要考虑的其他问题,算法的实现就是将一个算法转换成计算机程序,一个算法可以用不同的程序设计语言实现。 随着软件技术的发展,目前的程序设计语言种类繁多,C、C+、C#、Java、Python、R、, 需要根据问题要求和算法特点合理选择编程语言 。 结构化程序设计语言与面向对象程序设计语言。,1.3 算法实现与程序设计,1结构化程序设计 结构化程序设计以过程为中心思考问题,以功能模块和过程设计为主,其主要要点如下: 采用自顶向下,逐步求精的程序设计方法。 任何程序只使用顺序、选择、循环这三种基本控制结构。 结构化程序设计要求程序中的每个功能模块是单入口和单出口的;没有死循环;没有死语句,即没有绝对不会被执行的语句。,1.3 算法实现与程序设计,2面向对象程序设计 面向对象程序设计以对象为中心思考问题,以要解决的问题中所涉及的各种对象为主体,思维方式符合人们日常的思维习惯。相比传统的面向过程的程序设计方法,面向对象技术能够降低解决问题的难度和复杂性,提高代码的复用度和编程的效率,提高代码的可维护性。 对象与类 三个特点:封装、继承、多态,1.3 算法实现与程序设计,1分析问题的能力 2程序设计语言掌握能力 “读、写、查”是最好的程序设计的学习方法。 3编写符合规范的程序 4检查程序、排错的能力 5选择好的开发环境,1.3.2 其他需要说明的问题,1.1 上网搜索计算思维的资料,理解计算思维。 1.2 设计算法,实现交换存储单元a与b的内容。 1.3 设计算法,求10个数中的最大值和最小值。 1.4 设计算法,求n个数的平均值。 1.5 设计判断闰年的算法。 1.6 设计算法,计算斐波那契数列中的第20项 。 1.7 设计算法,要求将n个自然数从小到大排序输出。 1.8 设计算法,要求能在n个自然数中查找是否存在某个自然数m。,作业,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号