Dada un área de NXM . Tienes el número infinito de fichas de tamaño 2 i X 2 i , donde i = 0, 1, 2,… y así sucesivamente. La tarea es encontrar el número mínimo de mosaicos necesarios para llenar el área dada con mosaicos.
Ejemplos:
Input : N = 5, M = 6. Output : 9 Area of 5 X 6 can be covered with minimum 9 tiles. 6 tiles of 1 X 1, 2 tiles of 2 X 2, 1 tile of 4 X 4.
Input : N = 10, M = 5. Output : 14
La idea es dividir el área dada en el 2 i X 2 i más cercano .
Dividamos el problema en casos:
Caso 1: si N es impar y M es par, llena la fila o columna con M número de fichas 1 X 1. Luego cuente el número mínimo de mosaicos para el tamaño N/2 XM/2 del área. De manera similar, si M es impar y N es par, agregue N a nuestra respuesta y encuentre un número mínimo de mosaicos para el área N/2 XM/2.
Caso 2: si N y M son impares, complete una fila y una columna, de modo que sume N + M – 1 a la respuesta y encuentre la cantidad mínima de mosaicos necesarios para llenar el área N/2 XM/2.
Caso 3:Si N y M son pares, calcule el número mínimo de mosaicos necesarios para llenar el área con N/2 XM/2 área. Porque reducir a la mitad ambas dimensiones no cambia la cantidad de mosaicos requeridos.
A continuación se muestra la implementación de este enfoque:
C++
#include<bits/stdc++.h> using namespace std; int minTiles(int n, int m) { // base case, when area is 0. if (n == 0 || m == 0) return 0; // If n and m both are even, calculate tiles for n/2 x m/2 // Halving both dimensions doesn't change the number of tiles else if (n%2 == 0 && m%2 == 0) return minTiles(n/2, m/2); // If n is even and m is odd // Use a row of 1x1 tiles else if (n%2 == 0 && m%2 == 1) return (n + minTiles(n/2, m/2)); // If n is odd and m is even // Use a column of 1x1 tiles else if (n%2 == 1 && m%2 == 0) return (m + minTiles(n/2, m/2)); // If n and m are odd // add row + column number of tiles else return (n + m - 1 + minTiles(n/2, m/2)); } // Driven Program int main() { int n = 5, m = 6; cout << minTiles(n, m) << endl; return 0; }
Java
// Java code for Minimum tiles of // sizes in powers of two to cover // whole area class GFG { static int minTiles(int n, int m) { // base case, when area is 0. if (n == 0 || m == 0) return 0; // If n and m both are even, // calculate tiles for n/2 x m/2 // Halving both dimensions doesn't // change the number of tiles else if (n % 2 == 0 && m % 2 == 0) return minTiles(n / 2, m / 2); // If n is even and m is odd // Use a row of 1x1 tiles else if (n % 2 == 0 && m % 2 == 1) return (n + minTiles(n / 2, m / 2)); // If n is odd and m is even // Use a column of 1x1 tiles else if (n % 2 == 1 && m % 2 == 0) return (m + minTiles(n / 2, m / 2)); // If n and m are odd // add row + column number of tiles else return (n + m - 1 + minTiles(n / 2, m / 2)); } // Driver code public static void main (String[] args) { int n = 5, m = 6; System.out.println(minTiles(n, m)); } } // This code is contributed by Anant Agarwal.
Python3
def minTiles(n, m): # base case, when area is 0. if n == 0 or m == 0: return 0 # If n and m both are even, calculate # tiles for n/2 x m/2 # Halving both dimensions doesn't # change the number of tiles elif n%2 == 0 and m%2 == 0: return minTiles(int(n/2), int(m/2)) # If n is even and m is odd # Use a row of 1x1 tiles elif n % 2 == 0 and m % 2 == 1: return (n + minTiles(int(n/2), int(m/2))) # If n is odd and m is even # Use a column of 1x1 tiles elif n % 2 == 1 and m % 2 == 0: return (m + minTiles(int(n/2), int(m/2))) # If n and m are odd add # row + column number of tiles else: return (n + m - 1 + minTiles(int(n/2), int(m/2))) # Driven Program n = 5 m = 6 print (minTiles(n, m)) # This code is contributed # by Shreyanshi Arun.
C#
// C# code for Minimum tiles of // sizes in powers of two to cover // whole area using System; class GFG { static int minTiles(int n, int m) { // base case, when area is 0. if (n == 0 || m == 0) return 0; // If n and m both are even, // calculate tiles for n/2 x m/2 // Halving both dimensions doesn't // change the number of tiles else if (n % 2 == 0 && m % 2 == 0) return minTiles(n / 2, m / 2); // If n is even and m is odd // Use a row of 1x1 tiles else if (n % 2 == 0 && m % 2 == 1) return (n + minTiles(n / 2, m / 2)); // If n is odd and m is even // Use a column of 1x1 tiles else if (n % 2 == 1 && m % 2 == 0) return (m + minTiles(n / 2, m / 2)); // If n and m are odd // add row + column number of tiles else return (n + m - 1 + minTiles(n / 2, m / 2)); } // Driver code public static void Main() { int n = 5, m = 6; Console.WriteLine(minTiles(n, m)); } } // This code is contributed by vt_m.
PHP
<?php // PHP program for Minimum tiles of // sizes in powers of two to cover // whole area function minTiles($n, $m) { // base case, when area is 0. if ($n == 0 or $m == 0) return 0; // If n and m both are even, // calculate tiles for n/2 x m/2 // Halving both dimensions doesn't // change the number of tiles else if ($n % 2 == 0 and $m % 2 == 0) return minTiles($n / 2, $m / 2); // If n is even and m is odd // Use a row of 1x1 tiles else if ($n % 2 == 0 and $m % 2 == 1) return floor($n + minTiles($n / 2, $m / 2)); // If n is odd and m is even // Use a column of 1x1 tiles else if ($n % 2 == 1 and $m % 2 == 0) return ($m + minTiles($n / 2, $m / 2)); // If n and m are odd // add row + column number of tiles else return floor($n + $m - 1 + minTiles($n / 2, $m / 2)); } // Driver Code $n = 5; $m = 6; echo minTiles($n, $m); // This code is contributed by anuj_67. ?>
Javascript
<script> // JavaScript code for Minimum tiles of // sizes in powers of two to cover // whole area function minTiles(n, m) { // base case, when area is 0. if (n == 0 || m == 0) return 0; // If n and m both are even, // calculate tiles for n/2 x m/2 // Halving both dimensions doesn't // change the number of tiles else if (n % 2 == 0 && m % 2 == 0) return minTiles((n / 2),(m / 2)); // If n is even and m is odd // Use a row of 1x1 tiles else if (n % 2 == 0 && m % 2 == 1) return (n + minTiles(Math.floor(n / 2), Math.floor(m / 2))); // If n is odd and m is even // Use a column of 1x1 tiles else if (n % 2 == 1 && m % 2 == 0) return (m + minTiles(Math.floor(n / 2), Math.floor(m / 2))); // If n and m are odd // add row + column number of tiles else return (n + m - 1 + minTiles(Math.floor(n / 2), Math.floor(m / 2))); } // Driver Code let n = 5, m = 6; document.write(Math.floor(minTiles(n, m))); </script>
Producción:
9
Análisis de Complejidad:
Complejidad de tiempo: O(log(min(n,m))/log(2)), donde n y m son dimensiones de mosaicos.
Espacio auxiliar: O(log(min(n,m))/log(2)), porque estamos agregando un elemento a la pila durante cada llamada de recurrencia.
Este artículo es una contribución de Anuj Chauhan (anuj0503) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA