Cetak submatriks kuasa dua jumlah maksimum bagi saiz tertentu dalam program C

Diberi matriks NxN, cari submatriks MxM dengan M=1 supaya jumlah semua elemen matriks MxM adalah maksimum. Input kepada matriks NxN boleh mengandungi nilai sifar, integer positif dan integer negatif. . Kaedah ini mudah tetapi memerlukan kerumitan masa O(N^2.M^2), jadi kami cuba mencari kaedah dengan kerumitan masa yang kurang.

Algoritma

Input:
   {{1, 1, 1, 1, 1},
   {2, 2, 2, 2, 2},
   {3, 3, 3, 3, 3},
   {4, 4, 4, 4, 4},
   {5, 5, 5, 5, 5} }
Output:
   4 4
   5 5

Contoh

Start
Step 1 -> Declare Function void matrix(int arr[][size], int k)
   IF k>size
      Return
   Declare int array[size][size]
   Loop For int j=0 and j<size and j++
      Set sum=0
   Loop for int i=0 and i<k and i++
      Set sum=sum + arr[i][j]
   End
   Set array[0][j]=sum
   Loop For int i=1 and i<size-k+1 and i++
      Set sum=sum+(arr[i+k-1]][j]-arr[i-1][j]
      Set arrayi][j]=sum
   End
   Set int maxsum = INT_MIN and *pos = NULL
   Loop For int i=0 and i<size-k+1 and i++)
      Set int sum = 0
      Loop For int j = 0 and j<k and j++
         Set sum += array[i][j]
      End
      If sum > maxsum
         Set maxsum = sum
         Set pos = &(arr[i][0])
      End
      Loop For int j=1 and j<size-k+1 and j++
         Set sum += (array[i][j+k-1] - array[i][j-1])
         IF sum > maxsum
            Set maxsum = sum
            Set pos = &(arr[i][j])
         End
      End
   End
   Loop For int i=0 and i<k and i++
      Loop For int j=0 and j<k and j++
         Print *(pos + i*size + j)
      End
      Print </p><p>
   End
Step 2 -> In main()
   Declare int array[size][size] = {{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3}, {4, 4, 4, 4, 4}, {5, 5, 5, 5, 5}}
   Declare int k = 2
   Call matrix(array, k)
Stop

Output

Jika kita menjalankan program di atas maka ia akan menghasilkan output berikut

#include <bits/stdc++.h>
using namespace std;
#define size 5
void matrix(int arr[][size], int k){
   if (k > size) return;
      int array[size][size];
   for (int j=0; j<size; j++){
      int sum = 0;
      for (int i=0; i<k; i++)
         sum += arr[i][j];
         array[0][j] = sum;
      for (int i=1; i<size-k+1; i++){
         sum += (arr[i+k-1][j] - arr[i-1][j]);
         array[i][j] = sum;
      }
   }
   int maxsum = INT_MIN, *pos = NULL;
   for (int i=0; i<size-k+1; i++){
      int sum = 0;
      for (int j = 0; j<k; j++)
         sum += array[i][j];
      if (sum > maxsum){
         maxsum = sum;
         pos = &(arr[i][0]);
      }
      for (int j=1; j<size-k+1; j++){
         sum += (array[i][j+k-1] - array[i][j-1]);
         if (sum > maxsum){
            maxsum = sum;
            pos = &(arr[i][j]);
         }
      }
   }
   for (int i=0; i<k; i++){
      for (int j=0; j<k; j++)
         cout << *(pos + i*size + j) << " ";
      cout << endl;
   }
}
int main(){
   int array[size][size] = {
      {1, 1, 1, 1, 1},
      {2, 2, 2, 2, 2},
      {3, 3, 3, 3, 3},
      {4, 4, 4, 4, 4},
      {5, 5, 5, 5, 5},
   };
   int k = 2;
   matrix(array, k);
   return 0;
}

Atas ialah kandungan terperinci Cetak submatriks kuasa dua jumlah maksimum bagi saiz tertentu dalam program C. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!