《《算法设计与分析》实验指导书》由会员分享，可在线阅读，更多相关《《算法设计与分析》实验指导书（19页珍藏版）》请在金锄头文库上搜索。
1、 算法设计与分析 实验指导书 本书是为配合 算法分析与设计实践教学大纲 而编写的上机指 导 其目的是使学生消化理论知识 加深对讲授容的理解 尤其是一 些算法的实现及其应用 培养学生独立编程和调试程序的能力 使学 生对算法的分析与设计有更深刻的认识 上机实验一般应包括以下几个步骤 1 准备好上机所需的程序 手编程序应书写整齐 并经人工检查 无误后才能上机 2 上机输入和调试自己所编的程序 一人一组 独立上机调试 上机时出现的问题 最好独立解决 3 上机结束后 整理出实验报告 实验报告应包括 题目 程序 清单 运行结果 对运行情况所作的分析 目录 实验一统计数字及字符编码 2 学时 1 实验二蛮力
2、法 2 学时 3 实验三递归与分治法 2 学时 5 实验四贪心算法 2 学时 8 实验五回溯算法 2 学时 10 实验六分支限界法 2 学时 12 实验七动态规划算法 3 学时 15 实验一统计数字及字符编码 2 学时 一 实验目的与要求 1 掌握算法的计算复杂性概念 2 掌握算法渐近复杂性的数学表述 3 掌握用C 语言描述算法的方法 4实现具体的编程与上机实验验证算法的时间复杂性函数 二 实验容 1 统计数字问题 1 问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n 书的页码按照通常的习惯编 排 每个页码都不含多余的前导数字0 例如 第6 页用数字6 表示而不是06 或 006 等
3、 数字计数问题要求对给定书的总页码n计算出书的全部页码中分别用到多少次数 字 0 1 2 9 2 编程任务 给定表示书的总页码的10 进制整数n 1 n 109 编程计算书的全部页码中分 别用到多少次数字0 1 2 9 3 程序算法 将页码数除以10 得到一个整数商和余数 商就代表页码数减余数外有多少个1 9 作为个位数 余数代表有1 余数本身这么多个数作为剩余的个位数 此外 商还 代表 1 商本身这些数出现了10 次 余数还代表剩余的没有计算的商的大小的数的个 数 把这些结果统计起来即可 2 字典序问题 1 问题描述 在数据加密和数据压缩中常需要对特殊的字符串进行编码 给定的字母表A 由 2
4、6 个小 写英文字母组成A a b z 该字母表产生的升序字符串是指字符串中字母按照从左到右 出现的次序与字母在字母表中出现的次序相同 且每个字符最多出现1 次 例如 a b ab bc xyz 等字符串都是升序字符串 现在对字母表A 产生的所有长度不超过6 的升序 字符串按照字典序排列并编码如下 1 2 26 27 28 a b z ab ac 对于任意长度不超过6 的升序字符串 迅速计算出它在上述字典中的编码 算法设计 对于给定的长度不超过6 的升序字符串 计算出它在上述字典中的编码 数据输入 输入数据由文件名为input txt 的文本文件提供 文件的第一行是一个正整数 k 表示接下来共
5、有k 行 接下来的k 行中 每行给出一个字符串 结果输出 将计算结果输出到文件output txt 中 文件共有k 行 每行对应于一个字符 串的编码 实验二蛮力法 2 学时 一 实验目的与要求 1 掌握蛮力法的基本思想 2 使用蛮力法解决具体问题 通常 问题规模比较小时 此方法才有意义 二 实验容 1 用 C C 编写程序实现BF 算法 进行模式匹配 以下是该算法的伪代码 请进行调试 int BF char S char T i 0 j 0 while i strlen S else return 0 2 用 C C 编写程序实现KMP 算法 进行模式匹配 求模式串 T 的 Next 数组 v
6、oid GetNext char T int next next 1 0 j 1 k 0 while j T 0 if k 0 T j T k j k next j k else k next k KMP 算法伪代码 1 在串 S和串 T 中分别设比较的起始下标i 和 j 2 循环直到S 中所剩字符长度小于T 的长度或T 中所有字符均比较完毕 2 1 如果 S i T j 则继续比较S和 T 的下一个字符 否则 2 2 将 j 向右滑动到next j 位置 即j next j 2 3 如果 j 0 则将 ii 1 j 1 准备下一趟比较 3 如果 T 中所有字符均比较完毕 则返回匹配的起始下标
7、 否则返回0 3 以源串 ababcabccabccacbab 和模式串 abccac w 为例 编写程序 给出采用BF 算 法和 KMP 算法进行串匹配过程中的字符比较次数 实验三递归与分治法 2 学时 基本题一 基本递归算法 一 实验目的与要求 1 熟悉 C C 语言的集成开发环境 2 通过本实验加深对递归过程的理解 二 实验容 掌握递归算法的概念和基本思想 分析并掌握 整数划分 问题的递归算法 三 实验题 任意输入一个整数 输出结果能够用递归方法实现整数的划分 四 实验步骤 1 理解算法思想和问题要求 2 编程实现题目要求 3 上机输入和调试自己所编的程序 4 验证分析实验结果 5 整理
8、出实验报告 基本题二 棋盘覆盖问题 一 实验目的与要求 1 掌握棋盘覆盖问题的算法 2 初步掌握分治算法 二 实验题 盘覆盖问题 在一个2k 2k个方格组成的棋盘中 恰有一个方格与其它方格不同 称该 方格为一特殊方格 且称该棋盘为一特殊棋盘 在棋盘覆盖问题中 要用图示的4 种不同形 态的 L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格 且任何2 个 L 型骨牌不 得重叠覆盖 三 实验提示 void chessBoard int tr int tc int dr int dc int size if size 1 return int t tile L 型骨牌号 s size 2 分割棋
9、盘 覆盖左上角子棋盘 if dr tr s else 此棋盘中无特殊方格 用 t 号 L 型骨牌覆盖右下角 board tr s 1 tc s 1 t 覆盖其余方格 chessBoard tr tc tr s 1 tc s 1 s 覆盖右上角子棋盘 if dr tc s 特殊方格在此棋盘中 chessBoard tr tc s dr dc s else 此棋盘中无特殊方格 用 t 号 L 型骨牌覆盖左下角 board tr s 1 tc s t 覆盖其余方格 chessBoard tr tc s tr s 1 tc s s 覆盖左下角子棋盘 if dr tr s else 用 t 号 L 型骨
10、牌覆盖左上角 board tr s tc s t 覆盖其余方格 chessBoard tr s tc s tr s tc s s 提高题一 二分搜索 一 实验目的与要求 1 熟悉二分搜索算法 2 初步掌握分治算法 二 实验题 1 设 a 0 n 1 是一个已排好序的数组 请改写二分搜索算法 使得当搜索元素x 不在数组中 时 返回小于x 的最大元素的位置I 和大于 x 的最小元素位置j 当搜索元素在数组中时 I 和 j 相同 均为x 在数组中的位置 2 设有 n 个不同的整数排好序后存放于t 0 n 1 中 若存在一个下标I 0 i n 使得 t i i 设计一个有效的算法找到这个下标 要求算法
11、在最坏的情况下的计算时间为O logn 三 实验提示 1 用 I j 做参数 且采用传递引用或指针的形式带回值 bool BinarySearch int a int n int x int int right n 1 while lefta mid left mid 1 else right mid 1 i right j left return false int SearchTag int a int n int x int left 0 int right n 1 while lefta mid right mid 1 else left mid 1 return 1 提高题二 用分治
12、法实现元素选择 一 实验要求与目的 1 了解分治法的基本思想 掌握递归程序编写方法 2 使用分治法编程 求解线形序列中第k 小元素 二 实验容 1 给定线形序列集中n 个元素和一个整数k 1 k n 输出这 n 个元素中第k 小元素的值 及其位置 2 简述该算法的原理 步骤 对该算法与直接排序查找进行比较 3 编写并调试程序 测试要求 元素个数不少于100 分三种情况 k 1 k n 和 k 中位数 实验四贪心算法 2 学时 基本题一 多机调度问题 一 实验目的与要求 1 熟悉多机调度问题的算法 2 初步掌握贪心算法 二 实验题 要求给出一种作业调度方案 使所给的n 个作业在尽可能短的时间由m
13、 台机器加工处理 完成 约定 每个作业均可在任何一台机器上加工处理 但未完工前不允许中断处理 作业 不能拆分成更小的子作业 三 实验提示 1 把作业按加工所用的时间从大到小排序 2 如果作业数目比机器的数目少或相等 则直接把作业分配下去 3 如果作业数目比机器的数目多 则每台机器上先分配一个作业 如下的作业分配时 是 选那个表头上s 最小的链表加入新作业 typedef struct Job int ID 作业号 int time 作业所花费的时间 Job typedef struct JobNode 作业链表的节点 int ID int time JobNode next JobNode p
14、JobNode typedef struct Header 链表的表头 int s pJobNode next Header pHeader int SelectMin Header M int m int k 0 for int i 1 i m i if M i shalf t t 1 2 count half return if t n sum else for int i 0 i 2 i p 1 t i count i for int j 2 j t j p j t j 1 p j 1 t j 1 p j 1 t j 2 count p j t j 1 Backtrack t 1 for
15、 int j 2 j t j count p j t j 1 count i 基本题二 0 1 背包问题 一 实验目的与要求 1 掌握 0 1 背包问题的回溯算法 2 进一步掌握回溯算法 二 实验题 给定 n 种物品和一背包 物品i 的重量是wi 其价值为vi 背包的容量为C 问应如何选择 装入背包的物品 使得装入背包中物品的总价值最大 三 实验提示 template Typep Knap Bound int i 计算上界 Typew cleft c cw 剩余容量 Typep b cp 以物品单位重量价值递减序装入物品 while i n b p i i 装满背包 if i H 1000 T
16、 MinOut new T n 1 计算 MinOut 离开顶点i 的最小耗费边的耗费 T MinSum 0 离开顶点i 的最小耗费边的数目 for int i 1 i n i T Min NoEdge for int j 1 j n j if a j NoEdge if Min NoEdge return NoEdge 此路不通 MinOut Min MinSum Min 把 E 节点初始化为树根 MinHeapNode E E x new int n for i 0 i n i E x i 1 E s 0 局部旅行路径为x 1 0 E cc 0 其耗费为0 E rcost MinSum T bestc NoEdge 目前没有找到旅行路径 搜索排列树 while E s n 1 不是叶子 if E s n 2 叶子的父节点 通过添加两条边来完成旅行 检查新的旅行路径是不是更好 if a E x n 2 E x n 1 NoEdge E cc bestc E lcost bestc E s H I n s e r t E else delete E x else 产生孩子 for in
