问题描述:G公司有n个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等.如何用最少搬运
算法设计:对于给定的n个环形排列的仓库的库存量,计算使n个仓库的库存数量相同的最少搬运量.
数据输入:由文件input.txt提供输入数据.文件的第1行中有1个正整数n,表示有n个仓库.第2行中有n个正整数,表示n个仓库的库存量.
结果输出:将计算的最少搬运量输出到文件output.txt.
算法设计:对于给定的n个环形排列的仓库的库存量,计算使n个仓库的库存数量相同的最少搬运量.
数据输入:由文件input.txt提供输入数据.文件的第1行中有1个正整数n,表示有n个仓库.第2行中有n个正整数,表示n个仓库的库存量.
结果输出:将计算的最少搬运量输出到文件output.txt.
第1题
问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.
算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).
结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.
第2题
问题描述:给定一条有向直线L及L上的n+1个点.有向直线L上的每个点x都有权值w(xi),每条有向边都有一个非负边长.有向直线L上的每个点x可以看作客户,其服务需求量为w(xi)e每条边的边长可以看作运输费用.如果在点xi处未设置服务机构,则将点xi处的服务需求沿有向边转移到点xj处服务机构需付出的服务转移费用为.在点x0处已设置了服务机构,现在要在直线L上增设2处服务机构,使得整体服务转移费用最小.
算法设计:对于给定的有向直线L,计算在直线L上增设2处服务机构的最小服务转移费用.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数m,表示有向直线L上除了点x0还有n个点接下来的n行中,每行有2个整数.第i+1行的2个整数分别表示和.
结果输出:将计算的最小服务转移费用输出到文件output.txt.
第3题
算法设计:对于给定的k个待安排的活动,计算使用最少会场的时间表.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数k,表示有k个待安排的活动.接下来的k行中,每行有2个正整数,分别表示k个待安排的活动的开始时间和结束时间.时间以0点开始的分钟计.
结果输出:将计算的最少会场数输出到文件output.txt.
第4题
问题描述:给定2个长度分别为n和m的序列x[0...n-1]和y[0...m-1],以及d个约束字符串多子串排斥约束的最长公共子序列问题就是要找出x和y的不含为其子串的最长公共子序列
算法设计:设计一个算法,找出给定序列x和y的不含为其子串的最长公共子序列.
数据输入:重文件input.txt提供输入数据.文件的第1行中给出正整数d,表示约束字符串个数.接下来的2行分别给出序列x和y.最后d行的每行给出一个约束字符串.
结果输出:将计算出的x和y的不含为其子串的最长公共子序列输出到文件output.txt中.文件的第1行输出最长公共子序列.第2行输出最长公共子序列的长度.
第5题
问题描述:设有n个程序{1,2,...,n}要存放在长度为1的磁带上.程序i存放在磁带上的长度是li(1≤i≤n).程序存储问题要求确定这n个程序在磁带上的一个存储方案,使得能够在磁带上存储尽可能多的程序.
算法设计:对于给定的n个程序存放在磁带上的长度,计算磁带上最多可以存储的程序数.
数据输入:由文件input.txt给出输入数据.第1行是2个正整数,分别表示文件个数n和磁带的长度L.接下来的1行中,有1个正整数,表示程序存放在磁带上的长度.
结果输出:将计算的最多可以存储的程序数输出到文件output.txt.
第6题
问题描述:假设有来自n个不同单位的代表参加一次国际会议.铄个单位的代表数分别为ri(i=1,2,...,n).会议餐厅共有m张餐桌,每张餐桌可容纳ci(i=1,2,...,m)个代表就餐.为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐.试设计一个算法,给出满足要求的代表就餐方案.
算法设计:对于给定的代表数和餐桌数以及餐桌容量,计算满足要求的代表就餐方案.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数m和n,m表示餐桌数,n表示单位数(1≤m≤150,1≤n≤270).文件第2行有m个正整数,分别表示每个单位的代表数.文件第3行有n个正整数,分别表示每个餐桌的容量.
结果输出:将代表就餐方案输出到文件output.txt如果问题有解,在文件第1行输出1,否则输出0.接下来的m行给出每个单位代表的就餐桌号.如果有多个满足要求的方案,只要输出一个方案.
第7题
问题描述:机器人Rob在一个有n×n个方格的方形区域F中收集样本.(i,j)方格中样本的价值为v(i,j),如图3-6所示.Rob从方形区域F的左上角A点出发,向下或向右行走,
直到右下角的B点,在走过的路上,收集方格中的样本.Rob从A点到B点共走2次,试找出Rob的2条行走路径,使其取得的样本总价值最大.
算法设计:给定方形区域F中的样本分布,计算Rob的2条行走路径,使其取得的样本总价值最大.
数据输入:由文件input.xt给出输入数据.第1行有1个正整数n,表示方形区域F有n×n个方格.按下来每行有3个整数,前2个数表示方格位置,第3个数为该位置样本价值.最后一行是3个0.
结果输出:将计算的最大样本总价值输出到文件output.txt.
第8题
的最小值称为数据包序列的均衡负载量.
算法设计:对于给定的数据包序列,计算m个处理器的均衡负载量.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.n表示数据包个数,m表示处理器数.接下来的1行中有n个整数,表示n个数据包的大小.
结果输出:将计算的处理器均衡负载量输出到文件output,txt,且保留2位小数.
第9题
算法设计:设计一个解n后问题的队列式分支限界法,计算在n×n个方格上放置彼此不受攻击的n个皇后的一个放置方案.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n.
结果输出:将计算的彼此不受攻击的n个皇后的一个放置方案输出到文件output.txt文件的第1行是n个皇后的放置方案.
第10题
问题描述:给定k个排好序的序列用2路合并算法将这k个序列合并成一个序列.假设采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较.
试设计一个算法确定合并这个序列的最优合并顺序,使所需的总比较次数最少.
为了进行比较,还需要确定合并这个序列的最运合并顺序,使所需的总比较次数最多.
算法设计:对于给定的k个待合并序列,计算最多比较次数和最少比较次数合并方案.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数k,表示有k个待合并序列.接下来的1行有k个正整数,表示k个待合并序列的长度.
结果输出:将计算的最多比较次数和最少比较次数输出到文件output.txt.
第11题
B.绒毛心
C.盔甲心
D.桑葚心
E.菜花心
2月龄猪群,生长迅速,部分猪发病,听诊心率加快、心律不齐,有的突然死亡,血砸含量在0.04μg/mL左右。该病的心脏病变为A.虎斑心
B.绒毛心
C.盔甲心
D.桑葚心
E.菜花心
请帮忙给出每个问题的正确答案和分析,谢谢!