阅读以下说明和流程图,填补流程图中的空缺,将解答填入答题纸的对应栏内。
【说明】
下面流程图的功能是:在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组 A[1:n](n≥2)中,要求寻找最长递增子序列 A[K: K+L-1] (即A[K]<A[K+1]<…<A[K+L-1])。流程图中,用 Kj 和Lj 分别表示动态子序列的起始下标和长度,最后输出最长递增子序列的起始下标 K 和长度 L。
例如,对于序列 A={1 ,2,4,4 ,5,6,8,9,4,5,8},将输出K=4, L=5。
【流程图】

注:循环开始框内应给出循环控制变量的初值和终值,默认递增值为1,格式为: 循环控制变量=初值,终值
正确答案及解析
正确答案
解析
(1)n-1
(2)Lj+1→Lj
(3)Lj > L
(4)Kj
(5)i+1
本题考查程序员在设计算法,理解并绘制程序流程图方面的能力 。
本题的目标是:在给定的一个整数序列中查找最长的连续递增子序列。查找的方法是:对序列中的数,从头开始逐个与后面邻接的数进行比较。若发现后面的数大于前面 的数,则就是连续递增的情况:若发现后面的数并不大,则以前查看的数中,要么没有连续递增的情况,要么连续递增的情况已经结束,需要再开始新的查找。
为了记录多次可能出现的连续递增情况,需要动态记录各次出现的递增子序列的起始位置(数组下标Kj)和长度 (Lj)。为了求出最大长度的递增子序列,就需要设置变量L和K。保存迄今为止最大的Lj及其相应的Kj。正如打擂台一样,初始时设置擂主 L=1,以后当 Lj>L 时,就将 Lj放到 L中,作为新的擂主。擂台上始终是迄今为止的连续递增序列的最大长度。而 Kj则随 Lj→L 而保存到 K 中。
由于流程图中最关键的步骤是比较 A[i]与 A[i+1].因此对i的循环应从1到n-1,而不是1到 n 。最后一次比较应是“A[n-1]<A[n]?”。因此(1)处应填 n-1 。
当 A[i]<A[i+1]成立时,这是递增的情况。此时应将动态连续递增序列的长度增1, 因此(2)处应填写 Lj+1→Lj。
当A[i]<A[i+1]不成立时,表示以前可能存在的连续递增已经结束。此时的动态长度Lj应与擂台上的长度 L 进行比较。即(3)处应填 Lj >L。
当 Lj>L 时,则 Lj将做新的擂主 (Lj→L).同时执行Kj→K。所以(4)处应填Kj 。
当 Lj>L 不成立时,L 不变,接着要从新的下标 i+1 处开始再重新查找连续递增子序列。因此 (5) 处应填 i+1。长度也要回到初始状态1。
循环结束时,可能还存在最后一个动态连续子序列(从下标码那里开始有长度的Lj子序列)没有得到处理。因此还需要再打一次擂台,看是否超过了以前的擂主长度。一旦超过,还应将其作为擂主,作为查找的结果 。





