首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(
admin
2013-01-05
33
问题
阅读下列函数说明和C代码,
[说明]
所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。
应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(作为边的权值),按长度大小对各边进行排序后,按贪婪准则从排序后的各边中选择组成回路的边,贪婪准则使得边的选择按各边长度从小到大选择。
函数中使用的预定义符号如下:
#define M 100
typedef struct{/*x为两端点p1、p2之间的距离,p1、p2所组成边的长度*/
float x;
int p1,p2;
}tdr;
typedef struct{/*p1、p2为和端点相联系的两个端点,n为端点的度*/
int n,p1,p2;
}tr;
typedef struct{/*给出两点坐标*/
float x,y;
}tpd;
typedef int tl[M];
int n=10;
[函数]
float distance(tpd a,tpd b);/*计算端点a、b之间的距离*/
void sortArr(tdr a[M],int m);
/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表,m为边的条数*/
int isCircuit(tr r[M],int i,int j);
/*判断边(i,j)选入端点关系表r[M]后,是否形成回路,若形成回路返回0*/
void selected(tr r[M],int i,int j);/*边(i,j)选入端点关系表r*/
void course(tr r [M],tl l[M]);/*从端点关系表r中得出回路轨迹表*/
void exchange(tdr a[M],int m,int b);
/*调整表排序表,b表示是否可调,即是否有长度相同的边存在*/
void travling(tpd pd [M],int n,float dist,tl locus[M])
/*dist记录总路程*/
{
tdr dr[M];/*距离关系表*/
tr r[M];/*端点关系表*/
int i,j,k,h,m;/*h表示选入端点关系表中的边数*/
int b;/*标识是否有长度相等的边*/
k=0;
/*计算距离关系表中各边的长度*/
for(i=1;i<n; i++){
for(j=i+1;J<=n;j++){
k++;
dr[k].x=(1);
dr[k].pl=i;
dr[k].p2=j;
}
}
m=k;
sortArr(dr,m);/*按距离大小从小到大排序形成排序表*/
do{
b=1;
dist=0;
k=h=0:
do{
k++;
i=dr[k].p1;
j=dr[k].p2;
if((r(i].n<=1)&&(r[j].n<=1)){/*度数不能大于2*/
if (2) {
/*若边(i,j)加入r后形成回路,则不能加入*/
(3);
h++;
dist+=dr[k].x;
}else if (4) {
/*最后一边选入r成回路,则该边必须加入且得到解*/
selected(r,i,j);
h++:
dist+=dr[k].x;
}
}
}while((k !=n) && (h !=n));
if(h==n){/*最后一边选入构成回路,完成输出结果*/
course(r,locus);
}else(/*找不到解,调整dr,交换表中边长相同的边在表中的顺序,并将b置0*/
(5);
}
}while(!b);
}
(1)
选项
答案
distance(pd[i],pd[j])
解析
是计算各边的长度,根据函数的声明及说明,可得应填distance(pd
,pd[j])。
转载请注明原文地址:https://kaotiyun.com/show/0YDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
造成软件测试风险的主要原因不包括()。
设数组a[0..n—1,0..m一1](n>1,m>1)中的元素以行为主序存放,每个元素占用4个存储单元,则数组元素a[i,j](0≤i
在输入输出控制方法中,采用______可以使得设备与主存间的数据块传送无需CPU干预。A.程序控制输入输出B.中断C.DMAD.总线控制
某系统中,模块A处理与销售相关的所有细节,仅需要发送一个包含销售量、价格和时间的报表到模块B,则这两个模块之间为()耦合。
功能测试执行过后一般可以确认系统的功能缺陷,缺陷的类型包括(37)。①功能不满足隐性需求②功能实现不正确③功能不符合相关的法律法规④功能易用性不好
若浮点数的阶码用移码表示,尾数用补码表示。两规格化浮点数相乘,最后对结果规格化时,右规的右移位数最多为(2)位。
下列操作系统中,_____保持网络系统的全部功能,并具有透明性、可靠性和高性能等特性。
以下不属于在需求分析阶段编写的文档是
目前,通过移动电话接人互联网采用的主要技术是什么?进行一次查询的数据信息如表9-1所示,网络的基本通信服务费用如表9-2所示,总费用=网络租用费+通信费。根据表中给出的数据,试计算销售员每月至少应进行多少次查询,才能使得使用移动电话的总费用比使用PDA
根据图3-1所给出的网络连接方式及相关的网络参数,区域(A)与区域(B)中计算机的网络参数配置(如图3-2所示)为:区域(A)计算机“IP地址”(范围):(1):区域(A)计算机“子网掩码”;(2);区域(A)计算机“默认网关”:(
随机试题
“政声人去后,民意巷谈时”,警示领导干部在工作作风方面要时刻注意【】
2011年3月10日凌晨两点钟左右,张某、李某和王某三人蒙面闯进郝某家。三个人进了郝某睡觉的房间,张某从身上抽出砍刀,用刀背猛敲郝某的脑袋。一阵剧痛使郝某惊醒过来:“你们是谁?要干什么?”随后,三人将郝某按在床上,并一齐举起手中的利刃,朝他身上一顿乱捅,可
住宅分户轻质隔墙的隔声标准的隔声量最低限值是:[2004年第085题][2007年第085题]
下列属于民用爆炸物品的爆破器材有()。
明确划分国家各级权力机关、各级政府、各级财政部门以及各部门各单位在预算活动中的职权,是保证依法管理预算的前提条件也是将各级预算编制、预算审批、预算执行、预算调整和预算决算的各环节纳入法治化、规范化轨道的必要措施。《预算法》明确地规定了各级人民代表大会及其常
下面有关托收业务的描述,正确的有( )。
根据《证券法》的规定,下列选项中,属于股份有限公司申请股票上市应当符合的条件有()。
学生李某在课堂上讲话,扰乱课堂秩序,教师让其下课后到办公室,李某来到办公室后,老师先给他一颗糖,说:“这糖奖励你能遵守我们的约定,按时到来。”李某听后羞愧万分,主动向教师道歉并保证不再扰乱课堂秩序。上述案例中的教师表现出的是()。
班主任工作的中心环节是全面了解和研究学生。()
【S1】【S5】
最新回复
(
0
)