Магический квадрат рекурсии бесконечный цикл Java - PullRequest
Новая
       15

Магический квадрат рекурсии бесконечный цикл Java

0 голосов
/ 22 марта 2012

Я пытаюсь написать программу, которая может генерировать все возможные магические квадраты для фиксированного N-измерения.Я собираюсь заполнить диагональные ячейки значениями, а затем заполнить строки значениями.

Кажется, я застрял в бесконечном цикле, когда заполняю строки, но не могу понять, как и почему.Я не реализовал проверку суммы, чтобы проверить, правильна ли сумма строк или столбцов, но это здесь не имеет значения.

Если кто-нибудь может мне помочь, я был бы очень благодарен.код ниже 

public class Magic {

public static final int DIMENSION = 3;
public static final int DIMSQ = DIMENSION * DIMENSION;
public static int[][] array = new int[DIMENSION][DIMENSION];
public static boolean[] boolArray = new boolean[DIMENSION * DIMENSION];
public static final int sum = (DIMENSION * (DIMENSION * DIMENSION + 1)) / 2;

/*
 * Inicializaljuk a matrixunkat, illetve a boolean matrixunkat
 * Initializes the matrix and boolArray with values.
 */
public static void init() {
    for (int e[] : array) {
        for (int e2 : e) {
            e2 = 0;
        }
    }
    for (boolean e : boolArray) {
        e = false;
    }
}

/*
 * Ki irassa a matrix jelenlegi allapotat konzolra
 * Prints the array out to the console.
 */
public static void print() {
    for (int i[] : array) {
        for (int j : i) {
            System.out.print(j + ",");
        }
        System.out.println();
    }
    System.out.println();
}

/*
 * feltolti a foatlot adatokkal, majd meghivja a diagonal2-t
 * fills diagonal cells with values
 */
public static void diagonal1(int x) {

    for (int i = 0; i < DIMSQ; i++) {
        if (!boolArray[i]) {
            boolArray[i] = true;
            array[x][x] = i + 1;
            if (x < DIMENSION - 1) {
                diagonal1(x + 1);
            } else
                diagonal2(0);
            boolArray[i] = false;
        }
    }

}

/*
 * feltolti a mellekatlot adatokkal, majd meghivja a row(0,0,0)-t
 * fills diagonal cells with values
 */
public static void diagonal2(int x) {

    for (int i = 0; i < DIMSQ; i++) {
        if (!boolArray[i]) {

            if (array[DIMENSION - 1 - x][x] == 0) {
                boolArray[i] = true;
                array[DIMENSION - 1 - x][x] = i + 1;
            }
            if (x < DIMENSION - 1) {
                diagonal2(x + 1);
            } else
                row(0, 0);
            boolArray[i] = false;
        }
    }
}
/*
 * feltolti a sorokat adatokkal
 * fills rows with values
 */
public static void row(int x, int y) {
    for (int i = 0; i < DIMSQ; i++) {
        if (!boolArray[i]) {

            if (array[x][y] == 0) {
                boolArray[i] = true;
                array[x][y] = i;
            }

            if (x < DIMENSION - 1) {
                row(x + 1, y);
            } else if(y < DIMENSION - 1) { 
                row(0,y+1);
            } else print();

            boolArray[i] = false;

        }
    }
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    init();
    print();
    diagonal1(0);

}

}

Ответы [ 2 ]

0 голосов
/ 23 марта 2012

Не думаю, что это бесконечно, но очень долго:

9-ступенчатая петля в diag1,
3-глубокий отбор до diag1,
затем 9-ступенчатая петля в diag2
3-глубокая рекурсия в diag2,
затем 9-ступенчатая петля в row
~ 6-глубокая рекурсия в row.

Несмотря на то, что не все циклы выполняют сложные операции на каждой итерации, это может легко добавить до нескольких часов, если учесть, что вы печатаете состояние квадрата при каждом «разрешении» квадрата - печать на консоль занимает время.

0 голосов
/ 22 марта 2012

Мой подозреваемый - это метод row() (см. Мои комментарии ниже): 

public static void row(int x, int y) {
    for (int i = 0; i < DIMSQ; i++) {
        if (!boolArray[i]) {

            if (array[x][y] == 0) {
                boolArray[i] = true; // <-- this one
                array[x][y] = i;
            }

            if (x < DIMENSION - 1) {
                row(x + 1, y);
            } else if(y < DIMENSION - 1) { 
                row(0,y+1);
            } else print();

            boolArray[i] = false; // <-- would be OVERWRITTEN by this one

        }
    }
}
...