算法设计与分析实验(第2、3章)

暨南大学本科实验报告专用纸暨南大学本科实验报告专用纸 课程名称 算法设计与分析 成绩评定 实验项目名称 分治策略与动态规划 指导教师 李展 实验项目编号 01 实验项目类型 设计类 实验地点 南海楼 6 楼 学生姓名 陈奕豪 学号 2012051351 学院 信息科学技术学院 系 计算机系 专业 软件工程 实验时间 年 月 日 一 一 实验目的 实验目的 本实验涉及用分治策略和动态规划算法来求解优化组合问题 通过上机实 验使学员学会程序的录入和调试 通过实验结果的比较 使学员了解两种算法 的主要特点 二 二 实验内容 实验内容 第二章实验题第二章实验题 必做必做 算法分析题算法分析题 1 1 线性时间选择问题线性时间选择问题 问题描述 给定线性序集中 n 个元素和一个整数 k 1 k n 要求找出这 n 个 元素中第 k 小的元素 主要思路及步骤 1 把 a 数组中元素分为 5 个一组 选每组中位数后分别将他们移向 数组头 再用同样的方法选取中位数的中位数 x 然后按 x 把 a 数 组分为两个划分 重复上述过程直至划分中元素个数少于 75 返 回要求值 算法描述 精品文档 2欢迎下载 Type Select Type a int p int r int k if r p 75 用某个简单排序算法对数组 a p r 排序 return a p k 1 for int i 0 i r p 4 5 i 将 a p 5 i 至 a p 5 i 4 的第 3 小元素 与 a p i 交换位置 找中位数的中位数 r p 4 即上面所说的 n 5 Type x Select a p p r p 4 5 r p 6 10 int i Partition a p r x j i p 1 if k j return Select a p i k else return Select a i 1 r k j 输入和输出 自行设计数组 a 的元素的值 要求元素个数不少于 80 个 并实现以下输出 1 输出数组 a 中下标范围从 p 到 p r p 4 5 的元素 2 输出 x 的值 判断 x 是否为数组 a 中下标范围从 p 到 p r p 4 5 的拟中 位数 3 输出数组 a 中下标范围从 p 到 r 的元素 验证其是否为以 x 为基准元素的 划分 源代码 include include include void Swap int i int j int a a i 精品文档 3欢迎下载 i j j a 交换函数交换函数 int Partition int a int p int r int i p j r 1 int x a p while true while a i x if i j break Swap a p a j a j x return j void QuickSort int a int p int r if p r int q Partition a p r QuickSort a p q 1 QuickSort a q 1 r 快速排列 int Partition S int a int p int r int x int count int i j p temp z 0 for i 0 i r i if a i x z else temp a z a z a j a j temp 精品文档 4欢迎下载 j z count i p j r 1 while true while a i x if i j break Swap a p a j a j x return j 划分函数划分函数 int Select int a int p int r int k if r p 75 QuickSort a p r return a p k 1 int i j t for i 0 i r p 4 5 i QuickSort a p 5 i p 5 i 4 int temp a p i a p i a p i 5 2 a p i 5 2 temp printf 数组 a 下标 p 到 p r p 4 5 的元素 for i p i p r p 4 5 i printf d a i 输出输出 1 1 int x Select a p p r p 4 5 r p 6 10 printf n 拟中位数 d n x 输出输出 2 2 精品文档 5欢迎下载 int count 0 i Partition S a p r x printf 以 d 为基准的划分 x for t p t r t printf d a t 输出输出 3 3 printf n n j i p if k 1 elsereturn Select a i count r k j count int main int i n j int a 80 1059 1285 50 32 788 651 106 42 67 7 1287 395 412 132 213 398 1750 406 1834 703 210 1102 1210 1092 161 1736 578 965 1037 881 1754 813 268 558 1961 1271 776 146 544 1921 514 1049 636 1275 1415 1294 929 765 472 187 1575 194 1342 1309 1026 1836 502 1412 289 161 137 1943 367 1163 1047 896 132 1375 428 655 94 111 636 103 1018 1099 479 465 346 1720 printf 输入 k 的值 scanf d int z n i Select a 0 79 n QuickSort a 0 79 排序排序 方便查看结果方便查看结果 for j 0 j 80 j printf d a j printf n printf 第 d 小的数是 d n z i return 0 实验截图 精品文档 6欢迎下载 实验总结 基本熟悉线性时间选择算法的结构 第三章实验题第三章实验题 选做选做 算法实现题算法实现题 2 2 二维二维 0 10 1 背包问题 背包问题 P79P79 3 43 4 问题描述 分析与解答 要求 给出最优值的递归关系 算法描述 输入和输出 要求 物品不少于 10 个 输出最优值数组的全部值和最后的最优解 算法实现 include int m 100 100 100 int min int i int j 精品文档 7欢迎下载 return ij i j void Knapsack int v int w int c int b int d int n int min int i int j int max int i int j int i j k int jMax min w n 1 c 可选物品只有 n int kMax min b n 1 d 同上 for j 0 j jMax j for k kMax k d k m n j k 0 可选物品只有 n 且重量不足 for j jMax j c j for k 0 k kMax k m n j k 0 可选物品只有 n 且体积不足 for j w n j c j 精品文档 8欢迎下载 for k b n k1 i jMax min w i 1 c kMax min b i 1 d for j 0 j jMax j for k 0 k d k m i j k m i 1 j k for j 0 j c j for k 0 k kMax k m i j k m i 1 j k for j w i j c j for k b i k w 1 精品文档 9欢迎下载 void Traceback int w int c int b int d int n int x for int i 1 i n i if m i c d m i 1 c d x i 0 else x i 1 c w i d b i x n m n c d 1 0 int main int n c d i printf 请输入物品个数 背包容量 背包容积 scanf d d d int v 100 w 100 b 100 x 100 精品文档 10欢迎下载 printf 请输入每个物品的价值 重量 体积 n for i 1 i n i scanf d d d Knapsack v w c b d n Traceback w c b d n