-1

我被问到这个问题是为了测试我的编程能力。虽然我觉得它和编程一样多的数学。老实说，我失败了，但我想知道它是如何完成的，以供将来参考。

理想的答案将使用递归和线程。

你的侄女在生日时收到了一组积木，她决定用 3”×1” 和 4.5”×1” 的积木搭建一个面板。为了结构完整性，积木之间的空间不能在相邻的行中排列. 比如下面这个13.5”×3”的面板是不能接受的，因为前两排的块之间有一些空间是对齐的（如虚线所示）。

7.5”×1”面板有2种方法，7.5”×2”面板有2种方法，12”×3”面板有4种方法，27”×5有7958种方法“ 控制板。您的侄女有多少种不同的方法可以制作 48”×10” 面板？答案将适合 64 位整数。编写程序计算答案。

这就是问题所在，我不知道从数学方面开始。我知道我需要计算第一行的所有可能组合。但我不确定如何。然后，您可以此时在特定线程上计算下一行的所有可能组合，依此类推。然后每个第一行组合可以获得自己的线程并将其设置传递给递归算法，该算法将当前行与最后一行进行比较，并找到可能的答案。但我无法真正对其进行编程，因为我不知道如何计算任何行的可能组合。如果我这样做了，那么也许我可以检查它是否是合法行（没有两个块完全重叠（交错））并继续下一个。就代码而言，每一行可能都是嵌套在下一行周围的 for 循环。但我又一次没有

4

2 回答 2

1

我认为你对这个问题有一个很好的初步把握。如果我正确理解您的想法，您应该在每个块放置上递归，而不是在每个行放置上递归- 因为垂直定向的块将很快排除任何普通行。

这是我将采取的方法：您最终将构建一棵树（在内存中显式或隐式：树可以是在递归函数中传递的参数）。树的节点将是树的状态 - 所以根是“没有放置块”。你“以某种方式”放置了第一个块（我们会谈到那个），它代表一个新的状态。

目标将是构建一组完整的叶节点（棋盘已填满）且合法（没有裂缝排列）。那么我们如何到达那里呢？

对于每个块放置，有 4 个“替代现实”：水平放置的 3x1 块、垂直放置的 3x1（称为 1x3）、水平放置的 4.5x1 和 1x4.5。对于这些选项中的每一个，您都将尝试“合法地”将块放置在行中的下一个点。如果它是合法的（合法的是“块不与板边缘重叠，块不共享垂直边缘”），那么您可以接受该板作为中间状态并使用该新状态递归。如果不合法，则必须放弃该状态。

这样想，前 4 个子节点将是左下角的一个块，为 [3x1, 1x3, 4.5x1, 1x4.5]。这四种状态中的每一种都将在 4 种配置中的一种中“向右”有一个块，依此类推。

为了跨行移动，当你点击右边缘时，我会找到“最低”的空白空间，并在它们从左到右连接时任意填充它们。当边缘参差不齐时，这足以修剪大型集合，但在水平平坦时仍然可以很好地工作，就像您刚开始时一样。

本质上，您的树对于每个中间状态将有（最多）4 个节点，边缘表示“尝试放置”。如果你不能合法地将块放置在那个“尝试的位置”，你就不会递归，修剪这种可能性和树上的所有后代。

这种蛮力方法应该可以为您提供一个完整的电路板，即使它的计算复杂度是天文数字。只有在您可以正确解决一些问题时，您才应该考虑使用线程进行并行化。递归问题往往很适合线程，因为每个递归通常可以并行化而不会带来太多痛苦。只要确保你先做对了。

于 2013-02-01T04:30:34.210 回答
1

这篇文章已经快 5 年了，但也许我的回答对某人有用。下面有两种解决方案。首先是没有多线程。第二个使用四个线程来解决问题。它计算 48x4 面板（48x10 持续很长时间），但可以通过更改初始值轻松修改：

nbOfRows、nbOfCols、wallWidth 和墙

没有多线程的解决方案：

import java.io.*;
import java.util.*;

class WallFlexOld
{
    static final float blocks[] = {3.0f, 4.5f};
    static final int nbOfRows = 4;
    static final int nbOfCols = 16;
    static final float wallWidth = 48.0f;
    static final float wall[][] = {
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
                            };

    static long nbOfCombinations = 0;

    public static void main(String args[])
    {
        long startTime = System.currentTimeMillis();
        addBlock(0, 0);
        long workingTime = System.currentTimeMillis() - startTime;

        System.out.println("Working time: " + workingTime + "ms");
        System.out.println("noc: " + nbOfCombinations);
    }

    static void addBlock(int row, int col)
    {
        for(float b: blocks)
        {
            wall[row][col] = b;
            if(blockFit(row, col))
            {
                if(rowWidth(row) <= wallWidth)
                {
                    if(rowWidth(row) == wallWidth)
                    {
                        if(row == (nbOfRows - 1))
                            nbOfCombinations++;
                        else
                            addBlock(row + 1, 0);
                    }
                    else //rowWidth < wallWidth
                        addBlock(row, col + 1);

                }
            }   
            wall[row][col] = 0; 
        }
    }

    static float rowWidth(int row)
    {
        float width = 0;
        for(float b: wall[row])
            width = width + b;
        return width;
    }

    static boolean blockFit(int row, int col)
    {
        if(row == 0)
            return true;

        boolean fit = true;
        float currentLenght = 0;
        for(int i = 0; i < col; i++)
            currentLenght = currentLenght + wall[row][i];

        float lowerRowCurLenght = 0;
        for(float b: wall[row - 1])
        {
            lowerRowCurLenght = lowerRowCurLenght + b;
            if((currentLenght == lowerRowCurLenght) & (currentLenght != wallWidth))
                fit = false;
        }

        return fit;
    }
}

多线程解决方案：

import java.io.*;
import java.util.*;

class Wall implements Runnable
{
    private float blocks[];
    private int nbOfRows;
    private int nbOfCols;
    private float wallWidth;
    private float wall[][];
    private long nbOfCombinations = 0;
    private int row, col;

    public long getNbOfCombinations() { return this.nbOfCombinations; }

    Wall(float blocks[], int nbOfRows, int nbOfCols, float wallWidth, float wall[][], int row, int col)
    {
        this.blocks = blocks;
        this.nbOfRows = nbOfRows;
        this.nbOfCols = nbOfCols;
        this.wallWidth = wallWidth;
        this.wall = wall;
        this.row = row;
        this.col = col;
    }

    private boolean blockFit(int row, int col)
    {
        if(row == 0)
            return true;

        boolean fit = true;
        float currentLenght = 0;
        for(int i = 0; i < col; i++)
            currentLenght = currentLenght + wall[row][i];

        float lowerRowCurLenght = 0;
        for(float b: wall[row - 1])
        {
            lowerRowCurLenght = lowerRowCurLenght + b;
            if((currentLenght == lowerRowCurLenght) & (currentLenght != wallWidth))
                fit = false;
        }

        return fit;
    }

    private float rowWidth(int row)
    {
        float width = 0;
        for(float b: wall[row])
            width = width + b;
        return width;
    }

    private void addBlock(int row, int col)
    {
        for(float b: blocks)
        {
            wall[row][col] = b;
            if(blockFit(row, col))
            {
                if(rowWidth(row) <= wallWidth)
                {
                    if(rowWidth(row) == wallWidth)
                    {
                        if(row == (nbOfRows - 1))
                            nbOfCombinations++;
                        else
                            addBlock(row + 1, 0);
                    }
                    else //rowWidth < wallWidth
                    {
                        addBlock(row, col + 1);
                    }
                }
            }
            wall[row][col] = 0;
        }
    }


    @Override
    public void run()
    {
        addBlock(row, col);
    }
}

class WallMT
{
    static final float blocks[] = {3.0f, 4.5f};
    static final int nbOfRows = 4;
    static final int nbOfCols = 16;
    static final float wallWidth = 48.0f;
    static final float wall[][] = {
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
                            };

    public static void main(String args[])
    {
        wall[0][0] = blocks[0];
        wall[0][1] = blocks[0];
        Wall myWall1 = new Wall(blocks, nbOfRows, nbOfCols, wallWidth, getWallCopy(wall), 0, 2);
        Thread t1 = new Thread(myWall1);

        wall[0][0] = blocks[0];
        wall[0][1] = blocks[1];
        Wall myWall2 = new Wall(blocks, nbOfRows, nbOfCols, wallWidth, getWallCopy(wall), 0, 2);
        Thread t2 = new Thread(myWall2);

        wall[0][0] = blocks[1];
        wall[0][1] = blocks[0];
        Wall myWall3 = new Wall(blocks, nbOfRows, nbOfCols, wallWidth, getWallCopy(wall), 0, 2);
        Thread t3 = new Thread(myWall3);

        wall[0][0] = blocks[1];
        wall[0][1] = blocks[1];
        Wall myWall4 = new Wall(blocks, nbOfRows, nbOfCols, wallWidth, getWallCopy(wall), 0, 2);
        Thread t4 = new Thread(myWall4);

        long startTime = System.currentTimeMillis();
        t1.start();
        t2.start();
        t3.start();
        t4.start();
        try
        {
            t1.join();  
            t2.join();
            t3.join();  
            t4.join();  
        }
        catch(InterruptedException ie)
        {
            System.out.println("Thread " + t1 + " interrupted.");
        }

        long workingTime = System.currentTimeMillis() - startTime;

        System.out.println("Working time: " + workingTime + "ms");
        System.out.println("noc: " + (myWall1.getNbOfCombinations() + myWall2.getNbOfCombinations() + myWall3.getNbOfCombinations() + myWall4.getNbOfCombinations()));
    }

    static private float[][] getWallCopy(float wall[][])
    {
        float tmpWall[][] = new float[nbOfRows][nbOfCols];

        for(int i = 0; i < nbOfRows; i++)
            for(int j = 0; j < nbOfCols; j++)
                tmpWall[i][j] = wall[i][j];

        return tmpWall;
    }
}
于 2018-01-04T20:38:58.427 回答