算法课程设计报告--算法设计与分析

《算法课程设计报告--算法设计与分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计报告课程设计名称：算法设计与分析系别：三系学生姓名：李亚颂班级：09软件（1）学号：20090307130成绩：指导教师：秦川开课时间：2011-2012学年上学期2121目录1课程设计概述51.1课程设计目的51.2课程设计要求51.3课程设计题目52运用贪心算法实现普通背包问题62.1问题描述62.2问题分析62.3算法设计62.3.1贪心算法基本思想62.3.2数据结构说明72.3.3算法描述72.4算法实现72.5测试分析102.5.1运行测试102.5.2时间复杂度分析123运用分治算法实现棋盘覆盖问题133.1问题描述133.2问题分析133.3算法设计143.

2、3.1分治算法基本思想143.3.2问题分解143.3.3棋盘的识别153.3.4数据结构设计153.3.5算法描述163.4算法实现173.5测试分析203.5.1运行测试20213.5.2时间复杂度分析214课程设计总结215参考文献21211课程设计概述1.1课程设计目的1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2．初步掌握软件开发过程的问题分析、算法设计、程序编码、测试等基本方法和技能；3．提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4．训练用系统的观点和软件开发一般规范进行软件开发。1.2课程设计要求1．学生必须认真主动完成课设的

3、要求。有问题及时主动通过各种方式与教师联系沟通。2．学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。3．课程设计按照教学要求需要1.5周时间完成，1.5周中每天教师安排上机时间学生不得缺席。1.3课程设计题目1.普通背包问题要求：使用贪心算法实现；2.棋盘覆盖问题要求：使用分治算法实现；212运用贪心算法实现普通背包问题2.1问题描述有一个背包容量为M，输入n个物品。已知n个物体重量为：w1、w2…n个物体价值为：p1、p2…物体i可以部分的装入背包，若物体i的一部分xi装入背包，则装入的重量为wi*xi，装入

4、的价值为pi*xi。求选择放入的物品，不超过背包的容量，且得到的收益最好。2.2问题分析1.按单位物品价值递增将物品排序；2.依次将单位价值大的物品放入背包（贪心选择），直到背包放满位置；3.如果正在考虑装入的物品不能全部放进去，则可以将部分物品放入背包。2.3算法设计2.3.1贪心算法基本思想从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策,尽可能地求得当前最优的解，当达到算法中某一步不需要再继续前进时，算法停止。贪心算法原理是通过局部最优来达到全局最优,采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的（在一定的标准下），决策一旦做出，就不可再

5、更改。212.3.2数据结构说明定义物品信息结构，如下所示。structGoodInfo{floatP;//物品价值floatW;//物品重量floatX;//物品该放的数量intFlag;//物品编号};//物品信息结构体2.3.3算法描述voidgreedy_knapsack(GoodInfogoods[],floatM,intn){floatmm=M;//mm背包剩余载重inti,j;for(i=1;i<=n;i++)goods[i].X=0;//初始化for(i=1;i<=n;i++){if(goods[i].W>mm)//当该物品重量大于时剩余容量跳出break;good

6、s[i].X=1;mm=mm-goods[i].W;//确定背包新的剩余容量}if(i<=n)goods[i].X=mm/goods[i].W;｝2.4算法实现#include#includestructGoodInfo{floatP;//物品价值floatW;//物品重量floatX;//物品该放的数量intFlag;//物品编号};//物品信息结构体//插入排序，按pi/wi价值收益进行排序voidInsertionsort(GoodInfogoods[],intn)21{intj,i;for(j=2;j<=n;j++){goods

7、[0]=goods[j];i=j-1;while(goods[0].P>goods[i].P){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}}voidgreedy_knapsack(GoodInfogoods[],floatM,intn){floatmm=M;//mm背包剩余载重inti,j;for(i=1;i<=n;i++)goods[i].X=0;for(i=1;i<=n;i++){if(goods[i].W>mm)