算法设计（最小正方形可均匀切割矩形） _数据结构

本文概述

建议：在继续解决方案之前, 请先在{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 Codeif __name__ = = '__main__' : l = 4 w = 6 ans = countRectangles(l, w) print ( int (ans))# this code is contributed by # SURENDRA_GANGWAR

// 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 ?>

【算法设计（最小正方形可均匀切割矩形）】输出如下：