本文概述
- 建议:在继续解决方案之前, 请先在"实践"上解决它。
- C ++
- Java
- Python3
- C#
- 的PHP
- C ++
- Java
- Python3
- C#
例子 :
Input:m = 2, n = 2Output: 5There are 4 squares of size 1x1 + 1 square of size 2x2.Input: m = 4, n = 3Output: 20There 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
通过以上解释, 我们知道m x m矩阵中的平方数为m(m + 1)(2m + 1)/ 6
当我们添加一列时, 即m x(m + 1)矩阵中的平方数是多少?
当我们添加一列时, 增加的平方数为m +(m-1)+…+ 3 + 2 +1
[尺寸为1×1的m平方+尺寸为2×2的(m-1)平方+…+尺寸为m x m的1平方]
等于m(m + 1)/ 2
因此, 当我们添加(n-m)列时, 增加的平方总数为(n-m)* m(m + 1)/ 2。
因此, 平方总数为m(m + 1)(2m + 1)/ 6 +(n-m)* 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++ program to count squares
// in a rectangle of size m x n
#include<
iostream>
using namespace std;
// Returns count of all squares
// in a rectangle of size m x n
int countSquares( int m, int n)
{
// If n is smaller, swap m and n
if (n <
m)
swap(m, n);
// Now n is greater dimension, // apply formula
return m * (m + 1) * (2 * m + 1) /
6 + (n - m) * m *(m + 1) / 2;
}// Driver Code
int main()
{
int m = 4, n = 3;
cout <
<
"Count of squares is "
<
<
countSquares(m, n);
}
Java
// Java program to count squares
// in a rectangle of size m x nclass GFG
{
// Returns count of all squares
// in a rectangle of size m x n
static int countSquares( int m, int n)
{
// If n is smaller, swap m and n
if (n <
m)
{
// swap(m, n)
int temp = m;
m = n;
n = temp;
}// Now n is greater dimension, // apply formula
return m * (m + 1 ) * ( 2 * m + 1 ) /
6 + (n - m) * m * (m + 1 ) / 2 ;
}// Driver Code
public static void main(String[] args)
{
int m = 4 , n = 3 ;
System.out.println( "Count of squares is " +
countSquares(m, n));
}
}
Python3
# Python3 program to count squares
# in a rectangle of size m x n# Returns count of all squares
# in a rectangle of size m x n
def countSquares(m, n):# If n is smaller, swap m and n
if (n <
m):
temp = m
m = n
n = temp# Now n is greater dimension, # apply formula
return ((m * (m + 1 ) * ( 2 * m + 1 ) /
6 + (n - m) * m * (m + 1 ) / 2 ))# Driver Code
if __name__ = = '__main__' :
m = 4
n = 3
print ( "Count of squares is "
, countSquares(m, n))# This code is contributed by mits.
C#
// C# program to count squares in a rectangle
// of size m x n
using System;
class GFG {// Returns count of all squares in a
// rectangle of size m x n
static int countSquares( int m, int n)
{
// If n is smaller, swap m and n
if (n <
m)
{
// swap(m, n)
int temp = m;
m = n;
n = temp;
}// Now n is greater dimension, apply
// formula
return m * (m + 1) * (2 * m + 1) / 6 +
(n - m) * m * (m + 1) / 2;
}// Driver method
public static void Main()
{
int m = 4, n = 3;
Console.WriteLine( "Count of squares is "
+ countSquares(m, n));
}
}//This code is contributed by vt_m.
的PHP
<
?php
// PHP program to count squares
// in a rectangle of size m x n// Returns count of all squares
// in a rectangle of size m x n
function countSquares( $m , $n )
{
// If n is smaller, swap m and n
if ( $n <
$m )
list( $m , $n ) = array ( $n , $m );
// Now n is greater dimension, // apply formula
return $m * ( $m + 1) * (2 * $m + 1) /
6 + ( $n - $m ) * $m * ( $m + 1) / 2;
}// Driver Code
$m = 4;
$n = 3;
echo ( "Count of squares is " . countSquares( $m , $n ));
// This code is contributed by Ajit.
?>
输出:
Count of Squares is 20
【算法题(如何计算矩形中的正方形数())】替代解决方案:
让我们取m = 2, n = 3;
边1的平方数将是6, 因为将存在两种情况, 一种是沿水平(2)的1单元边的正方形, 第二种是沿垂直(3)的1单元边的正方形。给我们2 * 3 = 6平方
当边为2个单位时, 一种情况将是仅沿一个位置水平放置2个单位的边的正方形, 而第二个情况将为垂直放置两个位置的情况。所以平方数= 2
所以我们可以推断出
大小为1 * 1的平方数将为m * n
大小2 * 2的平方数将为(n-1)(m-1)
因此, 大小为n的平方数将为1 *(m-n + 1)
总平方数的最终公式为
n *(n + 1)(3m-n + 1)/ 6
C ++
// C++ program to count squares
// in a rectangle of size m x n
#include<
iostream>
using namespace std;
// Returns count of all squares
// in a rectangle of size m x n
int countSquares( int m, int n)
{// If n is smaller, swap m and n
if (n <
m)
{
int temp = m;
m = n;
n = temp;
}// Now n is greater dimension, // apply formula
return n * (n + 1) * (3 * m - n + 1) / 6;
}// Driver Code
int main()
{
int m = 4, n = 3;
cout <
<
"Count of squares is "
<
<
countSquares(m, n);
}// This code is contributed by 29AjayKumar
Java
// Java program to count squares
// in a rectangle of size m x n
import java.util.*;
class GFG
{// Returns count of all squares
// in a rectangle of size m x n
static int countSquares( int m, int n)
{// If n is smaller, swap m and n
if (n <
m)
{
int temp = m;
m = n;
n = temp;
}// Now n is greater dimension, // apply formula
return n * (n + 1 ) * ( 3 * m - n + 1 ) / 6 ;
}// Driver Code
public static void main(String[] args)
{
int m = 4 ;
int n = 3 ;
System.out.print( "Count of squares is " +
countSquares(m, n));
}
}// This code is contributed by 29AjayKumar
Python3
# Python3 program to count squares
# in a rectangle of size m x n # Returns count of all squares
# in a rectangle of size m x n
def countSquares(m, n): # If n is smaller, swap m and n
if (n <
m):
temp = m
m = n
n = temp # Now n is greater dimension, # apply formula
return n * (n + 1 ) * ( 3 * m - n + 1 ) / / 6# Driver Code
if __name__ = = '__main__' :
m = 4
n = 3
print ( "Count of squares is" , countSquares(m, n)) # This code is contributed by AnkitRai01
C#
// C# program to count squares
// in a rectangle of size m x n
using System;
class GFG
{// Returns count of all squares
// in a rectangle of size m x n
static int countSquares( int m, int n)
{// If n is smaller, swap m and n
if (n <
m)
{
int temp = m;
m = n;
n = temp;
}// Now n is greater dimension, // apply formula
return n * (n + 1) * (3 * m - n + 1) / 6;
}// Driver Code
public static void Main(String[] args)
{
int m = 4;
int n = 3;
Console.Write( "Count of squares is " +
countSquares(m, n));
}
}// This code is contributed by Rajput-Ji
输出:
Count of Squares is 20
感谢Pranav提供此替代解决方案。
如果发现任何不正确的地方, 或者你想分享有关上述主题的更多信息, 请发表评论
推荐阅读
- 算法题(如何检测检测链表中的循环())
- 如何计算从mXn矩阵的左上角到右下角所有可能的路径()
- jQuery如何使用fadeToggle()方法(代码示例)
- 如何使用CSS创建波浪背景(代码示例)
- 在PHP数组中如何返回两个日期之间的所有日期()
- TypeScript数字valueOf()方法用法介绍
- JavaScript赋值运算符深入学习指南
- 雨林木风win8纯净版64位安装版最新系统推荐
- win7专业版原版最新系统推荐