9
Tôi có một dự án mà trong đó tôi phải tạo bảng điều khiển từ các khối 3x1 và 4.5x1. Đối với tính toàn vẹn cấu trúc, khoảng cách giữa các khối không được xếp hàng trong các hàng liền kề. Tôi phải tính toán tất cả các kết hợp có thể. Một số ví dụ là một bảng 7.5x1 có 2 giải pháp khả thi, bảng 7.5x2 có 2 giải pháp khả thi, bảng 12x3 có 4 cách có thể và 27x5 có 7958 cách có thể. Vấn đề của tôi là khi tôi nhận được vào chiều rộng cao hơn tôi nhận được nhiều giải pháp sau đó tôi nên. Tôi nghĩ rằng điều này phải làm với điều đó là có khả năng tôi đang nhận được bảng trùng lặp, nhưng tôi không thể nhìn thấy nơi nó đang xảy ra hoặc làm thế nào để sửa chữa nó. Mọi sự trợ giúp sẽ rất được trân trọng. Mã sau đây.Kết hợp bảng duy nhất với khối - Mã trong 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;
}
}
Và câu đố của tôi.
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);
}
}
Bạn có thể cung cấp trường hợp không thành công không? Có phải "27x5 có 7958 cách có thể" đại diện cho một trường hợp lỗi không? Nếu có, đó sẽ là giải pháp? Nếu không bạn có thể cung cấp một trường hợp nó không thành công? – Zecas