Dado el largo , el ancho y la altura de un paralelepípedo. La tarea es dividir el cuboide dado en un número mínimo de cubos de modo que el tamaño de todos los cubos sea el mismo y la suma de los volúmenes de los cubos sea máxima.
Ejemplos:
Input : l = 2, b = 4, h = 6 Output : 2 6 A 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 3 Output : 1 6
En primer lugar, no se nos permite desperdiciar el volumen del paralelepípedo ya que necesitamos la suma máxima del volumen. Entonces, cada lado debe estar completamente dividido entre todos los cubos. Y dado que cada uno de los tres lados de los cubos es igual, cada lado del cuboide debe ser divisible por el mismo número, digamos x, que será el lado del cubo. Entonces, tenemos que maximizar esta x, que dividirá la longitud, la anchura y la altura dadas. Esta x será máxima solo si es el máximo común divisor de la longitud, la anchura y la altura dadas. Entonces, la longitud del cubo será GCD de la longitud, la anchura y la altura.
Ahora, para calcular el número de cubos, conocemos el volumen total del cuboide y podemos encontrar el volumen de un cubo (ya que el lado ya está calculado). Entonces, el número total de cubos es igual a (volumen del cuboide)/(volumen del cubo), es decir, (l * b * h)/(x * x * x).
A continuación se muestra la implementación de este enfoque:
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>
Producción:
2 6
Complejidad temporal: O(log 2 n), donde n es el límite superior de b y h.
Espacio Auxiliar: O(1)
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.