Подтвердить что ты не робот

Рекурсия расписания турниров 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();
    }
}
4b9b3361

ОТВЕТЫ

Ответ 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);
    }
}