计算使用1 x m大小瓷砖铺设n x m大小地板的方法数量-yiteyi-C++库

给定一个尺寸为n x m的地板和尺寸为1 x m的瓷砖。问题是计算使用1 x m瓷砖铺设给定地板的方法的数量。瓷砖可以水平放置，也可以垂直放置。 n和m都是正整数，2<=m。例如：

null

Input : n = 2, m = 3Output : 1Only one combination to place two tiles of size 1 x 3 horizontallyon the floor of size 2 x 3. Input :  n = 4, m = 4Output : 21st combination:All tiles are placed horizontally2nd combination:All tiles are placed vertically.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

这个问题主要是一个更一般化的方法瓷砖问题 . 方法： 对于给定的n和m值，可以从以下关系式获得铺地板的方法数。

            |  1, 1 < = n < m count(n) = |  2, n = m            | count(n-1) + count(n-m), m < n

C++

                         // C++ implementation to count number of ways to                       
                         // tile a floor of size n x m using 1 x m tiles                       
                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         // function to count the total number of ways                       
                         int                                     countWays(                                     int                                     n,                                     int                                     m)                       
                         {                       
           
                                                 // table to store values                       
                                                 // of subproblems                       
                                                 int                                     count[n + 1];                       
                                                 count[0] = 0;                       
           
                                                 // Fill the table upto value n                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++) {                       
           
                                                 // recurrence relation                       
                                                 if                                     (i > m)                       
                                                 count[i] = count[i - 1] + count[i - m];                       
           
                                                 // base cases and for i = m = 1                       
                                                 else                                     if                                     (i < m || i == 1)                       
                                                 count[i] = 1;                       
           
                                                 // i = = m                       
                                                 else                       
                                                 count[i] = 2;                       
                                                 }                       
           
                                                 // required number of ways                       
                                                 return                                     count[n];                       
                         }                       
           
                         // Driver program to test above                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 7, m = 4;                       
                                                 cout <<                                     "Number of ways = "                       
                                                 << countWays(n, m);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation to count number                       
                         // of ways to tile a floor of size                       
                         // n x m using 1 x m tiles                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
           
                                                 // function to count the total number of ways                       
                                                 static                                     int                                     countWays(                                     int                                     n,                                     int                                     m)                       
                                                 {                       
                                                 // table to store values                       
                                                 // of subproblems                       
                                                 int                                     count[] =                                     new                                     int                                     [n +                                     1                                     ];                       
                                                 count[                                     0                                     ] =                                     0                                     ;                       
           
                                                 // Fill the table upto value n                       
                                                 int                                     i;                       
                                                 for                                     (i =                                     1                                     ; i <= n; i++) {                       
           
                                                 // recurrence relation                       
                                                 if                                     (i > m)                       
                                                 count[i] = count[i -                                     1                                     ] + count[i - m];                       
           
                                                 // base cases                       
                                                 else                                     if                                     (i < m || i ==                                     1                                     )                       
                                                 count[i] =                                     1                                     ;                       
           
                                                 // i = = m                       
                                                 else                       
                                                 count[i] =                                     2                                     ;                       
                                                 }                       
           
                                                 // required number of ways                       
                                                 return                                     count[n];                       
                                                 }                       
           
                                                 // Driver program                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     7                                     ;                       
                                                 int                                     m =                                     4                                     ;                       
                                                 System.out.println(                                     "Number of ways = "                       
                                                 + countWays(n, m));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

Python3

                         # Python implementation to                       
                         # count number of ways to                       
                         # tile a floor of size n x m                       
                         # using 1 x m tiles                       
           
                         def                                     countWays(n, m):                       
                                   
                                                 # table to store values                       
                                                 # of subproblems                       
                                                 count                                     =                                     []                       
                                                 for                                     i                                     in                                     range                                     (n                                     +                                     2                                     ):                       
                                                 count.append(                                     0                                     )                       
                                                 count[                                     0                                     ]                                     =                                     0                       
                                   
                                                 # Fill the table upto value n                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                   
                                                 # recurrence relation                       
                                                 if                                     (i > m):                       
                                                 count[i]                                     =                                     count[i                                     -                                     1                                     ]                                     +                                     count[i                                     -                                     m]                       
                                   
                                                 # base cases                       
                                                 elif                                     (i < m                                     or                                     i                                     =                                     =                                     1                                     ):                       
                                                 count[i]                                     =                                     1                       
           
                                                 # i = = m                       
                                                 else                                     :                       
                                                 count[i]                                     =                                     2                       
                                   
                                   
                                                 # required number of ways                       
                                                 return                                     count[n]                       
           
           
                         # Driver code                       
           
                         n                                     =                                     7                       
                         m                                     =                                     4                       
           
                         print                                     (                                     "Number of ways = "                                     , countWays(n, m))                       
           
                         # This code is contributed                       
                         # by Anant Agarwal.                       

C#

                         // C# implementation to count number                       
                         // of ways to tile a floor of size                       
                         // n x m using 1 x m tiles                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // function to count the total                       
                                                 // number of ways                       
                                                 static                                     int                                     countWays(                                     int                                     n,                                     int                                     m)                       
                                                 {                       
           
                                                 // table to store values                       
                                                 // of subproblems                       
                                                 int                                     [] count =                                     new                                     int                                     [n + 1];                       
                                                 count[0] = 0;                       
           
                                                 // Fill the table upto value n                       
                                                 int                                     i;                       
                                                 for                                     (i = 1; i <= n; i++) {                       
           
                                                 // recurrence relation                       
                                                 if                                     (i > m)                       
                                                 count[i] = count[i - 1]                       
                                                 + count[i - m];                       
           
                                                 // base cases and i = m = 1                       
                                                 else                                     if                                     (i < m || i == 1)                       
                                                 count[i] = 1;                       
           
                                                 // i = = m                       
                                                 else                       
                                                 count[i] = 2;                       
                                                 }                       
           
                                                 // required number of ways                       
                                                 return                                     count[n];                       
                                                 }                       
           
                                                 // Driver program                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 7;                       
                                                 int                                     m = 4;                       
           
                                                 Console.Write(                                     "Number of ways = "                       
                                                 + countWays(n, m));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by parashar.                       

PHP

                         <?php                       
                         // PHP implementation to count                       
                         // number of ways to tile a                       
                         // floor of size n x m using                       
                         // 1 x m tiles                       
           
                         // function to count the                       
                         // total number of ways                       
                         function                                     countWays(                                     $n                                     ,                                     $m                                     )                       
                         {                       
                                   
                                                 // table to store values                       
                                                 // of subproblems                       
                                                 $count                                     [0] = 0;                       
                                   
                                                 // Fill the table                       
                                                 // upto value n                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                   
                                                 // recurrence relation                       
                                                 if                                     (                                     $i                                     >                                     $m                                     )                       
                                                 $count                                     [                                     $i                                     ] =                                     $count                                     [                                     $i                                     - 1] +                       
                                                 $count                                     [                                     $i                                     -                                     $m                                     ];                       
                                   
                                                 // base cases                       
                                                 else                                     if                                     (                                     $i                                     <                                     $m                                     or                                     $i                                     == 1)                       
                                                 $count                                     [                                     $i                                     ] = 1;                       
           
                                                 // i = = m                       
                                                 else                       
                                                 $count                                     [                                     $i                                     ] = 2;                       
                                                 }                       
                                   
                                                 // required number of ways                       
                                                 return                                     $count                                     [                                     $n                                     ];                       
                         }                       
           
                                                 // Driver Code                       
                                                 $n                                     = 7;                       
                                                 $m                                     = 4;                       
                                                 echo                                     "Number of ways = "                                     , countWays(                                     $n                                     ,                                     $m                                     );                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript implementation to count number                       
                                                 // of ways to tile a floor of size                       
                                                 // n x m using 1 x m tiles                       
                                   
                                                 // function to count the total                       
                                                 // number of ways                       
                                                 function                                     countWays(n, m)                       
                                                 {                       
                                   
                                                 // table to store values                       
                                                 // of subproblems                       
                                                 let count =                                     new                                     Array(n + 1);                       
                                                 count[0] = 0;                       
                                   
                                                 // Fill the table upto value n                       
                                                 let i;                       
                                                 for                                     (i = 1; i <= n; i++) {                       
                                   
                                                 // recurrence relation                       
                                                 if                                     (i > m)                       
                                                 count[i] = count[i - 1] + count[i - m];                       
                                   
                                                 // base cases and i = m = 1                       
                                                 else                                     if                                     (i < m || i == 1)                       
                                                 count[i] = 1;                       
                                   
                                                 // i = = m                       
                                                 else                       
                                                 count[i] = 2;                       
                                                 }                       
                                   
                                                 // required number of ways                       
                                                 return                                     count[n];                       
                                                 }                       
                                   
                                                 let n = 7;                       
                                                 let m = 4;                       
           
                                                 document.write(                                     "Number of ways = "                                     + countWays(n, m));                       
           
                         // This code is contributed by rameshtravel07.                       
                         </script>                       

输出：

Number of ways = 5

时间复杂度：O（n）辅助空间：O（n）本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章