我有一个项目，其中我必须从3x1和4.5x1的块创建面板。为了结构完整性，块之间的空间不得在相邻的行中对齐。我必须计算所有可能的组合。一些示例是7.5x1面板具有2种可能的解决方案，7.5x2面板具有2种可能的解决方案，12x3面板具有4种可能的解决方案，而27x5面板具有7958种可能的解决方案。我的问题是，当我步入更高的宽度时，我会得到更多的解决方案。我认为这与可能有重复的表有关，但是我看不到它在哪里发生或如何修复。任何帮助将不胜感激。代码如下。
import java.util.ArrayList;
import java.util.List;
import puzzle.Row;
public class panel {
/**
* This program will return the number of unique tables that for structural integrity don't have blocks that line up
* in adjacent rows. The width is to be between 3 and 48 and the height between 1 and 10. The width
* should also be a multiple of 0.5.
*
* @param width, height
* @return totalTables
*/
public static void main(String[] args) {
int width = 0;
int height = 0;
// Check to make sure that two arguments were passed.
if (args.length != 2) {
System.out.println("Please enter both a height and a width.");
System.exit(1);
} else {
// Check that a data type of double was entered.
if ( ( args[0].matches("^[0-9]+(\\.[0-9]+)?$") ) &&
( Double.valueOf(args[0].trim()).doubleValue() >= 3.0 ) &&
( Double.valueOf(args[0].trim()).doubleValue() <= 48.0 ) &&
( Double.valueOf(args[0].trim()).doubleValue()) % 0.5 == 0 ) {
width = (int) (Double.valueOf(args[0].trim()).doubleValue() * 2); // Double the width so that we are working with an integer.
} else {
System.out.println("Please enter a number for your width that is between 3 and 48 and divisable by 0.5.");
System.exit(1);
}
// Check that a data type of integer was entered.
if ( ( args[1].matches("^[0-9]+$") ) && ( Integer.valueOf(args[1]) >= 1 ) && ( Integer.valueOf(args[1]) <= 10 )) {
height = Integer.valueOf(args[1].trim()).intValue();
} else {
System.out.println("Please enter an integer for your height that is between 1 and 10.");
System.exit(1);
}
List<Row> allRows = new ArrayList<Row>(); // Holds all the possible rows and needed information
findAllRows(width, 0, 0, allRows);
findMatches(allRows);
long totalTables = findUniqueTables(allRows, height);
System.out.println(totalTables);
}
}
/**
* Recursively calculates all possible row combinations for supplied width.
* Row configuration is stored in binary format with 1 indicating gaps. Each bit is
* represented by 3 inches. The bits 1, 2, nth are dropped as they are not needed.
*
* i.e. width of 12 would produce
* width = 12 * 2 = 24
*
* Bricks Binary Stored Binary Decimal Value
* 6 x 6 x 6 x 6 0 1 0 1 0 1 0 1 1 0 1 0 1 21
* 9 x 9 x 6 0 0 1 0 0 1 0 1 0 1 0 0 1 9
* 9 x 6 x 9 0 0 1 0 1 0 0 1 0 1 0 1 0 10
* 6 x 9 x 9 0 1 0 0 1 0 0 1 1 0 0 1 0 18
*/
public static void findAllRows(int width, int currLen, int rowConfig, List<Row> root) {
if (currLen + 6 == width) {
root.add(new Row(width, rowConfig)); // Add current row configuration as an acceptable row.
return;
} else if (currLen + 9 == width) {
rowConfig = rowConfig << 1;
root.add(new Row(width, rowConfig)); // Add current row configuration as an acceptable row.
return;
} else if (currLen + 6 > width) {
return; // Current configuration is longer than the width is allowed. Do not add.
} else {
int nextConfig = (rowConfig << 2) + 1; //
findAllRows(width, currLen + 6, nextConfig, root);
nextConfig = (rowConfig << 3) + 1;
findAllRows(width, currLen + 9, nextConfig, root);
}
return;
}
/**
* Finds all possible row matches for the given row that do not have gaps that line up.
*/
public static void findMatches(List<Row> rows) {
for (Row row : rows) {
for (Row rowC : rows) {
if (matchesBelow(row.getGaps(), rowC.getGaps())) {
row.addChilcRows(rowC.getGaps());
}
}
}
}
/**
* Does a bitwise AND to see if there are any gaps that line up. If there are no gaps then
* the resulting AND should equal to 0.
*/
public static boolean matchesBelow(int row, int rows) {
if ((row & rows) == 0) {
return true;
} else {
return false;
}
}
/**
* Finds all the unique tables and returns the count.
*/
public static long findUniqueTables(List<Row> allRows, int height) {
long tableCount = 0;
for (Row row : allRows) {
tableCount += findTables(row, height);
}
return tableCount;
}
/**
* This makes all possible tables.
*/
public static long findTables(Row row, int tableHeight) {
long count;
if (tableHeight == 1) {
return 1;
} else {
count = 0;
for (int i = 0; i < row.getChildRowsSize(row); i++) {
count += findTables(row, tableHeight -1);
}
}
return count;
}
}
还有我的难题。
package puzzle;
import java.util.ArrayList;
import java.util.List;
public class Row {
int gaps;
int width;
List<Long> potChildRows = new ArrayList<Long>();
public Row(int width, int gaps) {
this.gaps = gaps;
this.width = width;
}
public int getGaps() {
return this.gaps;
}
public int getWidth() {
return this.width;
}
public long getChildRowsSize(Row row) {
return row.potChildRows.size();
}
public void addChilcRows(long row) {
this.potChildRows.add(row);
}
}
最佳答案
我想我刚刚解决了任务。尽管问这个问题已经两个月了，但我认为这看起来像是一个很有趣的问题，所以我试了一下。我不想由于“作业”标签而发布代码(即使在2个月后)，因此我将仅介绍我的方法。我使用Python，但是我将尝试将任何术语转换为Java。
首先，我觉得您正在跟踪比您需要的更多数据的方式。我只是保留了一个 double 的ArrayList，以便对于任何 double i，i都引用一个ix1块。该列表已排序，使得row[0]是最左侧的块，而row[row.length-1]是最右侧的块。例如，[3, 3, 4.5]使用从左到右的3x1块，另一个3x1块和4.5x1块来引用长度为10.5的行。使用这种简单的结构，我可以轻松地可视化我的配置。我的行长就像将所有元素加在一起一样容易(即3 + 3 + 4.5 = 10.5)。我的差距就像遍历列表时保持总计一样容易(即，我的差距是3和3 + 3 = 6)。使用这种更简单的数据类型，您可以极大地简化您的代码。
另外，我发现将问题视为修改后的Depth-First Search很有帮助。使用DFS并给出一个二叉树，您首先尝试从根开始向左移动。然后，您尝试除最后一个节点以外的所有节点。等等。代替“left”和“right”，考虑“3”和“4.5”，其中节点的值为宽度，一旦宽度大于所需宽度width，您就停止遍历树。如果找到一个值恰好为width的节点，那么该路径现在就是可能的行，请记住它。换句话说，首先尝试N个3x1块(例如width + 2.5 >= N*3 >= width)，然后从左到右构建行。然后，您尝试(N-1)个3x1块和1个4x1块(最右边的4x1)。然后(N-2)个3x1s，一个4x1和另外一个3x1。等等。没有移位，没有rowConfig变量，只有一个数组宽度的ArrayList。另外，由于您一次又一次地系统地遍历了每条路径(即尝试了每种组合)，因此您知道自己尝试了每种组合，并且知道没有重复项。
现在，建立您的墙。也可以将其视为修改后的DFS。想象一个n元树，其中n等于宽度width的潜在行数。使用相同的系统方法，尝试每条路径，直到有一堵墙的高度为height(因为每一行的高度均为1)。但是请记住，如果所有间隙都不相邻，则只想遍历路径。尝试一次从下往上 build 一排墙。通过在墙的顶部添加一个新行，只要且仅当它的所有缝隙都不与顶行中的缝隙相邻时，您才能相信部分墙始终有效。在那里，一旦您按下height，您就会知道您有一面有效的墙。记录路径并继续，直到没有其他有效路径可供探索为止。
很抱歉在您仍在做作业时不回答。我想知道您最终的解决方案与我的有何不同。