题目内容
（请给出正确答案）
算法设计:对任意给定的整数n和k,以及完成任务i需要的时间为ti(i=1,2,...,n).设计一个优先队列式分支限界法,计算完成这n个任务的最佳调度.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k.第2行的n个正整数是完成n个任务需要的时间.
结果输出:将计算的完成全部任务的最早时间输出到文件output.txt.
如果结果不匹配，请 联系老师 获取答案
更多“问题描述:假设有n个任务由k个可并行工作的机器完成.完成任务…”相关的问题
问题描述:给定k个正整数,用算术运算符+、-、*./将这k个正整数连接起来,使最终的得数恰为m.
算法设计:对于给定的k个正整数,给出计算m的算术表达式.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数k和m,表示给定k个正整数,且最终的得数恰为m.接下来的一行中有k个正整数.
结果输出:将计算m的算术表达式输出到文件output.txt.如果有多个满足要求的表达式,只要输出一组,每步算式用分号隔开.如果无法得到m,则输出“NoSolution!”.
算法设计:对于给定的维修程序时间表,计算最优时间表.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k.n表示仪器的工作时间单位,k是维修程序数.在接下来的k行中,每行有2个表示维修程序的整数s和t,该维修程序从第s个时间单位开始,持续t个时间单位.
结果输出:将计算出的最短维修时间输出到文件output.txt.
算法设计:对于给定的I和k,计算I的最大k乘积.
数据输入:由文件input.txt提供输入数据.文件的第1行中有2个正整数n和k.正整数n是序列的长度,正整数k是分割的段数.接下来的一行中是一个n位十进制整数(n≤10).
结果输出:将计算结果输出到文件output.txt.文件第1行中的数是计算出的最大k乘积.
问题描述:设磁盘上有n个文件
每个文件占用磁盘上的1个磁道.这n个文件的检索概率分别是
且
磁头从当前磁道移到被检信息磁道所需的时间可用这两个磁道之间的径向距离来度量.如果文件fi存放在第i(1≤i≤n)道上,则检索这n个文件的期望时间是
.式中,d(i,j)是第i道与第j道之间的径向距离|i-j|.
磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置,使期望检索时间达到最小.试设计一个解此问题的算法,并分析算法的正确性与计算复杂性.
算法设计:对于给定的文件检索概率,计算磁盘文件的最优存储方案.
数据输入:由文件input.txt给出输入数据.第1行是正整数n,表示文件个数.第2行有n个正整数a,表示文件的检索概率.实际上第k个文件的检索概率应为
结果输出:将计算的最小期望检索时间输出到文件output.txt.
处.居民们希望在城市中至少选择一个,但不超过k个居民点建立服务机构.在每个居民点xi处,服务需求量为wi≥0.在该居民点设置服务机构的费用为ci≥0.假设居民点xi到距其最近的服务机构的距离为di,则居民点x的服务费用为
建立k个服务机构的总费用为A+B.A是在k个居民点设置服务机构的费用的总和;B是n个居民点服务费用的总和.算法设计:对于给定直线上的n个点
,计算在直线L上最多设置k处服务机构的最小总费用.
数据输入:由文件input,txt给出输入数据.第1行有2个正整数n和k.n表示直线L上有n个点k是服务机构总数的上限.接下来的n行中,每行有3个整数.第i+1行的3个整数xi、wi、ci,分别表示相应居民点的位置坐标、服务需求量和在该点设置服务机构的费用.
结果输出:将计算的最小服务费用输出到文件output.txt
A.①、②
B.②、③
C.①、③
D.无
规则I:每次只能移动1个圆盘:
规则II:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
规则III:任何时刻都不允许将同色圆盘叠放在一起:
规则IV:在满足移动规则I~III的前提下,可将圆盘移至A、B、C中任一塔座上.
试设计一个算法,用最少的移动次数将塔座A上的n个圆盘移到塔座B上,并仍按同样顺序叠置.
算法设计:对于给定的正整数n,计算最优移动方案.
数据输入:由文件input.txt给出输入数据.第1行是给定的正整数no.
结果输出:将计算出的最优移动方案输出到文件output.txt.文件的每行由一个正整数k
和2个字符c1和c2组成,表示将第k个圆盘从塔座c1移到塔座c2上.
试题四（15分）
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
某工程计算中要完成多个矩阵相乘（链乘）的计算任务。
两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算Am*n*Bn*p，需要m*n*p次乘法运算。
矩阵相乘满足结合律，多个矩阵相乘，不同的计算顺序会产生不同的计算量。以矩阵A110*100，A2100*5，A35*50三个矩阵相乘为例，若按（A1*A2）*A3计算，则需要进行10*100*5+10*5*50=7500次乘法运算；若按A1*（A2*A3）计算，则需要进行100*5*50+10*100*50=75000次乘法运算。可见不同的计算顺序对计算量有很大的影响。
矩阵链乘问题可描述为：给定n个矩阵＜A1,A2,….An＞，矩阵Ai的维数为pi-1*Pi，其中i = 1,2,….n。确定一种乘法顺序，使得这n个矩阵相乘时进行乘法的运算次数最少。
由于可能的计算顺序数量非常庞大，对较大的n，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若A1*A2*…*An的一个最优计算顺序从第k个矩阵处断开，即分为A1*A2*….Ak和Ak+1*Ak+2*…*An两个子问题，则该最优解应该包含A1*A2*…*Ak的一个最优计算顺序和Ak+1*Ak+2*…An的一个最优计算顺序。据此构造递归式，
其中，cost[i][j]表示Ai+1*Ai+2*...Aj+1的最优计算的计算代价。最终需要求解cost[0][n-1]。
【C代码】
算法实现采用自底向上的计算过程。首先计算两个矩阵相乘的计算量，然后依次计算3个矩阵、4个矩阵、…、n个矩阵相乘的最小计算量及最优计算顺序。下面是算法的C语言实现。
（1）主要变量说明
n：矩阵数
seq[]：矩阵维数序列
cost[][]：二维数组，长度为n*n，其中元素cost[i][j]表示Ai+1*Ai+2*…Aj+1的最优计算的计算代价
trace[][]：二维数组，长度为n*n，其中元素trace[i][j]表示Ai+1*Ai+2*Aj+1的最优计算对应的划分位置，即k
（2）函数cmm
define N 100
intcost[N][N];
inttrace[N][N];
int cmm(int n,int seq[]){
int tempCost;
int tempTrace;
int i,j,k,p;
int temp;
for(i=0;i＜n;i++){ cost[i][i] =0;}
for(p=1;p＜n;p++){
for(i=0; （1） ;i++){
（2）;
tempCost = -1;
for(k = i;k＜j;k++){
temp = （3） ;
if(tempCost==-1||tempCost＞temp){
tempCost = temp;
（4） ；
}
}
cost[i][j] = tempCost;
trace[i][j] = tempTrace;
}
}
return cost[0][n-1];
}
【问题1】（8分）
根据以上说明和C代码，填充C代码中的空（1）~（4）。
【问题2】（4分）
根据以上说明和C代码，该问题采用了 （5） 算法设计策略，时间复杂度 （6） 。（用O符号表示）
【问题3】（3分）
考虑实例n=6，各个矩阵的维数：A1为5*10，A2为10*3，A3为3*12，A4为12*5，A5为5*50，A6为50*6，即维数序列为5,10,3,12,5,50,6。则根据上述C代码得到的一个最优计算顺序为 （7） （用加括号方式表示计算顺序），所需要的乘法运算次数为 （8） 。
0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为vi ，重量为wi（vi，和wi为非负数），背包容量为W（W为非负数），选择其中一些物品装入背包，使装入背包物品的总价值最大，
，且总重量不超过背包容量，即
，其中，xi∈{0,1}，xi=0表示第i个物品不放入背包，xi=1表示第i个物品 放入背包。
【问题1】（8分）
用回溯法求解此0-1背包问题，请填充下面伪代码中（1）~（4）处空缺。
回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点己经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND（v,w,k,W）函数，其中v, w, k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。
下面给出0-1背包问题的回溯算法伪代码。
函数参数说明如下：
W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。
变量说明如下：
cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。
BKNAP(W,n,w,v,fw,fp,X）
1 cw ← cp ← 0
2 （1）
3 fp ← -1
4 while true
5 while k≤n and cw＋w[k]≤W do
6 （2）
7 cp ← cp＋v[k]
8 Y[k]← 1
9 k ← k+1
10 if k＞n then
11 if fp＜cp then
12 fp ← cp
13 fw ← ew
14 k ← n
15 X ← Y
16 else Y(k)← 0
17 while BOUND(cp,cw,k,W) ≤fp do
18 while k≠0 and Y(k)≠1 do
19 （3）
20 if k＝0 then return
21 Y[k]←0
22 cw ← cw ← w[k]
23 cp ← cp ← v[k]
24 （4）
A.400
B.4000
C.4500
D.5000
阅读以下嵌入式多核程序设计技术方面的叙述，回答问题1至问题3。
甲公司承担了一项为宇航系统配套生产高性能嵌入式计算机系统的任务，用户要求该系统要具有高速并发处理能力、低功耗、高可靠性，并可以有效地防止系统故障的蔓延。根据用户对本项目的要求，甲公司成立了软/硬件两个项目组，总体设计由硬件组承担，负责高性能嵌入式计算机系统体系结构设计，软件组负责确定软件的技术需求和应用软件开发平台的软件设计工作。
在处理器选型方面，硬件组王工与软件组张工在讨论采用哪种CPU体系结构方面发生争议。目前，流行的处理器结构包括了单核结构、多处理器结构、超线程结构、多核结构、共享Cache的多核结构和超线程技术的多核结构六种，如下图所示。
.jpg)
王工提出，根据用户要求，本嵌入式系统应具有高速并行处理能力，采用多处理器结构比较适合，主要理由是多处理器结构设计简单、可支持多个进程在不同处理器上并发处理；而张工提出，必须分清“多处理器结构”与“多核结构”的优点和缺点，多处理器结构虽然支持多进程的并发处理，但没有直接实现多线程并发执行；多核结构可以直接实现多线程并发执行。要提高应用的并行性就必须利用多个硬件资源的并行工作，建议采用超线程技术的多核结构的处理器。请填写下图(f)中的(1)～(8)，并用300字以内的文字对上述六种处理器结构的工作原理进行简要描述。
