大学计算机-卓越-第8章

1、大学计算机面向实践与创新能力培养第8章 问题求解与算法设计卓越工程师培养计划提纲项目13： 使用Raptor进行算法设计和问题求解2项目描述3思维方法 第8章 问题求解与算法设计14知识和技能准备5实践操作引导拓展与创新项目13项目描述 本项目旨在使用可视化的快速算法设计工具Raptor进行一些常见问题的算法设计，以便使读者了解和掌握使用计算机编写程序进行问题求解的一般过程。（1）Raptor软件的安装。（2）设计一个算法，求s=1+3+5+7+97+99的计算结果。（3）从键盘输入一个正整数，判断其是否为素数。（4）输入一个正整数n，计算n！。 第8章 问题求解与算法设计项目13思维方法 瑞

2、士著名的计算机科学家尼古拉斯沃斯（Niklaus Wirth）曾提出一个著名的公式：程序=算法+数据结构。这说明，程序的核心是算法和数据结构。 Raptor是一种基于流程图的可视化编程开发环境。使用Raptor，用户可以集中精力设计和分析算法，而不必纠缠于具体语言繁琐的语法规则中。而且，Raptor可以实现算法的动态执行，有利于观察算法的执行过程，理清算法的设计思路。 第8章 问题求解与算法设计项目13知识和技能准备 1. 问题求解过程 问题求解的一般过程： 明确问题理解问题方案设计方案选择解决步骤方案评价 问题求解的计算机处理过程： 第8章 问题求解与算法设计问题描述问题抽象建立模型设计与实

3、现调试与测试项目13知识和技能准备 1. 问题求解过程 鸡兔同笼（穷举法） 第8章 问题求解与算法设计开始x0 x=352*x+4*(35-x)=94输出答案Xxx+1结束NYNY项目13知识和技能准备 2. 计算机求解问题的方法 （1）使用计算机软件进行问题求解 使用已有软件解决问题，这是计算机应用的典型方式。 （2）编写计算机程序进行问题求解 抽象分析与建模，设计与实现，调试与测试 （3）构建系统进行问题求解 要特别注意组成系统的各部分之间的相互约束、依赖和控制关系。 第8章 问题求解与算法设计项目13知识和技能准备 3. 算法及其描述 （1）算法的定义 算法（Algorithm）就是指为

4、解决一个具体问题而采取的方法和步骤的集合。算法是程序设计的灵魂。 （2）算法的基本特征 0或多个输入； 1或多个输出； 有穷性；确定性； 可行性。 第8章 问题求解与算法设计项目13知识和技能准备 3. 算法及其描述 （3）算法的表示 自然语言表示法 伪代码表示法 流程图表示法 N-S图 PAD图 第8章 问题求解与算法设计项目13知识和技能准备 3. 算法及其描述 流程图是一种采用程序框、流程线及简要文字说明来表示算法的有效方法。 其中，程序框图用于表示算法中的具体步骤，流程线表示算法的执行顺序。 第8章 问题求解与算法设计项目13知识和技能准备 3. 算法及其描述 流程图是一种采用程序框、

5、流程线及简要文字说明来表示算法的有效方法。 其中，程序框图用于表示算法中的具体步骤，流程线表示算法的执行顺序。 第8章 问题求解与算法设计项目13知识和技能准备 3. 算法及其描述 （4）算法的评价 对于算法的评价有两个基本标准，即时间复杂度和空间复杂度。 时间复杂度：常数O(1)、对数阶O(log2n)、线形阶O(n)、线形对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、指数阶O(2n)。 空间复杂度：即执行这个算法需要占用多少资源（可以理解为占用了多少计算机存储单元）。 算法的可读性 第8章 问题求解与算法设计项目13知识和技能准备 4. 程序的三种基本结构 顺序结构，选择结

6、构，循环结构 第8章 问题求解与算法设计项目13知识和技能准备 5. Raptor可视化算法流程图设计 第8章 问题求解与算法设计项目13知识和技能准备 5. Raptor可视化算法流程图设计 最大公约数问题 第8章 问题求解与算法设计nrmn开始求m和n的余数r结束NY输入m，nr=0?输出最大公约数n项目13实践操作引导（1）Raptor软件的安装 对参考图8-7和8-8，同时注意赋值框和输入框的区别： 第8章 问题求解与算法设计项目13实践操作引导（2）求s=1+3+5+7+97+99的结果。（循环结构） 第8章 问题求解与算法设计项目13实践操作引导（3）判断x是否是素数。（三种结构，标志变量） 第8章 问题求解与算法设计项目13实践操作引导（4）求n！。（递归算法） 第8章 问题求解与算法设计项目13拓展与创新（1）计算s=1-2+