Рекурсия расписания турниров Java
Я работаю над домашним заданием для своего класса Java, и я зациклился на том, как настроить рекурсию (требуется), чтобы она работала. Мы должны запросить у пользователя ряд "n" конкурентов (предположим, что это должно быть сила 2, нам не нужно проверять правильность ввода пользователя). Каждая команда должна играть каждую команду только один раз. Выход для n = 8 должен быть:
1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1
Единственным параметром, который я могу передать методу, является "int n". Так что, если есть 16 команд (т.е. N = 16), то второй вызов будет проходить 8, затем пропустить 4, затем 2 и, наконец, 1.
Итак, исходя из этого, я понимаю, что каждая другая строка просто переворачивает каждую пару чисел. Итак, для 2 ^ 0 есть только одна команда. Для 2 ^ 1 это:
1 2
2 1
Для 2 ^ 2 это 4 команды, но команды 3 и 4 имеют ту же рекурсию, что и команды 1 и 2. Затем вы меняете их так, чтобы 3 и 4 приходили до 1 и 2, а затем вы меняли отдельные пары снова
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
Итак, вы можете разбить диаграмму на 4 равных угла, и каждый противоположный угол равен друг другу.
За последние пару дней я прошел через несколько вариантов моего кода, но вот где я сейчас. Это на самом деле шаг назад от того места, где я был, но я изначально пытался передать стартовую строку и начальный столбец, но мне сообщили, что я не должен этого делать, и просто передаю n рекурсивно.
class MyArray {
final int MAXROW = 32, MAXCOL = 32;
int A[][]; //reference variable
int nR, nC; //number of integers in A, <= MAXSIZE
//constructor
MyArray() {
A = new int[MAXROW] [MAXCOL];
nR = nC = 0;
}
void schedule(int n) {
if (n > 1) {
schedule(n/2);
for (int r = 0; r < n/2; r++)
for (int c = 0; c < n/2; c++) {
A[r+n][c] = A[r][c+n];
A[r+n][c+n] = A[r][c];
}
}
}
void printA() {
printA(nC-1)
}
void printA(int n) {
if (n >= 0) {
printA(n-1);
for (int c = 0; c < nC; c++)
System.out.printf("%3d", (A[n][c]));
System.out.println();
}
}
Ответы
Ответ 1
Наконец понял это. Вот код для метода расписания, красивый и короткий и сладкий, в основном, верхние левые значения + (n/2) = верхние правые и нижние левые значения. Нижние правые значения = верхние левые значения.
void schedule(int n) {
if (n > 0) {
schedule(n/2);
if (n == 1)
A[0][0] = 1;
else {
for (int r = 0; r < n/2; r++)
for (int c = 0; c < n/2; c++) {
A[r][c+(n/2)] = A[r][c] + (n/2);
A[r+(n/2)][c] = A[r][c] + (n/2);
A[r+(n/2)][c+(n/2)] = A[r][c];
}
}
}
}
Ответ 2
Я не смог исправить свой код..... мое решение:
![recursive]()
public class MyArray {
final int MAXROW = 32, MAXCOL = 32;
int A[][]; //reference variable
MyArray() {
A = new int[MAXROW][MAXCOL];
}
public static void main(String[] args) {
MyArray m = new MyArray();
int n = 8;
m.mySchedule(n);
m.printA(n);
}
void mySchedule(int n) {
mySchedule(n, 0, 0, n);
}
void mySchedule(int n, int row, int col, int carry) {
if (n == 1) {
A[row][col] = carry; //Trivial Case
} else {
//divide the problem into 4 subproblems
int k = n / 2;
mySchedule(k, row, col, carry - k);
mySchedule(k, row, col + k, carry);
mySchedule(k, row + k, col, carry);
mySchedule(k, row + k, col + k, carry - k);
}
}
void printA(int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
System.out.print(A[i][j] + "\t");
}
System.out.println();
}
}
}
Ответ 3
Вот моя текущая версия кода. Мой профессор все еще говорит, что он может быть более эффективным, удалив 2-й рекурсивный вызов. Я включил все свои комментарии, поэтому я вспомнил, что на самом деле делали.
class MySchedule {
final int MAXSIZE = 32;
int A[][]; //reference variable
int max; //number of integers in A, <= MAXSIZE
int row = 1; //keeps track of rows during recursion, row 0 set during user input
//constructor
MySchedule() {
A = new int[MAXSIZE] [MAXSIZE];
max = 0;
}
/*
if teams = 4, then movements per row are: 2^0, 2^1, 2^0
if teams = 8: 2^0, 2^1, 2^0, 2^2, 2^0, 2^1, 2^0
(n/2) gives us the correct power to calculate movements
for each value of n, we move n places in either direction
for loop iterates ever 2*n
outer loop is for each iteration
inner loops are each number of movements for each iteration
*/
void schedule(int n) {
if (n >= 1) {
schedule(n/2);
//start at column 0 for each row
int col = 0;
for (int i = 0; i < max; i += (2*n)) {
//current position uses value from previous n rows/columns.
for (int j = 0; j < n; j++)
A[row][col+j] = A[row-n][col+j+n];
for (int j = n; j < n*2; j++)
A[row][col+j] = A[row-n][col+j-n];
col += 2*n;
}
row++;
if (n > 1)
schedule(n/2);
}
}
void printA() {
//print header, then print team schedule
System.out.printf("%4s", "day");
System.out.printf("%12s", "teams");
System.out.println();
printA(max-1);
}
void printA(int n) {
if (n >= 0) {
printA(n-1);
//n=0 is the row to list the teams.
//Following rows indicate which team they play on which day
if (n == 0)
System.out.printf("%4s", "");
if (n >= 1)
System.out.printf("%4s", "D"+n);
for (int c = 0; c < max; c++)
System.out.printf("%3d", (A[n][c]));
System.out.println();
}
}
}
public class Hw10 {
//determine if n is a 2 power
static boolean isPow(int n) {
while (n > 1) {
if (n%2 != 0)
return false;
n = n / 2;
}
return true;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int teams;
//prompt user input for teams and print schedule
do {
System.out.print("How many teams (0 to exit): ");
teams = in.nextInt();
//check to make sure user input is a power of 2.
do {
if (isPow(teams) == false) {
System.out.println("Invalid input, must be a power of 2.");
System.out.print("How many teams (0 to exit): ");
teams = in.nextInt();
}
} while (isPow(teams) == false);
//initialize array to avoid out of bounds errors on repeat tries
MySchedule sched = new MySchedule();
//initialize first row of array with number of teams
for (int i = 0; i < teams; i++)
sched.A[0][i] = i+1;
sched.max = teams;
sched.schedule(teams/2);
sched.printA();
System.out.println();
} while (teams > 0);
}
}
