Comment calculer combien de combinaisons possibles de carreaux 1x1, 1x2, 2x1 peuvent remplir un sol 2 x N ?

l'éditeur php Xinyi répondra à une question intéressante et brûlante pour tout le monde : Comment calculer combien de combinaisons possibles de carreaux 1x1, 1x2, 2x1 peuvent remplir un sol 2 x N ? Ce problème implique la connaissance des mathématiques combinatoires et de la programmation dynamique. Grâce à l'analyse et à la dérivation, nous pouvons proposer une méthode de calcul simple et efficace. Ensuite, explorons ensemble la réponse à cette question !

Contenu de la question

Je viens de faire un test technique et je suis confus quant à cette tâche. Mon objectif est de comprendre comment résoudre ce problème de « sol couvert ». Honnêtement, je ne sais pas par où commencer.

La mission est :

1. Il y a une couche 2 x n.
2. Nous avons des carreaux 1x1, 1x2, 2x1 pour remplir le sol.

La question est :

1. solution(1) La sortie attendue est de 2, la sortie réelle est de 2.
2. Cependant, solution(2) le résultat attendu est de 7 et le résultat réel est de 3.

La solution actuelle est :

1. 1x1 peut toujours remplir 2 x n couches, donc le chemin possible commence à partir de 1.
2. Si les étages restants mod 2 sont 0, les chemins possibles sont augmentés de 1.

Le problème avec la solution actuelle est qu'elle ne fait pas la différence entre les blocs 1x2 et 2x1. Donc pour solution(2), le résultat réel est de 3 au lieu de 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))
}

Solution

Une tentative plus descriptive et approfondie :

Le nombre de façons d'appeler une grille 2xn est x_n, le nombre de façons de couvrir une grille 2xn+1 est y_n et le nombre de façons de couvrir une grille 2xn+2 est z_n.

Cas de base :

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

Étape d'induction, n>=2 :

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

Considérez la cellule la plus à gauche d'une grille 2xn + 2, si elle est recouverte par une tuile 1x1, alors le reste est une grille 2xn + 1, sinon, elle est recouverte par une tuile 1x2 et le reste est une grille 2xn. Par conséquent,

z_n = x_n + y_n

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

Considérez la cellule la plus à gauche d'une grille 2xn + 1, si elle est recouverte par une tuile 1x1, le reste sera une grille 2xn, sinon, elle est recouverte par une tuile 1x2, le reste sera 2x(n- 1) + 1 grille. Par conséquent,

y_n = x_n + y_(n-1)

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

Considérez le coin supérieur gauche d'une grille 2xn, s'il est recouvert par une tuile 1x1, le reste sera 2x(n-1) + 1 grille, s'il est recouvert par une tuile 1x2, le reste sera un 2x( n-2) + 2 grilles, sinon, il est recouvert de tuiles 2x1 et le reste sera une grille 2x(n-1). Donc :

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

En remplaçant z_n par x_n + y_n, nous avons :

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

Maintenant, parcourez simplement chaque valeur :

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

Vous pouvez le faire sans utiliser de tranches, mais c'est plus facile à comprendre. Démo Playground

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!