Bagaimana untuk mengira berapa banyak kemungkinan kombinasi jubin 1x1, 1x2, 2x1 boleh mengisi lantai 2 x N?

editor php Xinyi akan menjawab soalan yang menarik dan membakar otak untuk semua orang: Bagaimana untuk mengira berapa banyak kemungkinan kombinasi jubin 1x1, 1x2, 2x1 boleh mengisi lantai 2 x N? Masalah ini melibatkan pengetahuan matematik gabungan dan pengaturcaraan dinamik Melalui analisis dan derivasi, kita boleh menghasilkan kaedah pengiraan yang mudah dan berkesan. Seterusnya, mari kita terokai jawapan kepada soalan ini bersama-sama!

Kandungan soalan

Saya baru buat ujian teknikal dan keliru dengan tugasan ini. Matlamat saya adalah untuk memahami cara menyelesaikan masalah "lantai berbumbung" ini. Sejujurnya saya tak tahu nak mula dari mana.

Misinya ialah:

1. Ada lapisan 2 x n.
2. Kami mempunyai jubin 1x1, 1x2, 2x1 untuk memenuhi lantai.

Soalannya ialah:

1. solution(1) Output yang dijangkakan ialah 2, output sebenar ialah 2.
2. Walau bagaimanapun, solution(2) output yang dijangkakan ialah 7 dan output sebenar ialah 3.

Penyelesaian semasa ialah:

1. 1x1 sentiasa boleh mengisi 2 x n lapisan, jadi cara yang mungkin bermula dari 1.
2. Jika baki tingkat mod 2 ialah 0, kemungkinan cara dinaikkan sebanyak 1.

Masalah penyelesaian semasa ialah ia tidak membezakan antara blok 1x2 dan 2x1. Jadi untuk solution(2) output sebenar ialah 3 bukannya 7.

Kod

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))
}

Penyelesaian

Percubaan yang lebih deskriptif dan teliti:

Bilangan cara untuk memanggil grid 2xn ialah x_n, bilangan cara untuk menutup grid 2xn+1 ialah y_n, dan bilangan cara untuk menutup grid 2xn+2 ialah z_n.

Kes asas:

• x_0 = 1, y_0 = 1, z_0 = 2
• x_1 = 2, y_1 = 3, z_1 = 5

Langkah induksi, n >=2:

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

Pertimbangkan sel paling kiri grid 2xn + 2, jika ia dilitupi oleh jubin 1x1, maka selebihnya ialah grid 2xn + 1, jika tidak, ia dilitupi oleh jubin 1x2, dan selebihnya ialah grid 2xn. Oleh itu,

z_n = x_n + y_n

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

Pertimbangkan sel paling kiri grid 2xn + 1, jika ia dilitupi oleh jubin 1x1, bakinya akan menjadi grid 2xn, jika tidak, ia dilindungi oleh jubin 1x2, bakinya akan menjadi 2x(n- 1) + 1 grid. Oleh itu,

y_n = x_n + y_(n-1)

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

Pertimbangkan sudut kiri atas grid 2xn, jika ia dilitupi oleh jubin 1x1, bakinya akan menjadi 2x(n-1) + 1 grid, jika ia dilitupi oleh jubin 1x2, bakinya akan menjadi 2x( n-2) + 2 grid, jika tidak, ia dilindungi oleh jubin 2x1 dan bakinya akan menjadi grid 2x(n-1). Oleh itu:

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

Menggantikan z_n dengan x_n + y_n, kami mempunyai:

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

Sekarang, hanya lelaran melalui setiap nilai:

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))
}

Anda boleh melakukan ini tanpa menggunakan kepingan, tetapi ia lebih mudah difahami. Demo Taman Permainan

Atas ialah kandungan terperinci Bagaimana untuk mengira berapa banyak kemungkinan kombinasi jubin 1x1, 1x2, 2x1 boleh mengisi lantai 2 x N?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!