计算用两种瓷砖尺寸建造墙的方法

Question

您将获得一组使用3"×1"和4.5"×1"块构建面板的块.

为了结构完整性,块之间的空间不得排列在相邻的行中.

构建7.5"×1"面板的方法有2种,构建7.5"×2"面板的方法有2种,构建12"×3"面板的方法有4种,构建27"×5"面板的方式有7958种. "小组.有多少种方法可以构建48"×10"面板？

这是我到目前为止所理解的:

块3 x 1和4.5 x 1

我已经使用组合公式来找到可以在这个尺寸的面板中排列2个块的所有可能组合

C =选择 - > C(n,k)= n!/ r!(nr)!一次在r组合n组

面板:7.5 x 1 = 2种方式 - >

1(3 x 1块)和1(4.5 x 1块) - >仅使用2个块 - > 2 C 1 = 2路

面板:7.5 x 2 = 2种方式

我也在这里使用过组合

1(3 x 1块)和1(4.5 x 1块) - > 2 C 1 = 2路

面板:12 x 3面板= 2种方式 - >

2(4.5 x 1块)和1(3 x 1块) - > 3 C 1 = 3路

0(4.5 x 1块)和4(3 x 1块) - > 4 C 0 = 1路

3种方式+ 1种方式= 4种方式

(这是我感到困惑的地方)

面板27 x 5面板= 7958种方式

6(4.5 x 1块)和0(3 x 1) - > 6 C 0 = 1路

4(4.5 x 1块)和3(3 x 1块) - > 7 C 3 = 35路

2(4.5 x 1块)和6(3 x 1块) - > 8 C 2 = 28路

0(4.5 x 1块)和9(3 x 1块) - > 9 C 0 = 1路

1路+ 35路+ 28路+ 1路= 65路

正如你在这里看到的那样,道路的数量远不及7958.我在这里做错了什么？

另外,我如何找到构建48 x 10面板的方法有多少？因为手动操作有点困难,特别是在尝试寻找7958种方法时.

如何编写程序来计算7958面板的方法数量的答案？构建程序来计算结果会更容易吗？任何帮助将不胜感激.

Answer 1

这是 Java 中的一个解决方案，一些数组长度检查等有点混乱，但我相信你可以很容易地改进它。

无论如何，我希望这有助于演示该算法的工作原理:-)

import java.util.Arrays;

public class Puzzle
{
    // Initial solve call
    public static int solve(int width, int height)
    {
        // Double the widths so we can use integers (6x1 and 9x1)
        int[] prev = {-1};      // Make sure we don't get any collisions on the first layer
        return solve(prev, new int[0], width * 2, height);
    }

    // Build the current layer recursively given the previous layer and the current layer
    private static int solve(int[] prev, int[] current, int width, int remaining)
    {
        // Check whether we have a valid frame
        if(remaining == 0)
            return 1;

        if(current.length > 0)
        {
            // Check for overflows
            if(current[current.length - 1] > width)
                return 0;

            // Check for aligned gaps
            for(int i = 0; i < prev.length; i++)
                if(prev[i] < width)
                    if(current[current.length - 1] == prev[i])
                        return 0;

            // If we have a complete valid layer
            if(current[current.length - 1] == width)
                return solve(current, new int[0], width, remaining - 1);
        }

        // Try adding a 6x1
        int total = 0;
        int[] newCurrent = Arrays.copyOf(current, current.length + 1);
        if(current.length > 0)
            newCurrent[newCurrent.length - 1] = current[current.length - 1] + 6;
        else
            newCurrent[0] = 6;
        total += solve(prev, newCurrent, width, remaining);

        // Try adding a 9x1
        if(current.length > 0)
            newCurrent[newCurrent.length - 1] = current[current.length - 1] + 9;
        else
            newCurrent[0] = 9;
        total += solve(prev, newCurrent, width, remaining);

        return total;
    }

    // Main method
    public static void main(String[] args)
    {
        // e.g. 27x5, outputs 7958
        System.out.println(Puzzle.solve(27, 5));
    }
}