如何计算 1x1、1x2、2x1 瓷砖的可能组合有多少种可以填充 2 x N 地板？-Golang-PHP中文网

如何计算 1x1、1x2、2x1 瓷砖的可能组合有多少种可以填充 2 x N 地板？

WBOY

发布： 2024-02-10 08:54:08

转载

674人浏览过

如何计算 1x1、1x2、2x1 瓷砖的可能组合有多少种可以填充 2 x n 地板？

php小编新一将为大家解答一个有趣而烧脑的问题：如何计算 1x1、1x2、2x1 瓷砖的可能组合有多少种可以填充 2 x N 地板？这个问题涉及到组合数学和动态规划的知识，通过分析和推导，我们可以得出一个简洁而有效的计算方法。接下来，让我们一起来探索这个问题的答案吧！

问题内容

我刚刚做了一个技术测试，并对这个任务感到困惑。我的目标是了解如何解决这个“覆盖地板”问题。老实说，我不知道从哪里开始。

任务是：

有一层 2 x n 层。
我们有 1x1、1x2、2x1 的瓷砖来填充地板。

问题是：

solution(1) 预期输出为 2，实际输出为 2。
但是，solution(2) 预期输出为 7，实际输出为 3。

当前的解决方案是：

1x1 总是可以填满 2 x n 层，因此可能的方式从 1 开始。
如果剩余楼层 mod 2 为 0，则可能的方式增加 1。

当前解决方案的问题是它不区分 1x2 和 2x1 块。因此对于 solution(2) 实际输出是 3 而不是 7。

代码

package main

import "fmt"

// Solution is your solution code.
func Solution(n int) int {
    possibleWays := 1

    floorArea := 2 * n
    // Your code starts here.

    for i := floorArea - 1; i >= 0; i-- {
        residualFloorArea := floorArea - i
        fmt.Println(i, residualFloorArea)
        if residualFloorArea%2 == 0 {
            fmt.Println("punch")
            possibleWays += 1
        }
    }

    return possibleWays
}

func main() {
    fmt.Println(Solution(1))
    fmt.Println("next")
    fmt.Println(Solution(2))
}

登录后复制

解决方法

更具描述性且详尽的尝试：

调用覆盖2xn网格的方式数量为x_n，覆盖2xn+1网格的方式数量为y_n，覆盖2xn+2网格的方式数量为z_n。

基本案例：

x_0 = 1，y_0 = 1，z_0 = 2
x_1 = 2，y_1 = 3，z_1 = 5

归纳步骤，n >=2：

-- --
      |  |  |
 -- -- -- --  ...
|xx|  |  |  |
 -- -- -- --

登录后复制

考虑 2xn + 2 网格的最左边的单元格，如果它被 1x1 瓦片覆盖，那么剩下的就是 2xn + 1 网格，否则，它被 1x2 瓦片覆盖，剩下的就是 2xn 网格。因此，

z_n = x_n + y_n

-- --
   |  |  |
 -- -- --  ...
|xx|  |  |
 -- -- --

登录后复制

考虑 2xn + 1 网格的最左边的单元格，如果它被 1x1 瓦片覆盖，剩余的将是 2xn 网格，否则，它被 1x2 瓦片覆盖，剩余的将是 2x(n- 1) + 1 格。因此，

y_n = x_n + y_(n-1)

-- --
|xx|  |
 -- --  ...
|  |  |
 -- --

登录后复制

考虑 2xn 网格的左上角，如果它被 1x1 的图块覆盖，则剩余的将是 2x(n-1) + 1 个网格，如果它被 1x2 的图块覆盖，则剩余的将是一个2x(n-2) + 2 网格，否则，它被 2x1 瓦片覆盖，剩余的将是 2x(n-1) 网格。因此：

x_n = y_(n-1) + z_(n-2) + x_(n-1)

将 z_n 替换为 x_n + y_n，我们有：

x_n = x_(n-1) + x_(n-2) + y_(n-1) + y_(n-2)
y_n = x_n + y_(n-1)

现在，只需迭代计算每个值：

package main

import "fmt"

// Solution is your solution code.
func Solution(n int) int {
    if n == 0 {
        return 1
    } else if n == 1 {
        return 2
    }

    x := make([]int, n + 1)
    y := make([]int, n + 1)
    x[0] = 1
    y[0] = 1
    x[1] = 2
    y[1] = 3

    for i := 2; i <= n; i++ {
        x[i] = x[i - 1] + x[i - 2] + y[i - 1] + y[i - 2]
        y[i] = x[i] + y[i - 1]
    }

    return x[n]
}

func main() {
    fmt.Println(Solution(1))
    fmt.Println("next")
    fmt.Println(Solution(2))
}

登录后复制

您可以不使用切片来完成此操作，但这更容易理解。游乐场演示

以上就是如何计算 1x1、1x2、2x1 瓷砖的可能组合有多少种可以填充 2 x N 地板？的详细内容，更多请关注php中文网其它相关文章！