Рубрики

По заданной квадратной матрице nxn найдите сумму всех квадратов размера kxk.

По заданной квадратной матрице nxn найдите сумму всех квадратов размера kxk, где k меньше или равно n.

Примеры :

Input:
n = 5, k = 3
arr[][] = { {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:
       18  18  18
       27  27  27
       36  36  36


Input:
n = 3, k = 2
arr[][] = { {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9},
         };
Output:
       12  16
       24  28

Простое решение состоит в том, чтобы один за другим выбрать начальную точку (крайний левый верхний угол) из всех возможных квадратов. Как только начальная точка выбрана, вычислите сумму квадрата, начиная с выбранной начальной точки.

Ниже приводится реализация этой идеи.

C ++

// Простая программа на C ++ для нахождения суммы всех квадратов размера kxk
#include <iostream>

using namespace std;

  
// Размер данной матрицы
#define n 5

  
// Простая функция для нахождения суммы всех квадратов размера kxk
// в заданной квадратной матрице размером nxn

void printSumSimple(int mat[][n], int k)

{

   // k должно быть меньше или равно n

   if (k > n) return;

  

   // номер строки первой ячейки в текущем квадрате размера kxk

   for (int i=0; i<n-k+1; i++)

   {

      // столбец первой ячейки в текущем квадрате размера kxk

      for (int j=0; j<n-k+1; j++)

      {

          // Рассчитать и распечатать сумму текущего квадрата

          int sum = 0;

          for (int p=i; p<k+i; p++)

             for (int q=j; q<k+j; q++)

                 sum += mat[p][q];

           cout << sum << "  ";

      }

  

      // Разделитель строк для субквадрат, начиная со следующей строки

      cout << endl;

   }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int mat[n][n] = {{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 = 3;

    printSumSimple(mat, k);

    return 0;

}

Джава

// Простая Java-программа для поиска суммы всех
// квадраты размером kxk

class GFG

{

      

    // Размер данной матрицы

    static final int n = 5;

      

    // Простая функция для поиска суммы всех

    // субквадрат размером kxk в данном

    // квадратная матрица размером nxn

    static void printSumSimple(int mat[][], int k)

    {

  

        // k должно быть меньше или

        // равно n

        if (k > n) return;

          

        // номер строки первой ячейки в

        // текущий субквадрат размера kxk

        for (int i = 0; i < n-k+1; i++)

        {

              

            // столбец первой ячейки в текущем

            // площадь квадрата размера kxk

            for (int j = 0; j < n-k+1; j++)

            {

                  

                // Рассчитать и распечатать сумму

                // текущий квадрат

                int sum = 0;

                for (int p = i; p < k+i; p++)

                    for (int q = j; q < k+j; q++)

                        sum += mat[p][q];

  

                System.out.print(sum+ " ");

            }

          

            // Разделитель строк для субквадрат

            // начиная со следующей строки

            System.out.println();

        }

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String arg[])

    {

        int mat[][] = {{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 = 3;

        printSumSimple(mat, k);

    }

}

  
// Этот код предоставлен Anant Agarwal.

Python 3

# Простая программа на Python 3 для поиска суммы
# всех подквадрат размером kxk

  
# Размер данной матрицы

n = 5

  
# Простая функция, чтобы найти сумму всех
# квадратов размера kxk в данном
# квадратная матрица размера nxn

def printSumSimple(mat, k):

  

    # k должно быть меньше или равно n

    if (k > n):

        return

  

    # номер строки первой ячейки в текущем

    # площадь квадрата размера kxk

    for i in range(n - k + 1):

      

        # столбец первой ячейки в текущем

        # площадь квадрата размера kxk

        for j in range(n - k + 1):

              

            # Рассчитать и распечатать сумму

            # текущий квадрат

            sum = 0

            for p in range(i, k + i):

                for q in range(j, k + j):

                    sum += mat[p][q]

            print(sum, end = " ")

      

        # Линейный разделитель для квадратов

        # начиная со следующей строки

        print()

  
Код водителя

if __name__ == "__main__":

  

    mat = [[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]]

    k = 3

    printSumSimple(mat, k)

  
# Этот код предоставлен ita_c

C #

// Простая программа на C # для поиска суммы всех
// квадраты размером kxk

using System;

  

class GFG

{

    // Размер данной матрицы

    static int n = 5;

      

    // Простая функция для поиска суммы всех

    // субквадрат размером kxk в данном

    // квадратная матрица размером nxn

    static void printSumSimple(int [,]mat, int k)

    {

        // k должно быть меньше или

        // равно n

        if (k > n) return;

          

        // номер строки первой ячейки в

        // текущий субквадрат размера kxk

        for (int i = 0; i < n-k+1; i++)

        {

            // столбец первой ячейки в текущем

            // площадь квадрата размера kxk

            for (int j = 0; j < n-k+1; j++)

            {

                // Рассчитать и распечатать сумму

                // текущий квадрат

                int sum = 0;

                for (int p = i; p < k+i; p++)

                    for (int q = j; q < k+j; q++)

                        sum += mat[p,q];

  

                Console.Write(sum+ " ");

            }

          

            // Разделитель строк для субквадрат

            // начиная со следующей строки

            Console.WriteLine();

        }

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void Main()

    {

        int [,]mat = {{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 = 3;

        printSumSimple(mat, k);

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// Простая PHP-программа для поиска
// сумма всех квадратов размера
// кхк

  
// Размер данной матрицы

$n = 5;

  
// функция, чтобы найти сумму всех суб -
// квадраты размером kxk в заданном
// квадратная матрица размером nxn

function printSumSimple( $mat, $k)

{

    global $n;

      

    // k должно быть меньше чем

    // или равно n

    if ($k > $n) return;

      

    // номер строки первой ячейки в

    // текущий квадрат площади

    // кхк

    for($i = 0; $i < $n - $k + 1; $i++)

    {

          

        // столбец первой ячейки в

        // текущий квадрат площади

        // кхк

        for($j = 0; $j < $n - $k + 1; $j++)

        {

              

            // Рассчитать и распечатать сумму

            // текущий квадрат

            $sum = 0;

            for ($p = $i; $p < $k + $i; $p++)

                for ($q = $j; $q < $k + $j; $q++)

                    $sum += $mat[$p][$q];

            echo $sum , " ";

        }

      

        // Разделитель строк для субквадрат

        // начиная со следующей строки

        echo "\n";

    }

}

  

    // Код драйвера

    $mat = array(array(1, 1, 1, 1, 1),

                 array(2, 2, 2, 2, 2,),

                  array(3, 3, 3, 3, 3,),

                 array(4, 4, 4, 4, 4,),

                 array(5, 5, 5, 5, 5));

                      

    $k = 3;

    printSumSimple($mat, $k);

  
// Этот код предоставлен anuj_67.
?>

Выход:

  18  18  18
  27  27  27
  36  36  36

Временная сложность вышеуказанного решения составляет O (k 2 n 2 ). Мы можем решить эту проблему за O (n 2 ) раз, используя хитрое решение . Идея состоит в том, чтобы предварительно обработать данную квадратную матрицу. На этапе предварительной обработки вычислите сумму всех вертикальных полос размером kx 1 во временной квадратной матрице stripSum [] []. Как только у нас есть сумма всех вертикальных полос, мы можем вычислить сумму первого квадрата в строке как сумму первых k полос в этом ряду, а для оставшихся суб квадратов мы можем вычислить сумму за время O (1), удалив крайняя левая полоса предыдущего квадрата и добавление самой правой полосы нового квадрата.

Ниже приводится реализация этой идеи.

C ++

// Эффективная программа на C ++ для нахождения суммы всех подквадрат размером kxk
#include <iostream>

using namespace std;

  
// Размер данной матрицы
#define n 5

  
// Функция AO (n ^ 2) для нахождения суммы всех квадратов размера kxk
// в заданной квадратной матрице размером nxn

void printSumTricky(int mat[][n], int k)

{

   // k должно быть меньше или равно n

   if (k > n) return;

  

   // 1: предварительная обработка

   // Для хранения сумм всех полос размером kx 1

   int stripSum[n][n];

  

   // Перейти столбец за столбцом

   for (int j=0; j<n; j++)

   {

       // Вычисляем сумму первого прямоугольника kx 1 в этом столбце

       int sum = 0;

       for (int i=0; i<k; i++)

          sum += mat[i][j];

       stripSum[0][j] = sum;

  

       // Рассчитать сумму оставшихся прямоугольников

       for (int i=1; i<n-k+1; i++)

       {

            sum += (mat[i+k-1][j] - mat[i-1][j]);

            stripSum[i][j] = sum;

       }

   }

  

   // 2: РАСЧЕТНАЯ СУММА субквадрат с использованием stripSum [] []

   for (int i=0; i<n-k+1; i++)

   {

      // Вычисляем и печатаем сумму первого субквадрата в этой строке

      int sum = 0;

      for (int j = 0; j<k; j++)

           sum += stripSum[i][j];

      cout << sum << "  ";

  

      // Рассчитать сумму оставшихся квадратов в текущей строке

      // удаляем крайнюю левую полосу предыдущего квадрата и

      // добавление новой полосы

      for (int j=1; j<n-k+1; j++)

      {

         sum += (stripSum[i][j+k-1] - stripSum[i][j-1]);

         cout << sum << "  ";

      }

  

      cout << endl;

   }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int mat[n][n] = {{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 = 3;

    printSumTricky(mat, k);

    return 0;

}

Джава

// Эффективная Java-программа для поиска
// сумма всех подквадрат размером kxk

import java.io.*;

  

class GFG {

      
// Размер данной матрицы

static int n = 5;

  
// AO (n ^ 2) функция, чтобы найти сумму всех
// субквадрат размером kxk в данном
// квадратная матрица размером nxn

static void printSumTricky(int mat[][], int k) {

      

    // k должно быть меньше или равно n

    if (k > n)

    return;

  

    // 1: предварительная обработка

    // Для хранения сумм всех полос размером kx 1

    int stripSum[][] = new int[n][n];

  

    // Перейти столбец за столбцом

    for (int j = 0; j < n; j++) {

          

    // Вычисляем сумму первого kx 1

    // прямоугольник в этом столбце

    int sum = 0;

    for (int i = 0; i < k; i++)

        sum += mat[i][j];

    stripSum[0][j] = sum;

  

    // Рассчитать сумму оставшихся прямоугольников

    for (int i = 1; i < n - k + 1; i++) {

        sum += (mat[i + k - 1][j] - mat[i - 1][j]);

        stripSum[i][j] = sum;

    }

    }

  

    // 2: РАСЧЕТНАЯ СУММА СУБКРАТОВ

    // используя stripSum [] []

    for (int i = 0; i < n - k + 1; i++) {

          

    // Рассчитать и вывести сумму первого

    // подквадрат в этом ряду

    int sum = 0;

    for (int j = 0; j < k; j++)

        sum += stripSum[i][j];

    System.out.print(sum + " ");

  

    // Рассчитать сумму оставшихся квадратов

    // в текущей строке, удалив

    // крайняя левая полоса предыдущего квадрата

    // и добавление новой полосы

    for (int j = 1; j < n - k + 1; j++) {

        sum += (stripSum[i][j + k - 1] - stripSum[i][j - 1]);

        System.out.print(sum + " ");

    }

    System.out.println();

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

public static void main(String[] args)

{

    int mat[][] = {{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 = 3;

    printSumTricky(mat, k);

}
}

  
// Этот код предоставлен vt_m.

python3

# Эффективная программа Python3 для поиска суммы
# всех подквадрат размером kxk

  
# AO (n ^ 2) функция, чтобы найти сумму всех
# квадратов размера kxk в данном
# квадратная матрица размера nxn

def printSumTricky(mat, k):

    global n

      

    # k должно быть меньше или

    # равно n

    if k > n:

        return

  

    # 1: ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА

    # Для хранения сумм всех полос размером кх 1

    stripSum = [[None] * n for i in range(n)]

  

    # Перейти столбец за столбцом

    for j in range(n):

          

        # Рассчитать сумму первого кх 1

        # прямоугольник в этом столбце

        Sum = 0

        for i in range(k):

            Sum += mat[i][j] 

        stripSum[0][j] = Sum

  

        # Рассчитать сумму оставшихся прямоугольников

        for i in range(1, n - k + 1):

            Sum += (mat[i + k - 1][j] -

                    mat[i - 1][j]) 

            stripSum[i][j] = Sum

  

    # 2: РАСЧЕТНАЯ СУММА ПОДКВЕРДОВ

    # используя stripSum [] []

    for i in range(n - k + 1):

          

        # Рассчитать и prsum первого

        # subquare в этом ряду

        Sum = 0

        for j in range(k):

            Sum += stripSum[i][j] 

        print(Sum, end = " ")

  

        # Рассчитать сумму оставшихся квадратов

        # в текущей строке, удалив самый левый

        # полоса предыдущего подполя и добавление

        # новая полоса

        for j in range(1, n - k + 1):

            Sum += (stripSum[i][j + k - 1] -

                    stripSum[i][j - 1]) 

            print(Sum, end = " ")

  

        print()

  
Код водителя

n = 5

mat = [[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]] 

k = 3

printSumTricky(mat, k) 

  
# Этот код предоставлен PranchalK

C #

// Эффективная программа на C # для поиска
// сумма всех подквадрат размером kxk

using System;

class GFG {

      

    // Размер данной матрицы

    static int n = 5;

      

    // AO (n ^ 2) функция, чтобы найти сумму всех

    // субквадрат размером kxk в данном

    // квадратная матрица размером nxn

    static void printSumTricky(int [,]mat, int k) 

    {

          

        // k должно быть меньше или равно n

        if (k > n)

        return;

      

        // 1: предварительная обработка

        // Для хранения сумм всех полос

        // размер кх 1

        int [,]stripSum = new int[n,n];

      

        // Перейти столбец за столбцом

        for (int j = 0; j < n; j++)

        {

              

            // Вычисляем сумму первого kx 1

            // прямоугольник в этом столбце

            int sum = 0;

            for (int i = 0; i < k; i++)

                sum += mat[i,j];

                  

            stripSum[0,j] = sum;

          

            // Рассчитать сумму оставшихся

            // прямоугольники

            for (int i = 1; i < n - k + 1; i++)

            {

                sum += (mat[i + k - 1,j] 

                               - mat[i - 1,j]);

                stripSum[i,j] = sum;

            }

        }

      

        // 2: РАСЧЕТНАЯ СУММА СУБКРАТОВ

        // используя stripSum [] []

        for (int i = 0; i < n - k + 1; i++)

        {

              

            // Рассчитать и вывести сумму первого

            // подквадрат в этом ряду

            int sum = 0;

            for (int j = 0; j < k; j++)

                sum += stripSum[i,j];

                  

            Console.Write(sum + " ");

          

            // Рассчитать сумму оставшихся

            // квадраты в текущей строке

            // удаление самой левой полосы

            // предыдущего квадрата

            // и добавление новой полосы

            for (int j = 1; j < n - k + 1; j++) 

            {

                sum += (stripSum[i,j + k - 1] 

                           - stripSum[i,j - 1]);

                Console.Write(sum + " ");

            }

            Console.WriteLine();

        }

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void Main()

    {

        int [,]mat = {{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 = 3;

        printSumTricky(mat, k);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Эффективная программа PHP для
// найти сумму всех подквадрат
// размером кхк

  
// Размер данной матрицы

$n = 5;

  
// AO (n ^ 2) функция для поиска
// сумма всех квадратов
// размер кхк в заданном
// квадратная матрица размером nxn

function printSumTricky($mat, $k)

{

global $n;

  
// k должно быть меньше
// чем или равно n

if ($k > $n) return;

  
// 1: предварительная обработка
// Хранить суммы всех
// полоски размером кх 1

$stripSum = array(array());

  
// Перейти столбец за столбцом

for ($j = 0; $j < $n; $j++)

{

    // Рассчитать сумму первого

    // kx 1 прямоугольник в этом столбце

    $sum = 0;

    for ($i = 0; $i < $k; $i++)

        $sum += $mat[$i][$j];

    $stripSum[0][$j] = $sum;

  

    // Рассчитать сумму

    // оставшиеся прямоугольники

    for ($i = 1; $i < $n - $k + 1; $i++)

    {

            $sum += ($mat[$i + $k - 1][$j] - 

                          $mat[$i - 1][$j]);

            $stripSum[$i][$j] = $sum;

    }

}

  
// 2: РАСЧЕТНАЯ СУММА
// суб-квадраты с использованием stripSum [] []

for ($i = 0; $i < $n - $k + 1; $i++)

{

    // Рассчитать и распечатать сумму

    // первый субквадрат в этом ряду

    $sum = 0;

    for ($j = 0; $j < $k; $j++)

        $sum += $stripSum[$i][$j];

    echo $sum , " ";

  

    // Рассчитать сумму оставшихся

    // квадраты в текущей строке

    // удаление самой левой полосы

    // предыдущего квадрата и

    // добавление новой полосы

    for ($j = 1; $j < $n - $k + 1; $j++)

    {

        $sum += ($stripSum[$i][$j + $k - 1] - 

                 $stripSum[$i][$j - 1]);

        echo $sum , " ";

    }

  

    echo "\n";

}
}

  
// Код драйвера

$mat = array(array(1, 1, 1, 1, 1),

             array(2, 2, 2, 2, 2),

             array(3, 3, 3, 3, 3),

             array(4, 4, 4, 4, 4),

             array(5, 5, 5, 5, 5));

$k = 3;

printSumTricky($mat, $k);

  
// Этот код предоставлен anuj_67.
?>

Выход :

  18  18  18
  27  27  27
  36  36  36

Эта статья предоставлена Рахул Гупта . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

По заданной квадратной матрице nxn найдите сумму всех квадратов размера kxk.

0.00 (0%) 0 votes