9
我有一個項目，我必須從3x1和4.5x1的塊創建面板。對於結構完整性，塊之間的空間不得排列在相鄰的行中。我必須計算所有可能的組合。一些示例是7.5x1面板有2種可能的解決方案，7.5x2面板有2種可能的解決方案，12x3面板有4種可能的方式，而27x5有7958種可能的方式。我的問題是，當我進入更高的寬度時，我得到更多的解決方案，然後我應該。我認爲這與我有可能會得到重複的表格，但我不能看到它發生在哪裏或如何解決它。任何幫助將不勝感激。代碼如下。具有塊的獨特面板組合 - 在Java中的代碼
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;
}
}
而我的puzzle.Row類。
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);
}
}
你能否提供一個失敗的案例？ 「27x5有7958種可能的方式」代表錯誤情況嗎？如果是的話，哪個解決方案？如果不是，你能提供一個失敗的案例嗎？ – Zecas 2012-05-11 09:19:21