Wie berechnet man, wie viele mögliche Kombinationen von 1x1-, 1x2- und 2x1-Fliesen es gibt, um einen 2 x N-Boden zu füllen?

php-Redakteur Dieses Problem erfordert Kenntnisse der kombinatorischen Mathematik und der dynamischen Programmierung. Durch Analyse und Ableitung können wir eine einfache und effektive Berechnungsmethode entwickeln. Lassen Sie uns als Nächstes gemeinsam die Antwort auf diese Frage untersuchen!

Frageninhalt

Ich habe gerade einen technischen Test durchgeführt und bin verwirrt über diese Aufgabe. Mein Ziel ist es zu verstehen, wie dieses Problem des „verdeckten Bodens“ gelöst werden kann. Ich weiß ehrlich gesagt nicht, wo ich anfangen soll.

Die Mission ist:

1. Es gibt eine 2 x n-Schicht.
2. Wir haben 1x1, 1x2, 2x1 Fliesen zum Füllen des Bodens.

Die Frage ist:

1. solution(1) Erwartete Ausgabe ist 2, tatsächliche Ausgabe ist 2.
2. Allerdings solution(2) beträgt die erwartete Ausgabe 7 und die tatsächliche Ausgabe 3.

Die aktuelle Lösung lautet:

1. 1x1 kann immer 2 x n Schichten füllen, der mögliche Weg beginnt also bei 1.
2. Wenn Mod 2 der verbleibenden Stockwerke 0 ist, werden die möglichen Wege um 1 erhöht.

Das Problem mit der aktuellen Lösung besteht darin, dass sie nicht zwischen 1x2- und 2x1-Blöcken unterscheidet. Für solution(2) beträgt die tatsächliche Ausgabe also 3 statt 7.

Code

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

Lösung

Ein aussagekräftigerer und gründlicherer Versuch:

Die Anzahl der Methoden, die zur Abdeckung des 2xn+1-Gitters aufgerufen werden, ist x_n, die Anzahl der Methoden, die das 2xn+1-Gitter abdecken, ist y_n, und die Anzahl der Methoden, die das 2xn+2-Gitter abdecken, ist z_n.

Grundfall:

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

Induktionsschritt, n >=2:

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

Betrachten Sie die Zelle ganz links in einem 2xn + 2-Gitter. Wenn sie von einer 1x1-Kachel bedeckt ist, ist der Rest ein 2xn + 1-Gitter. Andernfalls ist sie von einer 1x2-Kachel bedeckt und der Rest ist ein 2xn-Gitter. Deshalb

z_n = x_n + y_n

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

Betrachten Sie die Zelle ganz links in einem 2xn + 1-Gitter. Wenn sie von einer 1x1-Kachel bedeckt ist, ist der Rest ein 2xn-Gitter. Andernfalls ist sie von einer 1x2-Kachel bedeckt, der Rest ist 2x(n- 1) + 1 Netz. Deshalb

y_n = x_n + y_(n-1)

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

Betrachten Sie die obere linke Ecke eines 2xn-Gitters. Wenn sie von einer 1x1-Kachel bedeckt ist, ist der Rest 2x(n-1) + 1 Gitter. Wenn sie von einer 1x2-Kachel bedeckt ist, ist der Rest ein 2x( n-2) + 2 Gitter, andernfalls wird es von 2x1 Kacheln bedeckt und der Rest ist 2x(n-1) Gitter. Deshalb:

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

Wenn wir z_n durch x_n + y_n ersetzen, erhalten wir:

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

Jetzt durchlaufen Sie einfach jeden Wert:

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

Sie können dies tun, ohne Slices zu verwenden, aber es ist einfacher zu verstehen. Spielplatz-Demo

Das obige ist der detaillierte Inhalt vonWie berechnet man, wie viele mögliche Kombinationen von 1x1-, 1x2- und 2x1-Fliesen es gibt, um einen 2 x N-Boden zu füllen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!