(分割統治) trominoes アルゴリズムの複雑さとは何ですか?またその理由は何ですか?
2^k * 2^k サイズのボードが与えられましたが、タイルの 1 つがランダムに削除され、欠陥のあるボードになっています。タスクは、3 つのタイルで作られた L 字型の図形である「トロミノ」で埋めることです。
タイリングの問題
– 入力: n x n の正方形のボード。1 x 1 の正方形の 1 つが欠落しています。ここで、k ≥ 1 の場合は n = 2k です。
– 出力: トロミノを使用したボードのタイリング。2 x 2 の正方形から右上の 1 x 1 の角を削除した 3 つの正方形のタイル。
– ボードを並べるために、トロミノを回転させることができます。基本ケース: 2 x 2 の正方形を並べて表示できます。
誘導：
– 正方形を n/2 × n/2 の 4 に分割します。
– トロミノを「中央」に配置します。ここで、トロミノは、以前は 1 x 1 の正方形を逃していた n/2 x n/2 の正方形と重なりません。
– 4 つの n/2 x n/2 ボードのそれぞれを帰納的に解きます。