当前位置: 高中信息技术 / 综合题
  • 1. (2020·东阳模拟) 求最大连续子矩阵和。给出一个矩阵,序列元素有正整数、0、负整数,在矩阵中限定一块区域,并要求找到该限定区域内的一个子矩阵,使得这个子矩阵与限定区域同宽但可能不同高,且包含的所有元素之和为限定区域矩阵中最大值,在和最大的前提下还要求该子矩阵包含的元素个数最多。

    算法描述如下:

    1)从第一行开始向下进行累加,累加和若大于之前的最大和,则记录此时的最大和及结束位置;

    2)若累加和等于之前的最大和,但元素个数大于之前的最大和的元素个数,则记录此连续子矩阵的结束位置;

    3)若累加和小于0,则重新开始记录;

    4)若有符合条件的多个连续子矩阵,则输出最先找到的子矩阵。

        小俞编写了一个实现该功能的VB程序,窗体加载时生成m*n个序列数据,依次存放在数组a,并显示在列表框List1中,在文本框Text1中输入该矩阵限定区域的左上角位置,在文本框Text2中输入右下角位置,单击“计算”按钮Command1后,找出连续和最大的子矩阵,在标签Label3上显示最大连续子矩阵和,在Label 4上显示该连续子矩阵的元素个数,在Label 5上显示该连续子矩阵开始与结束位置。程序运行界面如图所示。

    1. (1) 在设计程序界面时,要清空文本框中的显示内容,应修改文本框的属性
    2. (2) VB程序代码如下,请在划线处填入合适的代码。

      Const m=12:Const n= 6

      Dim a(1 Tom*n) As Integer

      Private SubForm_Load()

      ‘生成m*n个数据,并显示在列表框List 1,代码略

      End Sub

      Private Sub Command1_Click()

         Dim i As Integer, j As Integer, k As Integer, temp As Integer 

         Dim length As integer, begin As Integer, sum As Integer

         Dim ks As String, js As String

         Dim xy( 1 to 4) As Integer, h sum(1tom*n) As Integer

         ‘读取文本框Text 1的数值分别存储到数组xy(1)、xy(2),读取文本框Text 2的数值分别存储到数组xy(3)、xy(4),xy(1)、xy(3)表示所在行,xy(2)、xy(4)表示所在列,代码略

           For i=1 To xy(3) -xy(1) + 1

             h sum(i) = 0

         Next i

         ‘求限定区域内每行数据之和

         For i=1 To xy(3) -xy(1) + 1

         For j= 1 To   ① 

             h sum(i) =h sum(i) +a((xy(1) +i-2) *n+xy(2) +j-1)

         Next j

         Next i

         ‘找出最大连续之矩阵和

         temp =0:sum=0:length=0:begin= 0

         For i=1 To xy(3)-xy(1) + 1

            If temp+h sum(i) >sum Then

              sum=temp+h sum(i)

             length=i-begin

             k=i

           ElseIf temp+h sum(i) =sum And   ②   Then

             length=i-begin

          k=i

        End If

        If temp+h sum(i) < 0 Then

          begin=i

          temp= 0

        Else

          temp=temp+h sum(i)

          End If

      Next i

          ks=“(“  ③  ”+Str(xy(2) ) +) ”    ‘开始位置

          js=“(“+Str(k+xy(1) -1) +” “+Str(xy(4) ) +”) ”    ‘结束位置

        Label 3.Caption=“最大子矩阵和为:”+Str(Sum)

        Label 4.Caption=“子矩阵中的元素个数为:”+Str(length*(xy(4) -xy(2) +1) )

        Label 5.Caption=“子矩阵位置为:”+ks+“,”+js

      End Sub

       ② ③ 

微信扫码预览、分享更方便