算法设计：最小正方形可均匀切割矩形

本文概述

• 建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
• C ++
• Java
• Python3
• C#
• 的PHP

给定一个矩形板, 长度为l, 宽度为w。我们需要将此工作表划分为正方形工作表, 以使正方形工作表的数量尽可能少。

例子：

输入：l = 4 w = 6输出：6我们可以形成边长为1个单位的正方形, 但是正方形的数目将是24, 这不是最小的。如果我们使边为2的正方形, 则我们有6个正方形。这是我们所需要的答案。同样, 我们也无法将边3设为正方形, 如果我们选择3作为正方形, 那么整张床单就无法转换成等长的糖衣。输入：l = 3 w = 5输出：15

推荐：请尝试使用{IDE}首先, 在继续解决方案之前。

正方形边的最佳长度等于GCD两个数

C ++

// CPP program to find minimum number of
// squares to make a given rectangle.
#include <bits/stdc++.h>
using namespace std;
  
int countRectangles( int l, int w)
{
     // if we take gcd(l, w), this
     // will be largest possible
     // side for suare, hence minimum
     // number of square.
     int squareSide = __gcd(l, w);
  
     // Number of squares.
     return (l * w) / (squareSide * squareSide);
}
  
// Driver code
int main()
{
     int l = 4, w = 6;
     cout << countRectangles(l, w) << endl;
     return 0;
}

Java

// Java program to find minimum number of
// squares to make a given rectangle.
  
class GFG{
static int __gcd( int a, int b) {
    if (b== 0 ) return a;
    return __gcd(b, a%b);
}
static int countRectangles( int l, int w)
{
     // if we take gcd(l, w), this
     // will be largest possible
     // side for suare, hence minimum
     // number of square.
     int squareSide = __gcd(l, w);
  
     // Number of squares.
     return (l * w) / (squareSide * squareSide);
}
  
// Driver code
public static void main(String[] args)
{
     int l = 4 , w = 6 ;
     System.out.println(countRectangles(l, w));
}
}
// This code is contributed by mits

Python3

# Python3 code to find minimum number of
# squares to make a given rectangle.
  
import math 
  
def countRectangles(l, w):
  
     # if we take gcd(l, w), this
     # will be largest possible
     # side for suare, hence minimum
     # number of square.
     squareSide = math.gcd(l, w)
      
     # Number of squares.
     return (l * w) / (squareSide * squareSide)
  
# Driver Code
          
if __name__ = = '__main__' :
     l = 4
     w = 6
     ans = countRectangles(l, w)
     print ( int (ans))
  
# this code is contributed by
# SURENDRA_GANGWAR

C#

// C# program to find minimum number of
// squares to make a given rectangle.
  
class GFG{
static int __gcd( int a, int b) {
if (b==0) return a;
return __gcd(b, a%b);
}
static int countRectangles( int l, int w)
{
     // if we take gcd(l, w), this
     // will be largest possible
     // side for suare, hence minimum
     // number of square.
     int squareSide = __gcd(l, w);
  
     // Number of squares.
     return (l * w) / (squareSide * squareSide);
}
  
// Driver code
public static void Main()
{
     int l = 4, w = 6;
     System.Console.WriteLine(countRectangles(l, w));
}
}
// This code is contributed by mits

的PHP

<?php 
// PHP program to find minimum number 
// of squares to make a given rectangle.
  
function gcd( $a , $b )
{
     return $b ? gcd( $b , $a % $b ) : $a ;
}
  
function countRectangles( $l , $w )
{
     // if we take gcd(l, w), this
     // will be largest possible
     // side for suare, hence minimum
     // number of square.
     $squareSide = gcd( $l , $w );
  
     // Number of squares.
     return ( $l * $w ) / ( $squareSide * 
                         $squareSide );
}
  
// Driver code
$l = 4;
$w = 6;
echo countRectangles( $l , $w ) . "\n" ; 
  
// This code is contributed 
// by ChitraNayal
?>

输出如下：

6

---