《算法分析与设计》课程实验教学大纲 《Analysis&Design of Algorithm》)Exper iment Outline 一、课程基本信息 课程代码：16158603 课程名称：算法分析与设计 英文名称：Analysis&Design of Algorithm 实验总学时：12 适用专业：计算机科学与技术专业本科生 课程类别：专业课 先修课程：C或JAVA语言、数据结构 二、实验教学的总体目的和要求 1、对学生的要求 ()准备好上机所需的程序 (②)上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的 问题，最好独立解决。 (3)上机结束后，要求整理出实验报告的实验项目，须在规定时间内完成并上交。 实验报告应包括：题目、实验环境、算法描述、程序实现、运行结果、对运行情 况所作时间复杂性等的分析。 2、对教师的要求 教师要向学生明确每次实验任务。在实验过程中，原则上以学生思考、学生相互 讨论为主，反映比较普遍的问题，应给予统一的解答。对程序调试过程中，学生 反映的问题，可及时给予释疑。 教师应当配合实验室管理人员，保证实验设备和软件环境的正常工作状态， 3、对实验条件的要求 保证一人一台计算机、安装C语言或C+语言环境、能够访问互联网
《算法分析与设计》课程实验教学大纲 《Analysis & Design of Algorithm》Experiment Outline 一、课程基本信息 课程代码： 16158603 课程名称：算法分析与设计 英文名称: Analysis & Design of Algorithm 实验总学时：12 适用专业：计算机科学与技术专业本科生 课程类别：专业课 先修课程：C 或 JAVA 语言、数据结构 二、实验教学的总体目的和要求 1、对学生的要求 (1) 准备好上机所需的程序。 (2) 上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的 问题，最好独立解决。 (3) 上机结束后，要求整理出实验报告的实验项目，须在规定时间内完成并上交。 实验报告应包括：题目、实验环境、算法描述、程序实现、运行结果、对运行情 况所作时间复杂性等的分析。 2、对教师的要求 教师要向学生明确每次实验任务。在实验过程中，原则上以学生思考、学生相互 讨论为主，反映比较普遍的问题，应给予统一的解答。对程序调试过程中，学生 反映的问题，可及时给予释疑。 教师应当配合实验室管理人员，保证实验设备和软件环境的正常工作状态。 3、对实验条件的要求 保证一人一台计算机、安装 C 语言或 C++语言环境、能够访问互联网
三、实验教学内容 实验项目一：递归程序实现 实验名称：数字计数问题 问题定义 一本书的页码从自然数1开始顺序编码到N。页码按照通常的习惯编 排，即每个页码不能含多余的前倒数0，例如，、第6页的页码为6，不能是06、 006等。数字计数问题要求从键盘输入页数N,输出全书页码中分别用到0、1、 2、3、4、5、6、7、8、9的次数： 实验内容：设计求解“数字计数问题”的算法，分析时间复杂性，并用C或C+ 语言编程实现，调试通过，得出正确答案。 实验性质：设计型 实验学时：2 实验目的与要求：掌握递归算法的概念和基本思想，分析并掌握“数字计数”问 题的递归算法：掌握CC+语言的基本库函数： 实验条件：C或C+,互联网络环境 研究与思考：分析算法时间复杂性，能否将递归程序非递归化？ 实验项目二：递归与分治策略 实验名称：棋盘覆盖问题 问题定义：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同， 称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图 示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方 格，且任何2个L型骨牌不得重叠覆盖 实验内容：设计求解“棋盘覆盖问题”的算法，分析时间复杂性，并用C或C+ 语言编程实现，调试通过，得出正确答案。 实验性质：设计型 实验学时：2 实验目的与要求：进一步熟悉CC+语言的集成开发环境：通过本实验加深对递 归与分治策略的理解和运用： 实验条件：C或C+,互联网络环境
三、实验教学内容 实验项目一：递归程序实现 实验名称：数字计数问题 问题定义：一本书的页码从自然数 1 开始顺序编码到 N。页码按照通常的习惯编 排，即每个页码不能含多余的前倒数 0，例如，、第 6 页的页码为 6，不能是 06、 006 等。数字计数问题要求从键盘输入页数 N，输出全书页码中分别用到 0、1、 2、3、4、5、6、7、8、9 的次数； 实验内容：设计求解“数字计数问题”的算法，分析时间复杂性，并用 C 或 C++ 语言编程实现，调试通过，得出正确答案。 实验性质：设计型 实验学时：2 实验目的与要求：掌握递归算法的概念和基本思想，分析并掌握“数字计数”问 题的递归算法；掌握 C/C++语言的基本库函数； 实验条件：C 或 C++，互联网络环境 研究与思考：分析算法时间复杂性，能否将递归程序非递归化？ 实验项目二：递归与分治策略 实验名称：棋盘覆盖问题 问题定义：在一个 2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同， 称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图 示的 4 种不同形态的 L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方 格，且任何 2 个 L 型骨牌不得重叠覆盖； 实验内容：设计求解“棋盘覆盖问题”的算法，分析时间复杂性，并用 C 或 C++ 语言编程实现，调试通过，得出正确答案。 实验性质：设计型 实验学时：2 实验目的与要求：进一步熟悉 C/C++语言的集成开发环境；通过本实验加深对递 归与分治策略的理解和运用； 实验条件：C 或 C++，互联网络环境
研究与思考：分析算法的时间复杂性，分析思考子问题相互独立在“棋盘覆盖问 题”的具体体现。 在讲解这个实验过程中，介绍目前以A缸和大数据为主要代表的第四次工业 革命前景和现状，进一步认识邓小平提出的重要诊断： “科学是第一生产力”。 实验项目三：动态规划算法(1) 实验名称：最长公共子序列 问题定义：已知两个串X和Y,求最长公共子序列。（详见教材） 实验内容：分析并掌握“最长公共子序列”问题的动态规划算法求解方法，并 用C或C+语言编程实现，调试通过，得出正确答案。 实验性质：设计型 实验学时：2 实验目的与要求：通过动态规划算法的示例程序理解动态规划算法的基本思想： 运用动态规划算法解决实际问题加深对动态规划算法的理解和运用： 实验条件：C或C+,互联网络环境 研究与思考：分析LCS的算法时间复杂性，思考其最优子结构和递推方程式。 在讲解这个实验过程中，简要介绍生物信息学这个本世纪的新兴学科，从而更 深入地认识“生物、医药、数学、化学 理手段、计算机算法技术、存储技 术等等”的大融合，大统一，进而推动技术的更高层面的发展。 实验项目四：动态规划算法(2) 实验名称：最大子段和问题 问题定义：己知串X,求X的最大子段和（详见教材）。 实验内容：设计求解“最大子段和”的算法，并用C或C+语言编程实现，调试 通过，得出正确答案。 实验性质：设计型 实验学时：2 实验目的与要求：通过动态规划算法的示例程序理解动态规划算法的基本思想： 运用动态规划算法解决实际问题加深对动态规划算法的理解和运用：
研究与思考：分析算法的时间复杂性，分析思考子问题相互独立在“棋盘覆盖问 题”的具体体现。 在讲解这个实验过程中，介绍目前以 AI 和大数据为主要代表的第四次工业 革命前景和现状，进一步认识邓小平提出的重要诊断：“科学是第一生产力”。 实验项目三：动态规划算法(1) 实验名称：最长公共子序列 问题定义： 已知两个串 X 和 Y，求最长公共子序列。(详见教材) 实验内容：分析并掌握“最长公共子序列” 问题的动态规划算法求解方法，并 用 C 或 C++语言编程实现，调试通过，得出正确答案。 实验性质：设计型 实验学时：2 实验目的与要求：通过动态规划算法的示例程序理解动态规划算法的基本思想； 运用动态规划算法解决实际问题加深对动态规划算法的理解和运用； 实验条件：C 或 C++，互联网络环境 研究与思考：分析 LCS 的算法时间复杂性，思考其最优子结构和递推方程式。 在讲解这个实验过程中，简要介绍生物信息学这个本世纪的新兴学科，从而更 深入地认识“生物、医药、数学、化学、物理手段、计算机算法技术、存储技 术等等”的大融合，大统一，进而推动技术的更高层面的发展。 实验项目四：动态规划算法(2) 实验名称： 最大子段和问题 问题定义： 已知串 X，求 X 的最大子段和（详见教材）。 实验内容：设计求解“最大子段和”的算法，并用 C 或 C++语言编程实现，调试 通过，得出正确答案。 实验性质：设计型 实验学时：2 实验目的与要求：通过动态规划算法的示例程序理解动态规划算法的基本思想； 运用动态规划算法解决实际问题加深对动态规划算法的理解和运用；
实验条件：C或C+,互联网络环境 研究与思考：分析最大子段和问题的算法时间复杂性，思考其最优子结构和递推 方程式。 实验项目五：贪心算法 实验名称：会场安排问题 问题定义：假设在足够多的会场里安排一批活动(N个活动)，每个活动事先给 定活动的开始时间和结束时间，试用贪心算法求出最少需要多少会场，并求出每 个活动安排在第几个会场， 实验内容： 掌握贪心算法的概念和基本思想，分析并掌握“会场安排”问题的贪 心算法：掌握CC+语言的基本库函数： 实验性质：设计型 实验学时：2 实验目的与要求：通过贪心算法的示例程序理解贪心算法的基本思想：运用贪心 算法解决实际问题加深对贪心算法的理解和运用： 实验条件：C或C+,互联网络环境 研究与思考：分析程序的算法时间复杂性，理解该问题的贪心选择性质和最优子 结构性质。 在讲解这个实验过程中，融合“从实际出发”的唯物论，从而在算法设计过程 中，要善于针对问题的特殊性，找到突破口，设计出更高效的算法。 实验项目六：回溯法 实验名称：01背包问题 问题定义： 已知i种物品的重量i和价值vi,背包的容重W,求价值最大的物 品装包方案（任一物品不能选择部分入包，即物品j要么全部装包，要么不装包）。 实验内容：设计求解“0-1背包问题”的算法，并用C或C+语言编程实现，调 试通过，得出正确答案。 实哈性质：设计型 实验学时：2 实验目的与要求：通过回溯法的示例程序理解回溯法的基本思想：运用回溯法解 决实际问题进一步加深对回溯法的理解和运用：
实验条件：C 或 C++，互联网络环境 研究与思考：分析最大子段和问题的算法时间复杂性，思考其最优子结构和递推 方程式。 实验项目五： 贪心算法 实验名称： 会场安排问题 问题定义： 假设在足够多的会场里安排一批活动（N 个活动），每个活动事先给 定活动的开始时间和结束时间，试用贪心算法求出最少需要多少会场，并求出每 个活动安排在第几个会场； 实验内容：掌握贪心算法的概念和基本思想，分析并掌握“会场安排”问题的贪 心算法；掌握 C/C++语言的基本库函数； 实验性质：设计型 实验学时：2 实验目的与要求：通过贪心算法的示例程序理解贪心算法的基本思想；运用贪心 算法解决实际问题加深对贪心算法的理解和运用； 实验条件：C 或 C++，互联网络环境 研究与思考：分析程序的算法时间复杂性，理解该问题的贪心选择性质和最优子 结构性质。 在讲解这个实验过程中，融合“从实际出发”的唯物论，从而在算法设计过程 中，要善于针对问题的特殊性，找到突破口，设计出更高效的算法。 实验项目六： 回溯法 实验名称： 0-1 背包问题 问题定义： 已知 i 种物品的重量 wi 和价值 vi，背包的容重 W，求价值最大的物 品装包方案（任一物品不能选择部分入包，即物品 j 要么全部装包，要么不装包）。 实验内容：设计求解“0-1 背包问题”的算法，并用 C 或 C++语言编程实现，调 试通过，得出正确答案。 实验性质：设计型 实验学时：2 实验目的与要求：通过回溯法的示例程序理解回溯法的基本思想；运用回溯法解 决实际问题进一步加深对回溯法的理解和运用；
实验条件：C或C+,互联网络环境 研究与思考：分析程序的算法时间复杂性，该问题的回溯法求解，当问题规模足 够大时，是否可行？为什么？ 在讲解这个实验过程中，要通过该问题的多种算法的设计与实现(BF算法、分 治算法、D算法)，强调马克思主义哲学的方法论，使得我们在思考问题的求 解方法时，能够一切从实际出发，理论联系实际。 四、考核方式 共6个实验，须交6个问题的求解算法，占平时成绩的15% 交两份实验报告，给予评分，作为平时成绩的一部分，占平时成绩的5% 五、推荐实验教材和教学参考书 实验教材：《算法设计与实验题解》，王晓东编著，电子工业出版社，2007-05 参考书：《算法设计与分析》，吕国英编著，清华大学出版社，2006.3(1) 六、其他需说明的（黑体/小四） 大纲修订人：李绍华 修订日期：2020/12/01 大纲审定人：许波 审定日期：2022年1月
实验条件：C 或 C++，互联网络环境 研究与思考：分析程序的算法时间复杂性，该问题的回溯法求解，当问题规模足 够大时，是否可行？为什么？ 在讲解这个实验过程中，要通过该问题的多种算法的设计与实现（BF 算法、分 治算法、DP 算法），强调马克思主义哲学的方法论，使得我们在思考问题的求 解方法时，能够一切从实际出发，理论联系实际。 四、考核方式 共 6 个实验，须交 6 个问题的求解算法，占平时成绩的 15% 交两份实验报告，给予评分，作为平时成绩的一部分，占平时成绩的 5% 五、推荐实验教材和教学参考书 实验教材：《算法设计与实验题解》，王晓东 编著，电子工业出版社，2007-05 参考书：《算法设计与分析》，吕国英 编著，清华大学出版社，2006.3(1) 六、其他需说明的（黑体／小四） 大纲修订人： 李绍华 修订日期：2020/12/01 大纲审定人： 许波 审定日期：2022 年 1 月