C プログラムで指定されたサイズの最大和二乗部分行列を出力します。-C++-php.cn

C プログラムで指定されたサイズの最大和二乗部分行列を出力します。

WBOY

リリース： 2023-09-07 13:53:04

転載

1332 人が閲覧しました

NxN 行列が与えられた場合、行列 MxM のすべての要素の合計が最大になるように、M=1 となる MxM 部分行列を見つけます。行列 NxN への入力には、ゼロ、正の整数値、および負の整数値を含めることができます。

C プログラムで指定されたサイズの最大和二乗部分行列を出力します。

例

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

ログイン後にコピー

上記の問題は簡単な解決策で解決できます。NxN 行列全体を取得し、すべての可能な MxM 行列を見つけて次を求めることができます。それらの合計を計算し、最大の合計を持つ MxM 行列を出力します。この方法は単純ですが、時間計算量が O(N^2.M^2) であるため、時間計算量がより少ない方法を見つけようとします。

アルゴリズム

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

ログイン後にコピー

例

#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;
}

ログイン後にコピー