算法设计与分析 实验4

测试过程 实验中出现的问题 错误 解决方法 这是第一个实验中由于 i 这个变量没有在循环外定义导致的错误 经过改正后程序就能正 常运行了 改正前的程序如下 改正后的程序如下 实验总结 通过这个实验我对贪心算法有了一定的了解 但是还很是不熟悉 希望在后的学习中能 更深入的学习并掌握这个非常有用且好用的算法 签名 2012 年 11 月 21 日 评语与成绩 教师签名 年 月 日 洛阳师范学院信息技术学院 软件实验报告 专业 网络工程 课程 算法设计与分析 学号 姓名 班级 网络工程 实验名称实验三 贪心算法实例编程 实验类型实践课实验时间 2012 11 21 实验环境计算机一台 实验目的与要求 1 掌握贪心算法的基本思想 2 能够编写用贪心算法解决问题的程序 3 能对算法的复杂度 可靠性进行分析 实验内容 1 要求给出一种作业调度方案 使所给的 n 个作业在尽可能短的时间内由 m 台机 器加工处理完成 约定 每个作业均可在任何一台机器上加工处理 但未完工前不 允许中断处理 作业不能拆分成更小的子作业 输入 输入 第一行 m n 分别表示机器数和作业数 第二行 n 个整数 分别表示 n 个作业所需的加工时间 输出 输出 t 表示加工时间 提示 调度时间由 m 台机器中 加工时间最长的一个决 定 故贪心选择的一个原则应该是 尽可能均衡 m 台机器的负载 参考木桶原理 2 一辆汽车加满油后可以行驶 N 千米 旅途中有若干个加油站 若要使沿途的加 油次数最少 设计一个有效的算法 指出应在那些加油站停靠加油 并证明你的算 法能产生一个最优解 输入输入 第一行 n k 分别表示加满油后可行驶公里数和加油站个数 第二行 k 1 个整数 分别表示起点 k 个加油站 终点之间的距离 输出输出 加油次数 实验步骤 算法描述 源程序 操作步骤和方法 1 要求给出一种作业调度方案 使所给的 n 个作业在尽可能短的时间内由 m 台机 器加工处理完成 约定 每个作业均可在任何一台机器上加工处理 但未完工前不允 许中断处理 作业不能拆分成更小的子作业 输入 输入 第一行 m n 分别表示机器数和作业数 第二行 n 个整数 分别表示 n 个作业所需的加工时间 输出 输出 t 表示加工时间 提示 调度时间由 m 台机器中 加工时间最长的一个决定 故贪心选择的一个原则应该是 尽可能均衡 m 台机器的负载 参考木桶原理 实验程序如下 include include using namespace std typedef struct Job 作业 int ID int time Job typedef struct JobNode 作业链表的节点 int ID int time JobNode next JobNode pJobNode typedef struct Header 链表的表头 int s 处理机上的时间 JobNode next Header pHeader int main void QuickSort Job job int left int right 将 job 时间排序 void outSort Job job int n 输出排序 void display Header M int m 输出每个每台机器处理的 工作序号数 int SelectMin Header M int m 分配作业时选取机器函数 void solve Header head Job job int n int m 作业分配函数 int m n cout m Header head new Header m 动态构建数组结构体 用于记录 机器的作业时间 cout n Job job new Job n 动态构建作业的数组结构体 cout n 请按序号输入每个作业调度所需时间 time for int i 0 i job i time job i ID i QuickSort job 0 n 1 作业排序 outSort job n 输出排序 solve head job n m 作业分配 display head m 输出分配 cout endl endl return 0 int SelectMin Header M int m 选择 s 最小的机器序号 k int k 0 for int i 1 i m i if M i smiddle while job j timeleft j if i j itemp job j job j job i job i itemp i j while i j if lefti QuickSort job i right void display Header M int m 作业分配输出函数 JobNode p for int i 0 i m i cout n 第 i 台机器上处理的工作序号 if M i next 0 continue p M i next do cout ID next while p 0 void outSort Job job int n 作业时间由大到小排序后输出函数 cout n 按工作时间由大到小为 n 时间 t for int i 0 i n i cout setw 4 job i time cout n 序号 t for int i 0 i n i cout setw 4 job i ID void solve Header head Job job int n int m 作业分配函数 int k i for int i 0 i m jobnode ID job i ID jobnode next 0 head i s jobnode time head i next jobnode if i m n m 的情况续处理 for int i im for int i itime job i time jobnode ID job i ID jobnode next 0 k SelectMin head m p head k next head k s jobnode time while p next 0 p p next p next jobnode 2 一辆汽车加满油后可以行驶 N 千米 旅途中有若干个加油站 若要使沿途的加 油次数最少 设计一个有效的算法 指出应在那些加油站停靠加油 并证明你的算法 能产生一个最优解 输入输入 第一行 n k 分别表示加满油后可行驶公里数和加油站个数 第二行 k 1 个整数 分别表示起点 k 个加油站 终点之间的距离 输出输出 加油次数 实验程序如下 include define N 1000 using namespace std int greedy int d int n int k int num 0 int i 0 int s 0 for i 0 i n printf no solution n return 0 for i 0 s 0 i n num s d i printf d n num cin num return 1 int main int i n k int d N printf 请输入汽车可行驶 n cout 请输入汽车可