- 1、本文档共11页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法与数据结构
课程设计实验报告书
课程设计名称:最小套圈设计
学 生 姓 名:张延云
学 号:201058501314
学 院:计算机学院
班 级:计101-3班
日 期:2012年7月13日
一、问题分析和任务定义
1、问题分析
本设计的要求是设计一个最小套圈。
规则是:游戏者将手中的圆环套圈投向场中的玩具,被套中的玩具就作为奖品奖给游戏者。
给定一个套圈游戏场中的布局,固定每个玩具的位置,请你设计一个圆环套圈的半径尺寸,使得它每次最多只能套中一个玩具,但同时为了让游戏看起来更具有吸引力,这个套圈的半径又需要尽可能大。
为使问题进一步简单化,假设每个玩具都是平面上一个没有面积的点,套圈是简单的圆,一个玩具被套住,是指这个点到圆心的距离严格小于圆的半径。如果有两个玩具被放在同一个位置,那么输出的圆半径就是0.
2、任务定义
(1)定义一个点的结构体Wanju来存放点的横纵坐标,表示一个玩具的空间位置,同时采用Wanju这种结构体数组来存放不同的玩具;
(2)求最小套圈设计问题归结为先输入每个玩具的空间位置,然后求他们任意两点之间的最小距离,然后取最小距离的一半即为套圈半径,判断是否有两个或两个以上的玩具放在同一点,若有,那么套圈的半径就为0;
(3)求最小距离的方法采用“分而治之”,将所有的点按它的X坐标排序,从中间将场地一分为二,然后递归的解决两边场地的子问题,分别得到两个字问题的最小半径d左和d右,在横跨分界线的且距离分界线小于d左和d右中较小的那个的区域中找出所有横跨分界线的点对中距离最近的点对,将其记为d,然后看它和刚刚求的那个最小距离哪个更小,最小的那个的一半即为最小套圈半径;
(4)定义两个数组分别来存放玩具和最小距离,实现对多组测试数据的输入和测试结果的存放和输出。
二、数据结构的选择和概要设计
1、玩具的存储结构
将玩具抽象成空间一个没有面积的点,其数学模型如下图所示:
a11 a12 ┅ a1n
a21 a22 ┅ a2n
Am×n= (1≤X≤m,1≤Y≤n)
┇ ┇ aij ┇
am1 am2 ┅ amn
因此可以用空间坐标X和Y来表示,在本程序中我采用了数组这种存储结构,包含横纵坐标的结构体类型Wanju;
数据类型描述如下:
typedef struct { float x; //点的横坐标;
float y; //点的纵坐标;
}Wanju;
2、创建放置玩具思想的算法
(1)声明Wanju类型的结构体,根据提示信息输入玩具的个数,根据输入的玩具个数将每个点的横纵坐标输入,然后依次存放在数组之中;
(2)如果输入的玩具个数大于程序刚开始自定义的MAXWANJUS或小于0输出错误的提示信息;
(3)当输入的玩具个数为0时结束输入测试组;
3、将所有的点按X坐标排序;
为了提高求最短距离的效率,将所有的点先按X坐标排序,本程序中排序采用的是系统的库函数qsort,采用该算法能够提高算法的效率;算法思想:在compx()函数为将两个点的横坐标减横坐标,如果大于0,返回1则发生交换,如果等于0或小于0则不发生交换,在qsort函数中第一个参数为数组名,第二个为数组中元素的个数,第三个为每个数组元素
所占的字节大小,最后一个为调用的表达式比较的交换函数compx;
int compx(const void *a, const void *b) { //实现按x排序
return ((Wanju*)a)-x-(( Wanju*)b)-x;
}
int compy(const void* a, const void* b) { //实现按y排序
return ((Wanju *)a)-y-(( Wanju *)b)-y;
}
qsort(wanjus, numWanjus,
您可能关注的文档
- 继电盒盖课程设计说明书.doc
- 简易波形发生器课程设计报告.doc
- 简易电子琴单片机课程设计.doc
- 简易示波器课程设计报告.doc
- 简易自动电阻测试仪设计周记.doc
- 简易自动油烟机控制系统毕业设计.doc
- 胶带输送机减速器课程设计.doc
- 节流变压降流量计课程设计.doc
- 结构设计原理课程设计---钢筋混凝土单向肋梁楼盖设计书.doc
- 结合支持向量机的特征选择方法在信用评估中的应用外文翻译.doc
- 浙江省临海市白云高级中学2025届高三历史3月月考试题.doc
- 云南拾谷县第一中学2024_2025学年高二物理上学期10月月考试题.doc
- 2025版高考生物总复习第13讲基因的分离定律教案苏教版.doc
- 湖北省黄石实验高中2024_2025学年高一历史下学期期末考试模拟卷.doc
- 通史版2025版高考历史大一轮复习专题七近代化的曲折发展__中日甲午战争至五四运动前4第4讲从维新思想到新文化运动课后达标检测含解析新人教版.doc
- 2024年高考数学考试大纲解读专题04导数及其应用含解析文.doc
- 河南省许汝平九校联盟2024_2025学年高一语文上学期期末考试试题扫描版无答案.doc
- 江西省吉安市吉水县第二中学2024_2025学年高一历史上学期第二次月考试题.doc
- 北京市平谷区2025届高三政治一模考试试题含解析.doc
- 2025届中考物理第四讲物态变化专项复习测试无答案新人教版.docx
文档评论(0)