Рубрики

Подсчитать количество квадратов в прямоугольнике

Учитывая прямоугольник amxn, сколько в нем квадратов?

Примеры :

Input:  m = 2, n = 2
Output: 5
There are 4 squares of size 1x1 + 
          1 square of size 2x2.

Input: m = 4, n = 3
Output: 20
There are 12 squares of size 1x1 + 
          6 squares of size 2x2 + 
          2 squares of size 3x3.

Давайте сначала решим эту проблему для m = n, т. Е. Для квадрата:

Для m = n = 1 выход: 1

Для m = n = 2 выведите: 4 + 1 [4 размера 1 × 1 + 1 размера 2 × 2]

Для m = n = 3 выведите: 9 + 4 + 1 [4 размера 1 × 1 + 4 размера 2 × 2 + 1 размера 3 × 3]

Для m = n = 4 выведите 16 + 9 + 4 + 1 [16 размера 1 × 1 + 9 размера 2 × 2 + 4 размера 3 × 3 + 1 размера 4 × 4]

В общем, это, кажется, n ^ 2 + (n-1) ^ 2 +… 1 = n (n + 1) (2n + 1) / 6

Давайте решим эту проблему, когда m не может быть равно n:

Предположим, что m <= n

Из приведенного выше объяснения мы знаем, что число квадратов в матрице amxm равно m (m + 1) (2m + 1) / 6.

Что происходит, когда мы добавляем столбец, т. Е. Каково количество квадратов в матрице mx (m + 1)?

Когда мы добавляем столбец, количество квадратов увеличивается: m + (m-1) +… + 3 + 2 + 1
[m квадратов размером 1 × 1 + (m-1) квадратов размером 2 × 2 +… + 1 квадрат размером mxm]

Что равно m (m + 1) / 2

Поэтому, когда мы добавляем (нм) столбцы, общее количество квадратов увеличивается (нм) * м (м + 1) / 2.

Таким образом, общее количество квадратов составляет m (m + 1) (2m + 1) / 6 + (nm) * m (m + 1) / 2.

Используя ту же логику, мы можем доказать, что n <= m.

Итак, в общем,

Total number of squares = m x (m+1) x (2m+1)/6 + 
                          (n-m) x m x (m+1)/2 

when n is larger dimension

,

Используя вышеприведенную логику для прямоугольника, мы также можем доказать, что число квадратов в квадрате равно n (n + 1) (2n + 1) / 6.

Ниже приведена реализация вышеприведенной формулы.

C ++

// C ++ программа для подсчета квадратов
// в прямоугольнике размером mxn
#include<iostream>

using namespace std;

  
// Возвращает количество всех квадратов
// в прямоугольнике размером mxn

int countSquares(int m, int n)

{
// Если n меньше, поменяйте местами m и n

if (n < m)

    swap(m, n);

  
// Теперь n больше измерения,
// применить формулу

return m * (m + 1) * (2 * m + 1) / 

     6 + (n - m) * m *(m + 1) / 2;

}

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

int main()

{

int m = 4, n = 3;

cout << "Count of squares is "

     << countSquares(m, n);

}

Джава

// Java-программа для подсчета квадратов
// в прямоугольнике размером mxn

  

class GFG

{

    // Возвращает количество всех квадратов

    // в прямоугольнике размером mxn

    static int countSquares(int m, 

                            int n)

    {

    // Если n меньше, поменяйте местами m и n

    if (n < m)

    {

        // своп (м, н)

        int temp = m;

        m = n;

        n = temp;

    }

          

      

    // Теперь n больше измерения,

    // применить формулу

    return m * (m + 1) * (2 * m + 1) / 

        6 + (n - m) * m * (m + 1) / 2;

    }

      

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

    public static void main(String[] args) 

    {

        int m = 4, n = 3;

        System.out.println("Count of squares is "

                            countSquares(m, n));

    }

}

python3

# Python3 программа для подсчета квадратов
# в прямоугольнике размером mxn

  
# Возвращает количество всех квадратов
# в прямоугольнике размером mxn

def countSquares(m, n):

      

    # Если n меньше, поменяйте местами m и n

    if(n < m):

        temp = m

        m = n

        n = temp

          

    # Теперь n больше измерения,

    # применить формулу

    return ((m * (m + 1) * (2 * m + 1) / 

           6 + (n - m) * m * (m + 1) / 2))

  
Код водителя

if __name__=='__main__':

    m = 4 

    n = 3

    print("Count of squares is "

         ,countSquares(m, n))

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

C #

// C # программа для подсчета квадратов в прямоугольнике
// размером mxn

using System;

  

class GFG {

      

    // Возвращает количество всех квадратов в

    // прямоугольник размером mxn

    static int countSquares(int m, int n)

    {

    // Если n меньше, поменяйте местами m и n

    if (n < m)

    {

        // своп (м, н)

        int temp = m;

        m = n;

        n = temp;

    }

              

    // Теперь n больше, применить

    // формула

    return m * (m + 1) * (2 * m + 1) / 6 + 

               (n - m) * m * (m + 1) / 2;

    }

      

    // Метод драйвера

    public static void Main() 

    {

        int m = 4, n = 3;

          

        Console.WriteLine("Count of squares is " 

                          + countSquares(m, n));

    }

}

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

PHP

<?php
// PHP программа для подсчета квадратов
// в прямоугольнике размером mxn

  
// Возвращает количество всех квадратов
// в прямоугольнике размером mxn

function countSquares($m, $n)

{

    // Если n меньше, поменяйте местами m и n

    if ($n < $m)

        list($m, $n) = array($n, $m);

      

    // Теперь n больше измерения,

    // применить формулу

    return $m * ($m + 1) * (2 * $m + 1) / 

       6 + ($n - $m) * $m * ($m + 1) / 2;

}

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

$m = 4; $n = 3;

echo("Count of squares is " . countSquares($m, $n));

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


Выход :

Count of Squares is 20

Альтернативное решение:
Возьмем m = 2, n = 3;
Число квадратов на стороне 1 будет равно 6, так как будет два случая, один из которых представляет собой квадраты сторон в 1 единицу по горизонтали (2), а второй — как квадраты сторон в 1 единицу по вертикали (3). что дает нам 2 * 3 = 6 квадратов.

Когда сторона составляет 2 единицы, один случай будет как квадраты стороны 2 единиц вдоль только одного места по горизонтали, а второй случай как два места по вертикали. Так что число квадратов = 2

Таким образом, мы можем сделать вывод, что
Количество квадратов размером 1 * 1 будет m * n

Количество квадратов размером 2 * 2 будет (n-1) (м-1)

Таким образом, число квадратов размером n будет равно 1 * (m-n + 1)

Окончательная формула для общего числа квадратов будет n * (n + 1) (3m-n + 1) / 6

python3

# Python3 программа для подсчета квадратов
# в прямоугольнике размером mxn

  
# Возвращает количество всех квадратов
# в прямоугольнике размером mxn

def countSquares(m, n): 

      

    # Если n меньше, поменяйте местами m и n

    if(n < m): 

        temp =

        m =

        n = temp 

          

    # Теперь n больше измерения,

    # применить формулу

    return n * (n + 1) * (3 * m - n + 1) // 6

  
Код водителя

if __name__=='__main__'

    m = 4

    n = 3

    print("Count of squares is",

           countSquares(m, n)) 

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

Выход :

Count of Squares is 20

Спасибо Pranav за предоставление этого альтернативного решения.

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

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

Подсчитать количество квадратов в прямоугольнике

0.00 (0%) 0 votes