已知:A1,A2,……,A81 共有81个数,其中只有一个数比其它数大,要用最少的比较运算次数,把这个值大的数找出来(假设两个数比较一次能决定出大于、小于或等于这三种情况)请将以下算法补充完整:(9%)
第一步: S1 = A1 + A2 + …… + A27
S2 = A28 + A29 +……+ A54
第一次比较(S1,S2) :
S1 > S2 取 K=0
S1 < S2 取 K=27
S1 = S2 取 K=54
第二步: S1 = AK+1 + AK+2 + …… + AK+9
S2 = AK+10 + AK+11 +……+ AK+18
第二次比较(S1,S2) :
S1 > S2 取 K=
S1 < S2 取 K=
S1 = S2 取 K=
第三步: S1 = AK+1 + AK+2 + AK+3
S2 = AK+4 + AK+5 + AK+6
第三次比较(S1,S2) :
S1 > S2 取 K=
S1 < S2 取 K=
S1 = S2 取 K=
第四步: S1 = AK+1
S2 = AK+2
第四次比较(S1,S2) :
S1 > S2 为最大数
S1 < S2 为最大数,
S1 = S2 为最大数。 答案:第二次比较(S1,S2):
S1>S2 取K=K+0
S1<S2 取K=K+9
S1=S2 取K=K+18
第三次比较(S1,S2):
S1>S2 取K=K+0
S1<S2 取K=K+3
S1=S2 取K=K+6
第四次比较(S1,S2):
S1>S2 AK+1为最大数
S1<S2 AK+2为最大数
S1=S2 AK+3为最大数
|