JAVA を使用して、次のような n 行 n 列のテーブルを含むテキスト ファイルを読み込む必要があります (ただし、サイズは異なる場合があります)。
0110
1000
1001
0010
n を人数とします。この表は、人物 (行) と別の人物 (列) の関係を示しています。テーブルの値が 1 の場合、2 つは友達です。0 の場合、それらは友達ではありません。たとえば、(0,1) は 1 です。したがって、1 と 2 は友達です。テーブル内の各人に、指定された数の文字 (この特定のテーブルの場合: 2) から文字を割り当てる必要があります。2 人が友達である場合、別の手紙を受け取る必要があります。人々は自分自身と友達とは見なされません。RECURSIVE BACKTRACKING を使用して、このパズルの解決策を見つけて印刷するか、解決策がないと判断する必要があります。
編集: 表に明示的に記載されていない限り、友達の友達は友達とは見なされません。たとえば、この表では、1 は 2 および 3 と友達です。ただし、2 と 3 は友達ではありません。1 と 3 は友達、3 と 4 は友達ですが、1 と 4 は友達ではありません。ここでの番号付けは自然ですが、実際にはテーブルのインデックスは 0 から始まります。
この問題をどこから始めればよいかわかりません。テーブルには (0,0) から (n,n) までの対称線があることに気付きます。なぜなら、(1,2) が友達である場合、(2,1) も友達であり、誰も自分自身の友達ではないからです ( n,n) は常に 0 になります。
編集:視覚的に表示するには、問題を解決するには太字の情報のみが必要なようです。
0 110
10 00
100 1
0010
常に人 1 に文字 A を割り当て、行を調べて値 1 の場所に別の文字を割り当てることはもっともらしいようです。これを正確に行う方法がわかりません。2 と 3 の異なる文字を割り当てる必要はありません。この時点で文字を入力します (バックトラックで後で処理します)。
編集:次を使用して、人に乱数を割り当てることができます(後で文字に変換されます)。次に、その番号を除外リストに追加して、これらの番号が値 1 (友人) を持つ行内の人に割り当てられないようにします。
public static int getRandomWithExclusion(Random rnd, int start, int end, List<Integer> exclude) {
int random = start + rnd.nextInt(end - start + 1 - exclude.size());
for (int ex : exclude) {
if (random < ex) {
break;
}
random++;
}
return random;
編集：
これまでのところ、このコードがあります。ただし、バックトラッキングを使用してそれを行う方法を見つけることができないようです。また、これがより大きなテーブルで機能するかどうかはわかりません。除外の実装を修正する必要があるようです。
public static void assignLetter(int[][] table, int number_of_letters) {
int[] assignments = new int[table.length];
Random rnd = new Random();
List<Integer> exclude = new ArrayList<>();
// Person 1 is always assigned 1
assignments[0]= 1;
// Add 1 to exclusion list
exclude.add(1);
int row;
int col;
int nextAssignment;
// Loop through each row
for(row = 0; row <= table.length; row++) {
//Loop through each column in each row
for (col = row + 1; col < table.length; col++) {
// If column value in row 1 equals 1, assigned number cannot be 1
if (table[row][col] == 1) {
// Generate random number within parameters excluding 1
nextAssignment = getRandomWithExclusion(rnd, 1, number_of_letters, exclude);
assignments[col] = nextAssignment;
}
// If column value in row 1 equals 0, assign person any number within parameters
if (table[row][col] == 0 && row == 0) {
// Generate random number within parameters, no exclusions
nextAssignment = rnd.nextInt(number_of_letters) + 1;
assignments[col] = nextAssignment;
}
// If a value in a subsequent row is 1 and the corresponding assignments are equal,
// the assignments must be altered per the specifications
if (table[row][col] == 1 && row > 0 && assignments[row] == assignments[col]) {
// If the exclude list is equal to the number of letters, there is no solution
if (exclude.size() == number_of_letters) {
System.out.println("There is no solution");
}
// If the value in row 1 of the table is not 1, it can be assigned 1
if (table[0][col] != 1) {
nextAssignment = 1;
assignments[col] = nextAssignment;
}
}
}
}
for (int i = 0; i < assignments.length; i++) {
int person = i + 1;
int letterNum = assignments[i];
char[] alphaArray = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
char letter = alphaArray[letterNum-1];
System.out.println(person + " : " + letter);
}
}
私を正しい道に導くのに役立つ提案はありますか?
ありがとうございました！