算法设计：矩形最大面积的正方形数量

本文概述

• C ++
• Java
• Python3
• C#
• 的PHP

给定边m和n的矩形。将矩形切成较小的相同块, 以使每个块都是一个正方形, 其边长应尽可能大, 而矩形的剩余部分应没有。这样的正方形的打印其数量。

例子：

Input: 9 6
Output: 6
Rectangle can be cut into squares of size 3.

Input: 4 2
Output: 2
Rectangle can be cut into squares of size 2.

方法：

任务是将矩形切成边长为s的正方形, 而矩形的剩余部分不留, 因此

s

必须将两者分开

米

和

ñ

。同样, 正方形的边应尽可能大, 因此, s应该是m和n的最大公约数。

所以,

s = gcd(m, n)

.

为了找到矩形被切成的正方形数, 要做的任务是将矩形的面积除以大小为s的正方形的面积。

C ++

// C++ code for calculating the
// number of squares
#include <bits/stdc++.h>
using namespace std;
  
// Function to find number of squares
int NumberOfSquares( int x, int y)
{
     // Here in built c++ gcd function is used
     int s = __gcd(x, y);
  
     int ans = (x * y) / (s * s);
  
     return ans;
}
  
// Driver code
int main()
{
     int m = 385, n = 60;
  
     // Call the function NumberOfSquares
     cout << NumberOfSquares(m, n);
  
     return 0;
}

Java

// Java code for calculating 
// the number of squares
import java.io.*;
  
class GFG
{
     // Recursive function to
     // return gcd of a and b
     static int __gcd( int a, int b)
     {
         // Everything divides 0 
         if (a == 0 || b == 0 )
         return 0 ;
      
         // base case
         if (a == b)
             return a;
      
         // a is greater
         if (a > b)
             return __gcd(a - b, b);
         return __gcd(a, b - a);
     } 
  
  
// Function to find 
// number of squares
static int NumberOfSquares( int x, int y)
{
     // Here in built c++ 
     // gcd function is used
     int s = __gcd(x, y);
  
     int ans = (x * y) / (s * s);
  
     return ans;
}
  
// Driver Code
public static void main (String[] args) 
{
     int m = 385 , n = 60 ;
  
     // Call the function
     // NumberOfSquares
     System.out.println(NumberOfSquares(m, n));
}
}
  
// This code is contributed by anuj_67.

Python3

# Python3 code for calculating 
# the number of squares
  
# Recursive function to
# return gcd of a and b
def __gcd(a, b):
      
     # Everything divides 0 
     if (a = = 0 or b = = 0 ):
         return 0 ;
  
     # base case
     if (a = = b):
         return a;
  
     # a is greater
     if (a > b):
         return __gcd(a - b, b);
     return __gcd(a, b - a);
  
# Function to find 
# number of squares
def NumberOfSquares(x, y):
      
     # Here in built PHP
     # gcd function is used
     s = __gcd(x, y);
  
     ans = (x * y) / (s * s);
  
     return int (ans);
  
# Driver Code
m = 385 ;
n = 60 ;
  
# Call the function
# NumberOfSquares
print (NumberOfSquares(m, n));
  
# This code is contributed 
# by mit

C#

// C# code for calculating 
// the number of squares
using System;
  
class GFG
{
      
     // Recursive function to
     // return gcd of a and b
     static int __gcd( int a, int b)
     {
         // Everything divides 0 
         if (a == 0 || b == 0)
         return 0;
      
         // base case
         if (a == b)
             return a;
      
         // a is greater
         if (a > b)
             return __gcd(a - b, b);
         return __gcd(a, b - a);
     } 
  
  
// Function to find 
// number of squares
static int NumberOfSquares( int x, int y)
{
     // Here in built c++ 
     // gcd function is used
     int s = __gcd(x, y);
  
     int ans = (x * y) / 
               (s * s);
  
     return ans;
}
  
// Driver Code
static public void Main ()
{
int m = 385, n = 60;
  
// Call the function
// NumberOfSquares
Console.WriteLine(NumberOfSquares(m, n));
}
}
  
// This code is contributed by ajit

的PHP

<?php
// PHP code for calculating 
// the number of squares
  
// Recursive function to
// return gcd of a and b
function __gcd( $a , $b )
{
     // Everything divides 0 
     if ( $a == 0 || $b == 0)
     return 0;
  
     // base case
     if ( $a == $b )
         return $a ;
  
     // a is greater
     if ( $a > $b )
         return __gcd( $a - $b , $b );
     return __gcd( $a , $b - $a );
} 
  
// Function to find 
// number of squares
function NumberOfSquares( $x , $y ) 
{
     // Here in built PHP
     // gcd function is used
     $s = __gcd( $x , $y );
  
     $ans = ( $x * $y ) / 
            ( $s * $s );
  
     return $ans ;
}
  
// Driver Code
$m = 385;
$n = 60;
  
// Call the function
// NumberOfSquares
echo (NumberOfSquares( $m , $n ));
  
// This code is contributed 
// by akt_mit
?>

输出如下：

924

---