2 x N の床を埋めることができる 1x1、1x2、2x1 タイルの組み合わせが何通りあるかを計算するにはどうすればよいでしょうか?

php 編集者の Shinichi が、誰もが興味深く頭を悩ませる質問に答えます: 2 x N の床を埋めることができる 1x1、1x2、および 2x1 タイルの組み合わせが何通りあるかを計算するにはどうすればよいですか?この問題には、組み合わせ数学や動的計画法の知識が必要であり、解析と導出を通じて、簡単で効果的な計算方法を導き出すことができます。次に、この質問に対する答えを一緒に考えてみましょう。

質問の内容

技術テストを行ったばかりですが、そのタスクについて混乱しています。私の目標は、この「覆われた床」問題を解決する方法を理解することです。正直、どこから始めればいいのかわかりません。

タスクは次のとおりです:

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) の場合、実際の出力は 7 ではなく 3 になります。

＃＃＃コード＃＃＃

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:

リーリー

2xn 2 グリッドの左端のセルを考えます。セルが 1x1 タイルで覆われている場合、残りは 2xn 1 グリッドになります。そうでない場合、1x2 タイルで覆われ、残りは 2xn グリッドになります。したがって、＃＃＃

z_n = x_n y_n

リーリー

2xn 1 グリッドの左端のセルを考えます。1x1 タイルで覆われている場合、残りは 2xn グリッドになります。そうでない場合、1x2 タイルで覆われている場合、残りは 2x(n- 1) 1 になります。グリッド。したがって、＃＃＃

y_n = x_n y_(n-1)

リーリー

2xn グリッドの左上隅を考えます。1x1 タイルで覆われている場合、残りは 2x(n-1) 1 グリッドになり、1x2 タイルで覆われている場合、残りは A 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)

• 次に、各値を反復処理します:
リーリー
• スライスを使用せずにこれを行うこともできますが、その方が理解しやすいです。
遊び場でのデモンストレーション

以上が2 x N の床を埋めることができる 1x1、1x2、2x1 タイルの組み合わせが何通りあるかを計算するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。