将长方体分成立方体，使体积之和最大-yiteyi-C++库

考虑到长 , 宽度 , 身高长方体的。任务是将给定的长方体划分为最小数量的立方体，以便所有立方体的大小相同，且立方体体积之和最大。例如：

null

Input : l = 2, b = 4, h = 6Output : 2 6A cuboid of length 2, breadth 4 and height 6 can be divided into 6 cube of side equal to 2.Volume of cubes = 6*(2*2*2) = 6*8 = 48.Volume of cuboid = 2*4*6 = 48.Input : 1 2 3Output : 1 6

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

首先，我们不允许浪费长方体的体积，因为我们需要最大的体积总和。所以，每一边都应该被所有立方体完全分割。因为立方体的三条边都是相等的，所以立方体的每一条边都需要被相同的数整除，比如x，这就是立方体的边。所以，我们必须最大化这个x，它将除以给定的长度，宽度和高度。只有当x是给定长度、宽度和高度的最大公约数时，x才是最大值。因此，立方体的长度将是长度、宽度和高度的GCD。现在，为了计算立方体的数量，我们知道长方体的总体积，并且可以找到一个立方体的体积（因为边已经计算过了）。所以，立方体的总数等于（长方体的体积）/（立方体的体积），即（l*b*h）/（x*x*x）。以下是该方法的实施：

C++

                         // CPP program to find optimal way to break                       
                         // cuboid into cubes.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Print the maximum side and no of cube.                       
                         void                                     maximizecube(                                     int                                     l,                                     int                                     b,                                     int                                     h)                       
                         {                       
                                                 // GCD to find side.                       
                                                 int                                     side = __gcd(l, __gcd(b, h));                       
           
                                                 // dividing to find number of cubes.                       
                                                 int                                     num = l / side;                       
                                                 num = (num * b / side);                       
                                                 num = (num * h / side);                       
           
                                                 cout << side <<                                     " "                                     << num << endl;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     l = 2, b = 4, h = 6;                       
           
                                                 maximizecube(l, b, h);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // JAVA Code for Divide cuboid into cubes                       
                         // such that sum of volumes is maximum                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     gcd(                                     int                                     m,                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n ==                                     0                                     )                       
                                                 return                                     m;                       
                                                 else                                     if                                     (n > m)                       
                                                 return                                     gcd(n,m);                       
                                                 else                       
                                                 return                                     gcd(n, m % n);                       
                                                 }                       
                                   
                                                 // Print the maximum side and no                       
                                                 //     of cube.                       
                                                 static                                     void                                     maximizecube(                                     int                                     l,                                     int                                     b,                       
                                                 int                                     h)                       
                                                 {                       
                                                 // GCD to find side.                       
                                                 int                                     side = gcd(l, gcd(b, h));                       
                                   
                                                 // dividing to find number of cubes.                       
                                                 int                                     num = l / side;                       
                                                 num = (num * b / side);                       
                                                 num = (num * h / side);                       
                                   
                                                 System.out.println( side +                                     " "                                     + num);                       
                                                 }                       
                                   
                                                 /* Driver program  */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     l =                                     2                                     , b =                                     4                                     , h =                                     6                                     ;                       
                                                 maximizecube(l, b, h);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Arnav Kr. Mandal.                       

Python3

                         # Python3 code to find optimal way to break                       
                         # cuboid into cubes.                       
                         from                                     fractions                                     import                                     gcd                       
           
                         # Print the maximum side and no of cube.                       
                         def                                     maximizecube( l , b , h ):                       
           
                                                 # GCD to find side.                       
                                                 side                                     =                                     gcd(l, gcd(b, h))                       
                                   
                                                 # dividing to find number of cubes.                       
                                                 num                                     =                                     int                                     (l                                     /                                     side)                       
                                                 num                                     =                                     int                                     (num                                     *                                     b                                     /                                     side)                       
                                                 num                                     =                                     int                                     (num                                     *                                     h                                     /                                     side)                       
                                   
                                                 print                                     (side, num)                       
           
                         # Driver code                       
                         l                                     =                                     2                       
                         b                                     =                                     4                       
                         h                                     =                                     6                       
           
                         maximizecube(l, b, h)                       
           
                         # This code is contributed by "Sharad_Bhardwaj".                       

C#

                         // C# Code for Divide cuboid into cubes                       
                         // such that sum of volumes is maximum                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     gcd(                                     int                                     m,                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n == 0)                       
                                                 return                                     m;                       
                                                 else                                     if                                     (n > m)                       
                                                 return                                     gcd(n,m);                       
                                                 else                       
                                                 return                                     gcd(n, m % n);                       
                                                 }                       
                                   
                                                 // Print the maximum side and no                       
                                                 // of cube.                       
                                                 static                                     void                                     maximizecube(                                     int                                     l,                                     int                                     b,                       
                                                 int                                     h)                       
                                                 {                       
                                                 // GCD to find side.                       
                                                 int                                     side = gcd(l, gcd(b, h));                       
                                   
                                                 // dividing to find number of cubes.                       
                                                 int                                     num = l / side;                       
                                                 num = (num * b / side);                       
                                                 num = (num * h / side);                       
                                   
                                                 Console.WriteLine( side +                                     " "                                     + num);                       
                                                 }                       
                                   
                                                 /* Driver program */                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     l = 2, b = 4, h = 6;                       
                                                 maximizecube(l, b, h);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to find optimal way                       
                         // to break cuboid into cubes.                       
           
                         // Recursive function to                       
                         // return gcd of a and b                       
                         function                                     __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                                     ) ;                       
                         }                       
           
           
                         // Print the maximum side and no of cube.                       
                         function                                     maximizecube(                                     $l                                     ,                                     $b                                     ,                                     $h                                     )                       
                         {                       
                                   
                                                 // GCD to find side.                       
                                                 $side                                     = __gcd(                                     $l                                     , __gcd(                                     $b                                     ,                                     $h                                     ));                       
           
                                                 // dividing to find number of cubes.                       
                                                 $num                                     =                                     $l                                     /                                     $side                                     ;                       
                                                 $num                                     = (                                     $num                                     *                                     $b                                     /                                     $side                                     );                       
                                                 $num                                     = (                                     $num                                     *                                     $h                                     /                                     $side                                     );                       
           
                                                 echo                                     $side                                     ,                                     " "                                     ,                                     $num                                     ;                       
                         }                       
           
                                                 // Driver code                       
                                                 $l                                     = 2;                       
                                                 $b                                     = 4;                       
                                                 $h                                     = 6;                       
                                                 maximizecube(                                     $l                                     ,                                     $b                                     ,                                     $h                                     );                       
                                   
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program for Divide cuboid into cubes                       
                         // such that sum of volumes is maximum                       
                                                 function                                     gcd(m, n)                       
                                                 {                       
                                                 if                                     (n == 0)                       
                                                 return                                     m;                       
                                                 else                                     if                                     (n > m)                       
                                                 return                                     gcd(n,m);                       
                                                 else                       
                                                 return                                     gcd(n, m % n);                       
                                                 }                       
                                   
                                                 // Print the maximum side and no                       
                                                 //     of cube.                       
                                                 function                                     maximizecube(l, b, h)                       
                                                 {                       
                                   
                                                 // GCD to find side.                       
                                                 let side = gcd(l, gcd(b, h));                       
                                   
                                                 // dividing to find number of cubes.                       
                                                 let num = l / side;                       
                                                 num = (num * b / side);                       
                                                 num = (num * h / side);                       
                                   
                                                 document.write( side +                                     " "                                     + num);                       
                                                 }                       
                                   
                         // Driver code                       
                                                 let l = 2, b = 4, h = 6;                       
                                                 maximizecube(l, b, h);                       
                                   
                                                 // This code is contributed by sanjoy_62.                       
                         </script>                       

输出：

2 6

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章