algorithm - 计算用两种瓷砖尺寸 build 墙的方法

Closed. This question is off-topic。它当前不接受答案。












想要改善这个问题吗？ Update the question，所以它是用于堆栈溢出的on-topic。

9年前关闭。



Improve this question





到目前为止，这是我的理解:
使用 3 x 1 和 4.5 x 1 块
我已经使用组合公式找到了所有可能的组合，可以将2个块布置在这种尺寸的面板中
C =选择-> C(n，k)= n!/r!(n-r)!一次在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面板的方式数量的答案？
构造一个程序来计算结果会更容易吗？任何帮助将不胜感激。

最佳答案

这是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));
    }
}