瓷砖问题-yiteyi-C++库

给定一块“2 x n”板和大小为“2 x 1”的瓷砖，计算使用2 x 1瓷砖平铺给定板的方法数。瓷砖可以水平放置，即1 x 2瓷砖，也可以垂直放置，即2 x 1瓷砖。

null

例如：

输入： n=4

产出：5

说明：

对于2×4板，有5种方法

所有4个垂直（1路）

全部4个水平（1路）

2个垂直方向和2个水平方向（3个方向）

输入： n=3

输出： 3.

说明：

我们需要3块瓷砖来铺设2 x 3的木板。

我们可以使用以下方法来平铺电路板

将所有3块瓷砖垂直放置。

垂直放置1块瓷砖，水平放置剩余2块瓷砖（2种方式）

tilingproblem

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

实施——

让“count（n）”作为在“2xn”网格上放置瓷砖的方法的计数，我们有以下两种方法来放置第一个瓷砖。 1）如果我们垂直放置第一个磁贴，问题将减少到“计数（n-1）” 2）如果我们水平放置第一块瓷砖，那么第二块瓷砖也必须水平放置。因此，问题归结为“计数（n-2）” 因此，计数（n）可以如下所示。

   count(n) = n if n = 1 or n = 2   count(n) = count(n-1) + count(n-2)

以下是上述方法的代码：

C++

                         // C++ program to count the                       
                         // no. of ways to place 2*1 size                       
                         // tiles in 2*n size board.                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     getNoOfWays(                                     int                                     n)                       
                         {                       
                                                 // Base case                       
                                                 if                                     (n <= 2)                       
                                                 return                                     n;                       
           
                                                 return                                     getNoOfWays(n - 1) + getNoOfWays(n - 2);                       
                         }                       
           
                         // Driver Function                       
                         int                                     main()                       
                         {                       
                                                 cout << getNoOfWays(4) << endl;                       
                                                 cout << getNoOfWays(3);                       
                                                 return                                     0;                       
                         }                       

Python3

                         # Python3 program to count the                       
                         # no. of ways to place 2*1 size                       
                         # tiles in 2*n size board.                       
                         def                                     getNoOfWays(n):                       
                                   
                                                 # Base case                       
                                                 if                                     n <                                     =                                     2                                     :                       
                                                 return                                     n                       
           
                                                 return                                     getNoOfWays(n                                     -                                     1                                     )                                     +                                     getNoOfWays(n                                     -                                     2                                     )                       
           
                         # Driver Code                       
                         print                                     (getNoOfWays(                                     4                                     ))                       
                         print                                     (getNoOfWays(                                     3                                     ))                       
           
                         # This code is contributed by Kevin Joshi                       

Javascript

                         <script>                       
                         // JavaScript program to count the                       
                         // no. of ways to place 2*1 size                       
                         // tiles in 2*n size board.                       
           
                         function                                     getNoOfWays(n)                       
                         {                       
                                                 // Base case                       
                                                 if                                     (n <= 2)                       
                                                 return                                     n;                       
                                   
                                                 return                                     getNoOfWays(n - 1) + getNoOfWays(n - 2);                       
                         }                       
           
                         // Driver Function                       
                         document.write(getNoOfWays(4));                       
                         document.write(getNoOfWays(3));                       
           
                         // This code is contributed by shinjanpatra                       
                         </script>                       

输出：

以上的反复只是斐波那契数表示我们可以在O（logn）时间内找到第n个Fibonacci数，下面是找到第n个Fibonacci数的所有方法。 https://youtu.be/NyICqRtePVs https://youtu.be/U9ylW7NsHlI n’th Fibonacci数的不同求法 . 计算使用1 x m大小瓷砖铺设n x m大小地板的方法数量本文由Saurabh Jain撰稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

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

THE END

技术文章