Nos dan una cuadrícula N*M, imprimamos el número de rectángulos en ella.
Ejemplos:
Input : N = 2, M = 2 Output : 9 There are 4 rectangles of size 1 x 1. There are 2 rectangles of size 1 x 2 There are 2 rectangles of size 2 x 1 There is one rectangle of size 2 x 2. Input : N = 5, M = 4 Output : 150 Input : N = 4, M = 3 Output: 60
Hemos discutido contar el número de cuadrados en una cuadrícula anxm . Obtengamos
una fórmula para el número de rectángulos.
Si la cuadrícula es 1×1, hay 1 rectángulo.
Si la cuadrícula es de 2×1, habrá 2 + 1 = 3 rectángulos
. Si la cuadrícula es de 3×1, habrá 3 + 2 + 1 = 6 rectángulos.
podemos decir que para N*1 habrá N + (N-1) + (n-2) … + 1 = (N)(N+1)/2 rectángulos
Si le sumamos una columna más a N×1, primero tendremos tantos rectángulos en la segunda columna como en la primera,
y luego tendremos el mismo número de rectángulos de 2×M.
Así que N×2 = 3 (N)(N+1)/2
Después de deducir esto podemos decir
Para N*M tendremos (M)(M+1)/2 (N)(N+1)/2 = M(M+1)(N)(N+1)/4
Entonces, la fórmula para el total de rectángulos será M(M+1)(N)(N+1)/4
.
Lógica combinatoria:
La cuadrícula N*M se puede representar como (N+1) líneas verticales y (M+1) líneas horizontales.
En un rectángulo, necesitamos dos horizontales distintas y dos verticales distintas.
Entonces, siguiendo la lógica de las matemáticas combinatorias, podemos elegir 2 líneas verticales y 2 líneas horizontales para formar un rectángulo. Y el número total de estas combinaciones es el número de rectángulos posibles en la cuadrícula.
Número total de rectángulos en la cuadrícula N*M: N+1 C 2 * M+1 C 2 = (N*(N+1)/2!)*(M*(M+1)/2!) = N* (N+1)*M*(M+1)/4
C++
// C++ program to count number of rectangles // in a n x m grid #include <bits/stdc++.h> using namespace std; int rectCount(int n, int m) { return (m * n * (n + 1) * (m + 1)) / 4; } /* driver code */ int main() { int n = 5, m = 4; cout << rectCount(n, m); return 0; }
Java
// JAVA Code to count number of // rectangles in N*M grid import java.util.*; class GFG { public static long rectCount(int n, int m) { return (m * n * (n + 1) * (m + 1)) / 4; } /* Driver program to test above function */ public static void main(String[] args) { int n = 5, m = 4; System.out.println(rectCount(n, m)); } } // This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to count number # of rectangles in a n x m grid def rectCount(n, m): return (m * n * (n + 1) * (m + 1)) // 4 # Driver code n, m = 5, 4 print(rectCount(n, m)) # This code is contributed by Anant Agarwal.
C#
// C# Code to count number of // rectangles in N*M grid using System; class GFG { public static long rectCount(int n, int m) { return (m * n * (n + 1) * (m + 1)) / 4; } // Driver program public static void Main() { int n = 5, m = 4; Console.WriteLine(rectCount(n, m)); } } // This code is contributed by Anant Agarwal.
PHP
<?php // PHP program to count // number of rectangles // in a n x m grid function rectCount($n, $m) { return ($m * $n * ($n + 1) * ($m + 1)) / 4; } // Driver Code $n = 5; $m = 4; echo rectCount($n, $m); // This code is contributed // by ajit ?>
Javascript
<script> // Javascript Code to count number // of rectangles in N*M grid function rectCount(n, m) { return parseInt((m * n * (n + 1) * (m + 1)) / 4, 10); } let n = 5, m = 4; document.write(rectCount(n, m)); </script>
Producción:
150
Complejidad del tiempo: O(1)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Pranav . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA