算法第2章教学提纲

第2章算法与程序实现
2.1解决问题的一般过程和用计算机解决问题
2.1.1解决问题的一般过程
分析问题
调查、收集资料
明确目标、条件
找出已知与未知联系
例子：交通警察观察路况，维护交通秩序
寻找解决问题的途径与方法
关联已知条件与规则
设计求解方案
例子：交通警察指挥车辆有序通行
解决问题并验证结果
依据求解方法执行
检验答案、评估效果
课堂上，我鼓励学生主动参与交通警察指挥交通的案例分析，让他们了解如何将理论知识应用于实际情境。多数学生能够积极参与，但也有部分学生在理解问题分析和解决方案设计方面存在困难。未来课程中，我计划采用更多互动教学法，如小组讨论或角色扮演，以提高学生的参与度和理解能力。
此外，我们也涉及了用计算机解决问题的过程。我注意到，对于计算机编程和算法设计的部分，学生们显示出极大的兴趣，但同时也表达了对编程逻辑和语言学习的难度。为了帮助学生克服这些难点，我决定在未来的课程中加入更多的编程实践和逐步指导，例如通过分解程序编写步骤，并提供更多的实例演示，以增强他们的编程信心和技能。
独立尝试解答题目，然后与教师和同学讨论。
记录解题过程中的疑问和教师的反馈。
通过真题演练，让学生熟悉考试形式和题型。
提高学生的解题能力和应试技巧。
活动四：
巩固练习
素质提升
布置与本节课内容相关的编程练习题。
巡视课堂，为学生提供即时帮助和指导。
在计算机上实践编程，应用所学知识解决问题。
与同伴交流编程心得，相互学习。
编程软件：如Python编程环境，用于演示和实践编程技术。
教学视频或动画：可能包含有关算法、程序设计、问题解决流程等内容的视频材料，帮助学生更好地理解抽象概念。

2.4.2 用流程图表示算法
美国国家标准化协会ANSI(American National Standard Institute)规定了一些 常用的流程图符号：
起止框
判断框
处理框
输入/输出框
注释框
流向线
连接点
例2.6 将求5!的算法用流程图表示
如果需要将最后结 果打印出来，可在 菱形框的下面加一 个输出框。
S6：如果i≤n-1，返回S3。否则打印 n “是素
实际上，n不必被2到(n-1)的整数除，只需 被2到n/2间整数除，甚至只需被2到 之n 间的 整数除即可。
2.3 算法的特性
一个算法应该具有以下特点： • 有穷性：包含有限的操作步骤。
• 确定性：算法中的每一个步骤都应当是确 定的。
• 有零个或多个输入：输入是指在执行算法 时需要从外界取得必要的信息。
第2章-算法概要
主要内容
2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法
2.1 算法的概念
广义地说，为解决一个问题而采取的方
法和步骤，就称为“算法”。
算法：
为了解决一个问题而采取的有限步骤。
计算机算法：
如何使计算机一步一步地工作的具体过程。
S7：deno=deno+1
S8：若deno≤100返回S4
反复执行S4到S8步骤，直到分母大于100为止。 一共执行了99次循环，向sum累加入了99个分数 。sum最后的值就是多项式的值。
例2.5 对一个大于或等于3的正整数，判断 它是不是一个素数。
概念：所谓素数，是指除了1和该数本身之外， 不能被其它任何整数整除的数。例如，13是 素数。因为它不能被2，3，4，…，12整除。

《计算机算法基础》教学大纲计算机算法基础教学大纲课程简介本课程作为计算机科学与技术专业必修课，旨在让学生掌握计算机算法的基础知识和基本应用，为后续深入研究算法提供基础。

教学目标通过本课程的研究，学生将能够：- 熟练掌握常用的计算机算法- 理解各种算法的基本思想和运行原理- 能够运用算法进行简单的问题求解和程序设计- 培养编写高效算法的能力教学内容第一章算法基础1.1 算法的定义和特性1.2 算法的分类1.3 时间复杂度和空间复杂度第二章常用算法2.1 排序算法（冒泡排序、快速排序、归并排序）2.2 查找算法（顺序查找、折半查找、哈希查找）2.3 图算法（最短路径算法、最小生成树算法）第三章算法应用3.1 算法在智能搜索、机器研究等领域的应用3.2 算法在计算机游戏、网络安全等领域的应用3.3 算法在大数据处理中的应用教学方法本课程采用讲授和实践相结合的教学方法。

教师将通过课堂讲解、板书演示、案例分析等方式向学生介绍算法基础原理和应用技巧，并通过实例编程和练巩固学生的实际应用能力。

考核方式本课程考核方式包括课堂作业、实验报告、期中考试和期末考试。

其中，期中考试占30%的成绩，期末考试占50%的成绩，课堂作业和实验报告占20%的成绩。

教材与参考书目教材《数据结构与算法分析》，作者：Mark Allen Weiss，出版社：机械工业出版社参考书目《算法导论》，作者：Thomas H. Cormen，出版社：机械工业出版社《算法设计与分析基础》，作者：Sun Limin，出版社：高等教育出版社实验环境本课程实验环境为Windows操作系统，使用Java语言进行编程实现。

教学进度。

“Hanoi 塔”问题演示 a 初始 a 步骤1 a
c
b
c
“Hanoi 塔”问题程序
void hanoi(int n,a,b,c)
{ if n == 1 move( 1, a, b );
else { hanoi( n-1, a, c, b );
move(n, a, b ); hanoi( n-1, c,b, a) ;
• 递归优点：结构清晰，可读性强
• 递归缺点：递归算法的运行效率较低，无论是耗 费的计算时间还是占用的存储空间都比非递归算 法要多。
整数划分问题的递归关系q(n,m)
如设p(n)为正整数n的划分数，则难以找到递归关系 • q(n,m):正整数n的不同的划分中，最大加数不 大于m的划分个数个数 q(n,m)=
1 q(n,n) 1+q(n,n-1) q(n,m-1)+q(n-m,m) n=1, m=1 n<m n=m n>m>1
递归函数举例(5)
学习要点
理解递归的概念。 掌握设计有效算法的分治策略。
通过典型范例，学习分治策略设计技巧。
2.1 递归的概念
• 递归算法：一个直接或间接地调用自身的算法 • 递归方程：对于递归算法，一般可把时间代 价表示为一个递归方程 • 递归函数：使用函数自身给出定义的函数 • 解递归方程最常用的方法是进行递归扩展
递归函数举例(1)
• 阶乘函数 n ！=
1 n(n-1)！ n=1 n>1
• Fibonacci数列
1 n=0
F(n)=
1 F(n-1)+F(n-2)
n=1 n>1
初始条件与递归方程是递归函数的二个要素