首页 >后端开发 >Golang >如何计算 1x1、1x2、2x1 瓷砖的可能组合有多少种可以填充 2 x N 地板?

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

WBOY
WBOY转载
2024-02-10 08:54:08439浏览

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

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

问题内容

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

任务是:

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

问题是:

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

当前的解决方案是:

  1. 1x1 总是可以填满 2 x n 层,因此可能的方式从 1 开始。
  2. 如果剩余楼层 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中文网其他相关文章!

声明:
本文转载于:stackoverflow.com。如有侵权,请联系admin@php.cn删除