太原理工大学算法设计与分析实验报告

1 本科实验报告本科实验报告 课程名称 算法设计与分析 实验项目 分治法合并排序 贪心法作业调度 动态规划法求多段图问题 回溯法求 n 皇后问题 实验地点 致远楼 B503 专业班级 学号 学生姓名 指导教师 2017 年 3 月 18 日 2 实验实验 1 分治法合并排序分治法合并排序 一 实验目的一 实验目的 1 掌握合并排序的基本思想 2 掌握合并排序的实现方法 3 学会分析算法的时间复杂度 4 学会用分治法解决实际问题 二 实验内容二 实验内容 随机产生一个整型数组 然后用合并排序将该数组做升序排列 要求输出排序前和排序后 的数组 三 实验环境三 实验环境 Window10 惠普笔记本 Dev cpp 4 算法描述和程序代码算法描述和程序代码 include include include include using namespace std define random x rand x int a 10 合并排序函数 void Merge int left int mid int right int t 11 int i left j mid 1 k 0 while i mid else t k a j while i mid t k a i while j right t k a j for i 0 k left k right a k t i 分划函数 并且调用合并函数 void MergeSort int left int right if left right int mid left right 2 3 MergeSort left mid MergeSort mid 1 right Merge left mid right 调用合并函数 int main int i cout 排序前的数组为 for i 0 i 10 i a i random 100 调用 random 函数 产生 10 个 0 100 的随机数 cout a i cout endl MergeSort 0 9 cout 排序后的数组为 for i 0 i 10 i cout a i getchar return 0 五 实验结果截图五 实验结果截图 六 实验总结六 实验总结 通过编写这个程序 我进一步了解了分株算法的思想 在实际运用过程当中 尤其是在算 法编写方面相对来说比较简单 实现起来较为容易 4 实验实验 2 贪心法作业调度贪心法作业调度 一 实验目的一 实验目的 1 掌握贪心算法的基本思想 2 掌握贪心算法的典型问题求解 3 进一步多级调度的基本思想和算法设计方法 4 学会用贪心法分析和解决实际问题 二 实验内容二 实验内容 设计贪心算法实现作业调度 要求按作业调度顺序输出作业序列 如已知 n 8 效益 p 35 30 25 20 15 10 5 1 时间期限 d 4 2 4 5 6 4 5 7 求该条件下的最大效益 三 实验环境三 实验环境 Window10 惠普笔记本 Dev cpp 四 算法描述和程序代码四 算法描述和程序代码 include using namespace std const int Work 8 45 30 28 25 23 15 10 1 所有作业按收益从大到小排序 const int maxTime 8 4 7 3 2 4 6 7 5 class HomeWork private int res 8 bool flag 8 int maxReap public void dealWith 遍历所有作业 int i for i 0 i 0 j if flag j res j Work i 5 flag j true break cout 作业完成顺序为 for i 0 i 7 i cout res i t cout endl cout endl 最佳效益为 int j for j 0 j 7 j maxReap res j cout maxReap endl HomeWork int i for i 0 i2 个不相交的子集 Vi 1 i k 其中 V1 和 Vk 分别只有一个顶点 s 源 和一个顶点 t 汇 图中所有边 的始点和终点都在相邻的两个子集 Vi 和 Vi 1 中 求一条 s 到 t 的最短路线 参考课本 P124 图 7 1 中的多段图 试选择使用向前递推算法或向后递推算法求解多段图问题 三 实验环境三 实验环境 Window10 惠普笔记本 Dev cpp 四 算法描述和程序代码四 算法描述和程序代码 include int V 50 50 int a 50 b 20 int static k n m void createGraph int i j t s printf 请输入结点数 scanf d for i 0 i n i for j 0 j n j V i j 0 初始化 V i j 0 表示两结点没有边相连 printf 输入图的层数 scanf d printf 请输入每层的结点数的最大编号 a 0 0 for i 1 i k i scanf d printf 请输入边数 scanf d printf 请输入结点之间的关系 如 结点 i 和结点 j 的距离为 s 则输入 i j s n for t 1 t m t 7 scanf d d d V i j s int Backward 向后求解法 int i j t r for i a 1 1 i a 2 i 把第二层每个结点 i 与第一层结点 s 的边距赋值给 V i i V i i V 1 i for r 2 r k r 向后逐层求解 for i a r 1 1 i a r i 遍历第 r 层的每个结点 i 与第 r 1 层结点 j 之间的边 距 选择此刻最优解 for j a r 1 j a r 1 j if V i j 0 else if V i j 0 r for i a r 1 i a r 1 i if b r j break for j a r 1 1 j a r j if V i i V j i V j j b r j break return V n n int Forward 向前求解法 int i j t r 8 for i a k 2 1 i1 r 向前逐层求解 for j a r 1 1 j a r j 遍历第 r 层的每个结点 i 与第 r 1 层结点 j 之间的边距 选择此刻最优解 for i a r 2 1 i a r 1 i if V i j 0 else if V i j 0 for r 2 r k 1 r for i a r 2 1 i a r 1 i for j a r 1 1 j a r j if V i i V i j V j j b r j break i j r return V 1 1 int main int i j r sp createGraph b 1 1 b k n sp Forward sp Backward printf 最短路径长度为 d n sp printf 最短路径为 9 printf d b 1 for i 2 i d b i return 0 五 实验结果截图五 实验结果截图 6 实验总结实验总结 这个实验让我从中懂得了动态规划算法的核心 更加收敛的运用动态规划算法秋节各类问 题 但动态规划算法最重要的还是方程的选择 这个在实际运用中相当重要 10 实验实验 4 回溯法求回溯法求 n 皇后问题皇后问题 一 实验目的一 实验目的 1 掌握回溯算法的基本思想 2 通过 n 皇后问题求解熟悉回溯法 3 使用蒙特卡洛方法分析算法的复杂度 二 实验内容二 实验内容 要求在一个 8 8 的棋盘上放置 8 个皇后 使得它们彼此不受 攻击 两个皇后位于棋盘 上的同一行 同一列或同一对角线上 则称它们在互相攻击 现在要找出使得棋盘上 8 个 皇后互不攻击的布局 三 实验环境三 实验环境 Window10 惠普笔记本 Dev cpp 四 算法描述和程序代码四 算法描述和程序代码 include include using namespace std define N 8 int res 100 8 int countRes 0 bool Place int k int i int x for int j 0 j k j if x j i abs x j i abs j k return false return true void NQueen int k int n int x for int i 0 i n i if Place k i x x k i if k n 1 for i 0 i n i res countRes i x i cout x i t countRes cout endl else NQueen k 1 n x 11 void NQueen int n int x NQueen 0 n x int main int x N for int i 0 i N i x i 10 NQueen N x cout endl 共 countRes 种解 endl char show cout 是否显示图示 Y N show if show Y show y for int n 0 n countRes n cout