发布时间 : 星期六 文章NOIP初赛复习 - 算法1更新完毕开始阅读9239e7099b89680202d8258b
If T1 else l0←l； {若乙早到达，则取区间右半部分} until |T1-T2| T1?T22； 输出两人到达B点的时间为 二、二分法 有些问题可以设计出直观的减半递推算法，经过逐次减半递推，直接得到所需要的结果 （例如例题廿八、廿九）。但对于另外一些问题，根据减半递推技术设计出的算法是递归算法，在执行过程中只能靠算法本身到达递归边界，并且原问题的解由子问题的解合并而成。这种递归的减半递推技术亦称二分法。其计算过程一般分三个步骤： 分解： 将原问题分解成规模减半、而结构与原问题相似的两个子问题； 解决： 递归解这两个子问题。若子问题不能再分解，则直接解； 合并： 将子问题结果合并成原问题的解； 【例题三十】合并排序 对序列A[1]，A[2]，??，A[n]进行合并排序。 输入： n A[1]，A[2]，??，A[n] 输出： 排序后的A[1]，A[2]，??，A[n] 算法分析： 合并排序的算法就是二分法 ?n??n????? 分解：将ｎ个元素各含?2?(或?2?)个元素的子序列； 解决：用合并排序法对两个子序列递归地排序； 合并：合并两个已排序的子序列以得到排序结果； 在对子序列排序时，当其长度为1时递归结束，因为单个元素被视为是已排好序的。合并排序的关键步骤在于合并目前产生的两个已排好序的子序列 A[p‥q]和A[q+1‥r] 将它们合并成一个已排好序的子序列A[p‥r]。我们引入一个辅助过程merge(A，p，q，r)来完成这一合并工作，其中A是数组，p，q ，r是下标。这个过程如果用玩扑克来比喻，就可以看作桌上有两堆牌，每一堆都是排好序的，最小的牌在最上面，我们希望把这两堆牌合并成排好序的一堆。基本步骤包括：先取面朝上的两堆牌的顶上两张中较小的一张，将它 取出面朝下地放到合并堆中。重复这个步骤直到其中某一堆为空。这时把另一个堆中余下的牌面朝下放入合并堆即可。 Procedure merge(Var A： ListType； p， q， r ： Integer)； {将两个已排好序的子序列A[p‥q]和A[q+1‥r]合并成一个已排好序的序列A[p‥r]} Var i， j， t ： Integer； {左子序列首指针；右子序列首指针；合并后的序列首指针} Lt ： ListType； {暂存合并序列} Begin t ：= p； i ：= p； j ：= q + 1；{设定合并序列的首指针、左子序列首指针、右子序列首指针} While（t≤r）Do Begin {若合并未完成，则循环} If (i≤q) And ((j > r) Or (A[i]≤A[j])) then Begin {若左序列剩有元素并且右序列元素全部合并或者左序列的首元素小于等于右序列的首元素，则左序列的首元素进入合并序列，左序列的首指针+1 Lt[t]←A[i]； Inc(i) End{then} Else Begin {否则左序列的首元素进入合并序列，右序列的首指针+1} Lt[t]←A[j]； Inc(j)； End；{else} Inc(t) {合并序列的指针+1} End；{while} For i ：= p to r Do A[i]←Lt[i]； {合并后的序列赋给A} End；{merge} 现在就可以把merge过程作为合并排序的一个子过程来用了。下面是merge_sort(A，p，r)对数组A[p‥r]进行排序。若p≥r，该子数组至多只有一个元素，当然就是已排序的。否 ?p?r?1???2??)，而将A[p‥r]分成A[p‥q]和A[q+1则，分解步骤就计算出一个中间下标q(q= ‥r]。若数组A〔p‥r〕的元素个数k＝r－p+1为偶数，则两个数组各含k/2个元素；否则 ?k??k??k???????A[p‥q]含?2? +1(?2?)元素、A[q+1‥r〕含?2?个元素。 Procedure merge_sort(Var A ： ListType； p， r ： Integer)； Var q ： Integer； Begin If p <> r Then Begin {若子序列A中不止一个元素} q←(p + r - 1) div 2； {计算中间下标q} merge_sort(A， p， q)； {继续对左子序列A[p‥q]递归排序} merge_sort(A， q + 1， r)； {继续对右子序列A[q+1‥r]递归排序} merge(A， p， q ，r)； {对左子序列和右子序列合并排序} End{then} End；{Merge_sort} 我们只要调用merge_sort(A，1，n)便可对整个序列A[1]??A[n]进行合并排序。如果我们自底向上(此处“底”为n是2的幂时)来看这个过程的操作时，算法将两个长度为1的序列合并成排好序的长度为2的序列，继而合并成长度为4的序列??，依次类推。随着算法自底向上执行，被合并的排序序列长度逐渐增加，一直进行到将两个长度为n／2的序列合并成最终排好序的长度为n的序列。（图5．2-3）列出了对序列(5，2，4，6，1，3，2，6)进行合并排序的过程。 排序结果： 1 2 2 3 4 5 6 6 当然，排序算法很多，但合并排序法也有其本身的特点──当输入的规模足够大时，合并排序的运行时间要比最坏情况下的插入排序好。分治算法不仅可应用于排序，而且还可应用于许多重要的场合，甚至有些问题看起来非得采用分治法求解不可。 【例题三十一】导线和开关 如(图5．2－4)所示，具有3根导线的电缆把A区和B区连接起来。在A区3根导线标以1，2，3；在B区导线1和3被连到开关3，导线2连到开关1。 一般说来，电缆含m(1≤m≤90)根导线，在A区标以1，2，?m。在B区有m个开关，标为1，2，?m。每一根导线都被严格地连到这些开关中的某一个上；每一个开关上可以连有0根或多根导线。 测量 你的程序应作某些测量来确定，导线和开关怎样连。每个开关或处于接通或处于断开状态，开关的初始状态为断开。我们可用一个探头(probe)P在A区进行测试：如果探头点到某根导线上，当且仅当该导线连到处接通状态的开关时，灯L才会点亮。 你的程序从标准输入(standard input)读入一行以得到数字m；然后可以通过向标准输出(standard output)写入一行以发出命令(共3种命令)。每种命令的开头是一个大写字母： 测试导线命令T：T后面跟一个导线标号； 改变开关状态命令C：C后面跟一个开关标号； 完成命令D：D后面跟的是一个表列(LIST)，该表列中的第ｉ个元素代表与导线ｉ相 连的开关号。 在命令T和C之后，你的程序应从标准输入(standard input)读入一行。若开关状态能使灯亮，则命令T的回答应是Y；反之，回答应是N。命令C的作用是改变开关的状态(若原来是接通则变为断开；若原来是断开则变为接通)。对C命令的回答是作为一种反馈信号。 你的程序可以给出一系列命令，将T命令与C命令以任意顺序混合使用。最后给出命令D，并结束。你的程序给出的命令总数应不大于900。 注意：为了在此任务中能正确使用标准输入(standard input)和标准输出(standard output)，若你使用pascal，请不要使用其中的CRT单元(unit CRT)。 举例 ( 图5．2－5)给出了一个实例，对应于(图5．2－4)，这是一个有8条命令的对话。 Standard Output C3 T1 T2 T3 C3 C2 T2 D 3 1 3 Standard Input 3 Y Y N Y N Y N (图5．2－5) 算法分析 为了使导线和开关间的连接工作有规律地进行，我们不妨采用二分法。设 当前待连接的开关为head‥tail，初始时为1‥m将这些开关一分为二