题目分析本题题目名称与197319731973年出版的同名棒球小说《Bang the Drum Slowly》相同但内容是关于早期计算机磁鼓存储器的指令执行时间优化问题。问题背景在早期的计算机系统中主存储器primary memory\texttt{primary memory}primary memory常采用磁鼓magnetic drum\texttt{magnetic drum}magnetic drum作为存储介质。磁鼓是一个沿水平轴旋转的圆柱体其外表面涂有磁性材料通过固定的读写头read/write heads\texttt{read/write heads}read/write heads来访问数据。磁鼓以恒定速度旋转数据按顺序排列在圆周的磁道上地址从111到nnn依次排列。当磁鼓旋转时读写头下方经过的数据字可以被访问。由于磁鼓持续旋转一条指令执行完毕后读写头可能已经旋转到了其他位置此时若要读取下一条指令可能需要等待磁鼓旋转到目标位置这就产生了旋转延迟rotational delay\texttt{rotational delay}rotational delay。为了最小化这种延迟早期机器的设计者采用了一种巧妙的策略在每条指令中包含一个“下一条指令地址”字段。这样汇编器assembler\texttt{assembler}assembler可以在编译时计算出最优的下一条指令位置使得当前指令执行完毕时下一条指令恰好到达读写头下方从而消除旋转等待时间。问题描述本题要求计算简单程序不含循环的平均执行时间。我们考虑单读写头、单磁道的情况。磁道上的地址从111到nnn顺序编号。所有指令的执行时间相同具体等于磁鼓旋转经过ttt个字所需的时间。注意ttt不包含从磁鼓读取指令的时间也不包含当下一指令不在“最优”地址时可能需要的额外旋转延迟但在计算平均执行时间时必须包含这些因素。指令分为三种类型终端指令terminal instruction\texttt{terminal instruction}terminal instruction没有下一条指令地址程序执行到此结束。无条件指令unconditional instruction\texttt{unconditional instruction}unconditional instruction只有一个下一条指令地址。条件指令conditional instruction\texttt{conditional instruction}conditional instruction有两个下一条指令地址每条分支被选择的概率相等即各50%50\%50%。输入格式每个测试用例的输入格式如下第一行包含两个整数nnn和ttt其中1n501 n 501n500tn0 t n0tn。接下来若干行每行表示一条指令首先是地址111到nnn然后是该指令的下一条地址数量000表示终端指令111表示无条件指令222表示条件指令接着是对应数量的分支地址。最后一条指令后以单独一行的000表示该测试用例结束。当n0n 0n0且t0t 0t0时输入结束。输出格式对每个测试用例输出Case X. Execution time Y.YYYY其中XXX是测试用例编号从111开始Y.YYYYY.YYYYY.YYYY是平均执行时间精确到小数点后444位。关键假设每个测试用例开始时磁鼓的位置使得地址111处的指令即将被读取。程序从地址111开始执行。读取一条指令的时间为111个时间单位。至少存在一个终端指令保证程序能够结束。解题思路时间计算模型设当前刚刚执行完地址为currcurrcurr的指令而下一个要执行的指令地址为nextnextnext。在执行currcurrcurr指令的过程中磁鼓一直在旋转。当currcurrcurr指令执行完毕后读写头的位置并不是在currcurrcurr所在的位置因为从读取currcurrcurr指令到执行完毕磁鼓又旋转了ttt个字。因此当前指令执行完毕后读写头的位置为head_positioncurrt(modn) head\_position curr t \pmod{n}head_positioncurrt(modn)更精确地说当currt≤ncurr t \leq ncurrt≤n时新位置为currtcurr tcurrt否则需要循环到地址111即currt−ncurr t - ncurrt−n。接下来需要读取地址nextnextnext处的指令。从当前读写头位置到nextnextnext地址所需的旋转延迟计算如下若head_positionnexthead\_position nexthead_positionnext则旋转延迟为next−head_positionnext - head\_positionnext−head_position。若head_position≥nexthead\_position \ge nexthead_position≥next则需要旋转到末尾再从头到nextnextnext延迟为n−head_positionnextn - head\_position nextn−head_positionnext。得到旋转延迟后再加上读取指令的时间111个时间单位就得到了从当前指令执行完毕到nextnextnext指令开始执行的时间。实际上题目中的ttt已经包含了指令执行时间而旋转延迟和读取时间需要单独计算。阅读通过代码可以发现代码中的处理方式是先计算从当前位置即上一条指令执行完毕后的读写头位置到nextnextnext的旋转延迟然后加上ttt当前指令执行时间再更新当前指令为nextnextnext然后加上ttt来更新读写头位置最后递归处理后续指令。递归计算方法定义函数execute(current,next)\text{execute}(current, next)execute(current,next)表示当前刚刚执行完地址为currentcurrentcurrent的指令读写头位于某个位置接下来要执行地址为nextnextnext的指令从此刻开始到程序结束所需的剩余执行时间。实际上通过代码中的execute(current,next)\text{execute}(current, next)execute(current,next)函数currentcurrentcurrent表示当前读写头的位置是上一条指令执行完毕后的位置nextnextnext表示下一条要执行指令的地址。函数首先计算旋转延迟从currentcurrentcurrent旋转到nextnextnext所需时间然后加上指令执行时间ttt然后更新当前执行地址为nextnextnext再更新读写头位置为nextt\text{next} tnextt模nnn最后根据nextnextnext地址处的指令类型继续执行。记忆化搜索由于程序可能包含条件分支不同路径可能到达相同的(current,next)(current, next)(current,next)状态。为了避免重复计算使用记忆化数组memoization[i][j]\text{memoization}[i][j]memoization[i][j]存储从状态(i,j)(i, j)(i,j)开始的剩余执行时间。对于状态(i,j)(i, j)(i,j)其递归关系如下旋转延迟从iii到jjj的距离。当前指令执行时间ttt。当前指令执行后读写头位置new_head(jt) mod n\text{new\_head} (j t) \bmod nnew_head(jt)modn若结果等于000则取nnn。根据地址jjj处的指令类型若为终端指令返回旋转延迟t tt即当前指令执行完毕程序结束。若为无条件指令剩余时间旋转延迟texecute(new_head,address1) t \text{execute}(new\_head, address1)texecute(new_head,address1)。若为条件指令剩余时间旋转延迟texecute(new_head,address1)execute(new_head,address2)2 t \frac{\text{execute}(new\_head, address1) \text{execute}(new\_head, address2)}{2}t2execute(new_head,address1)execute(new_head,address2)​。初始状态程序开始时地址111处的指令即将被读取这意味着当前读写头位置正好在地址111而还没有执行任何指令。代码中调用execute(0,1)\text{execute}(0, 1)execute(0,1)000是一个虚拟的当前位置表示初始状态。从000到111的旋转延迟计算为1−011 - 0 11−01因为010 101这恰好对应了读取第一条指令所需的111个时间单位。示例验证以Sample Input\texttt{Sample Input}Sample Input的第一个测试用例为例n10n 10n10t5t 5t5指令为1 0即地址111处是终端指令。程序从地址111开始读取第一条指令需111个时间单位。执行指令需t5t 5t5个时间单位。指令为终端程序结束。总时间156.0000 1 5 6.0000156.0000与输出一致。其他测试用例涉及无条件跳转和条件分支递归计算即可得到正确结果。复杂度分析状态数量n×nO(n2)n \times n O(n^2)n×nO(n2)由于n50n 50n50状态数最多250025002500。每个状态计算为O(1)O(1)O(1)。总时间复杂度O(n2)O(n^2)O(n2)空间复杂度O(n2)O(n^2)O(n2)。代码实现// Bang the Drum Slowly// UVa ID: 249// Verdict: Accepted// Submission Date: 2016-06-13// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintNO_ADDRESS-1;// 表示没有分支地址structaddress{intaddress1,address2;// 存储指令的分支地址};vectoraddressinstructions;// 指令存储下标为指令地址doublememoization[50][50];// 记忆化数组memoization[i][j] 表示从状态(i, j)开始的剩余时间intn,t;// n: 磁道上的字数量t: 指令执行时间旋转过的字数doubleexecute(int,int);// 获取从状态(current_address, next_address)开始的执行时间使用记忆化doublegetTime(intcurrent_address,intnext_address){if(memoization[current_address][next_address]0.0)memoization[current_address][next_address]execute(current_address,next_address);returnmemoization[current_address][next_address];}// 模拟程序执行使用记忆化存储结果否则会超时// current_address: 当前读写头位置上一条指令执行完毕后的位置// next_address: 下一条要执行指令的地址doubleexecute(intcurrent_address,intnext_address){// 如果已经计算过直接返回if(memoization[current_address][next_address]0.0)returnmemoization[current_address][next_address];// 计算旋转延迟从 current_address 旋转到 next_address 所需时间doubleelapsed0.0;if(current_addressnext_address)elapsed(next_address-current_address);elseelapsed(n-current_addressnext_address);// 加上当前指令的执行时间 telapsedt;// 更新当前执行地址为 next_addresscurrent_addressnext_address;// 当前指令执行完毕后读写头向前移动 t 个位置current_addresst;current_address(current_addressn)?(current_address-n):current_address;// 根据下一条指令的类型继续执行// 终端指令address1 为 0 表示无分支if(instructions[next_address].address10instructions[next_address].address2NO_ADDRESS)elapsedgetTime(current_address,instructions[next_address].address1);// 条件指令有两个分支elseif(instructions[next_address].address10instructions[next_address].address20){doubletime1getTime(current_address,instructions[next_address].address1);doubletime2getTime(current_address,instructions[next_address].address2);elapsed(time1time2)/2.0;// 两条分支等概率取平均值}// 终端指令的情况address1 为 0直接返回不需要额外处理returnelapsed;}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intcases0;while(cinnt,nt)// 输入 n 和 t均为 0 时结束{instructions.resize(n1);// 地址从 1 到 nfor(inti1;in;i){instructions[i].address1NO_ADDRESS;instructions[i].address2NO_ADDRESS;}intindexer,addresses;// 读取指令地址为 0 表示当前测试用例的指令输入结束while(cinindexer,indexer0){cinaddresses;// 读取分支地址数量// 根据分支数量读取对应地址instructions[indexer].address1addresses;if(addresses1)cininstructions[indexer].address1;if(addresses2)cininstructions[indexer].address2;}// 初始化记忆化数组for(inti0;i50;i)for(intj0;j50;j)memoization[i][j]0.0;// 从初始状态开始计算平均执行时间// 初始读写头位于位置 1 即将读取指令用 0 表示“当前位置”doubleexecution_timeexecute(0,1);// 输出结果coutCase cases. Execution time ;coutfixedsetprecision(4)execution_timeendl;}return0;}总结本题通过记忆化搜索和递归模拟磁鼓存储器的指令执行过程计算了包含条件分支的程序的平均执行时间。关键在于正确建模旋转延迟、指令读取时间和指令执行时间的关系并利用动态规划的思想避免重复计算。题目虽有一定复杂度但理解磁鼓的物理特性和时间计算模型后算法实现较为直接。