不是VIP会员,不能显示答案

题目解答

题目:
求出二个整形数组错位相加的最大面积。
1.数组面积的定义:(限定数组头尾不为0)
设有一个数组C=(4,8,12,0,6)
则C的面积为:
Sc=(4+8)/2 + (8+12)/2 + 12/2 + 6/2
也就是说,Sc=各梯形面积之和(其中梯
形的高约定为1,三角形作为梯形的特殊情况
处理)。
又如D=(12, 24, 6)时,其面积的定义为Sd=(12+24)/2 + (24+6)/2

2.数组错位相加的定义
设有2个正整数的数组a,b,长度为n,当n=5时:
a=(34,26,15,44,12) b=(23,46,4,0,18)
对a、b进行错位相加,可能有下列情况

34 26 15 44 12
+) 23 46 4 0 18
34 26 15 44 12 23 46 4 0 18
或:
34 26 15 44 12
+) 23 46 4 0 18 -
34 26 15 44 35 46 4 0 18
或:
34 26 15 44 12
+) 23 46 4 0 18
34 26 15 67 58 4 0 18
或:……
最后有:
34 26 15 44 12
+) 23 46 4 0 18 -
23 46 4 0 18 34 26 15 44 12
可以看到:由于错位不同,相加的结果也不同。

程序要求:找出一个错位相加的方案,使得输出的数组面积为最大。
[算法提要]: 设a,b的长度为10,用a,b: array[1..10] of integer表示,其结果用数组C,D: array[1..30] of integer表示。
错位相加的过程可以从开始不重叠,然后逐步重叠,再到最后的不重叠。
梯形面积的计算公式为:(上底+下底)×高÷2
其中由于约定高为1,故可写为(上底+下底)÷2。
程序:
   n = 10;
……        Function sea : real; {计算数组C面积}
               Begin
                 J1 := 1;
                 While __c[j1]=0 and j1<3*n__ do 
                   j1 := j1 + 1;
                 ENDWHILE;
                 If   j1 = 3 * n   then sea := 0  
                               Else begin
                                    J2 := 3 * n;
                                    While ___c[j2]=0 and j2>j1__  do 
                                      j2 := j2 - 1;
                                      If  j1 = j2  then sea := 0 
                                                 Else begin
                                                       J3 := c[j1] + c[j2];
                                                       For  j4 := j1 + 1 to j2 - 1 do
                                                         INC(j3,c[j4]*2);
                                                       ENDFOR;
                                                       Sea := j3 / 2
                                                     end
                                        ENDIF;
                                 End;

  //主程序//
        For  i := 1 to n do read(a[I]); endfor;
        For  j := 1 to n do read(b[j]); endfor;
        __s:=0;__;
        for  i := 1 to 2 * n + 1 do
            for  j := 1 to 3 * n do _c[j]:=0;__     endfor;
          for  j := 1 to n do c[j + n] := a[j]                 endfor;
          for  j := 1 to n do
               _c[i+j-1]:=c[i+j-1]+b[j]__;
          endfor;
          p := sea;
          if p > s then begin 
                       d := c;
                       s := p
                    end;
            endif;
          endfor;
          for I := 1 to 3 * n do write(d[I],' ');    endfor;
          write(s);
      End.  //主程序结束//
考点:
分析:
解答:
评论:
老师: