覆盖整个区域的最小瓷砖尺寸为二次方-yiteyi-C++库

给定一个面积 N×M .你有无限多个大小为2的瓷砖 ^我 x2 ^我，其中i=0，1，2等等。任务是找到用瓷砖填充给定区域所需的最小瓷砖数量。例如：

null

Input : N = 5, M = 6.Output : 9Area 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.

图片[1]-覆盖整个区域的最小瓷砖尺寸为二次方-yiteyi-C++库

Input : N = 10, M = 5.Output : 14

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

其想法是将给定区域划分为最接近的2个区域 ^我 x2 ^我 . 让我们把问题分成几个案例： 案例1： 如果N为奇数，M为偶数，则用M个1 X 1瓷砖填充行或列。然后计算该区域N/2 X M/2大小的最小瓷砖数量。类似地，如果M是奇数，N是偶数，将N加到我们的答案中，找到N/2xm/2区域的最小瓷砖数。 案例2： 如果N和M都是奇数，则填充一行和一列，因此在答案中添加N+M–1，并找到填充N/2x M/2区域所需的最小瓷砖数量。 案例3： 如果N和M都是偶数，则计算用N/2 X M/2面积填充该区域所需的最小瓷砖数量。因为将两个尺寸减半不会改变所需的瓷砖数量。以下是该方法的实施情况：

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                       
                                                 # Halfing 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>                       

输出：

本文由 Anuj Chauhan（anuj0503） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章