Hi - vielleicht kann mir wer helfen:
ich habe folgende aufgabe bekommen:
Ein magisches Quadrat ist eine n × n-Matrix, n 1, deren Felder
mit den natürlichen Zahlen 1, . . . , n2 gefüllt sind, sodass die Summe der Zahlen in jeder
Zeile, Spalte und Diagonale den gleichen Wert besitzen. Jede Zahl i, 1 i n2, muss
genau einmal vorkommen.
Beispiel für n = 3:
4 9 2
3 5 7
8 1 6
Beispiel für n = 5:
3 16 9 22 15
20 8 21 14 2
7 25 13 1 19
24 12 5 18 6
11 4 17 10 23
In der Vorlesung und der Übung wurden Backtracking-Algorithmen (8-Damen-Problem,
Sudoku-Rätsel) als Beispiele für rekursive Verfahren detailliert behandelt.
Ihre Aufgabe ist es, einen Backtracking-Algorithmus zu implementieren, der als Parameter
eine Zahl n erhält und ein magisches Quadrat der Größe n × n erzeugt
und auf dem Bildschirm ausgibt. Der Dialog soll folgendermaßen ablaufen:
Bitte geben Sie eine Zahl ein: 5
3 16 9 22 15
20 8 21 14 2
7 25 13 1 19
24 12 5 18 6
11 4 17 10 23
Testen Sie Ihr Programm mit Werten n < 4
Meine Lösung wäre folgende - für n=3 funktioniert das auch wunderbar aber ab 4 dauert es ewig
darf das sein?
ist das programm überhaupt rekursiv usw?
wäre echt nett wenn sich das jemand anschauen und verbessern bzwmir verbesserungsvorschläge geben kann
ich habe folgende aufgabe bekommen:
Ein magisches Quadrat ist eine n × n-Matrix, n 1, deren Felder
mit den natürlichen Zahlen 1, . . . , n2 gefüllt sind, sodass die Summe der Zahlen in jeder
Zeile, Spalte und Diagonale den gleichen Wert besitzen. Jede Zahl i, 1 i n2, muss
genau einmal vorkommen.
Beispiel für n = 3:
4 9 2
3 5 7
8 1 6
Beispiel für n = 5:
3 16 9 22 15
20 8 21 14 2
7 25 13 1 19
24 12 5 18 6
11 4 17 10 23
In der Vorlesung und der Übung wurden Backtracking-Algorithmen (8-Damen-Problem,
Sudoku-Rätsel) als Beispiele für rekursive Verfahren detailliert behandelt.
Ihre Aufgabe ist es, einen Backtracking-Algorithmus zu implementieren, der als Parameter
eine Zahl n erhält und ein magisches Quadrat der Größe n × n erzeugt
und auf dem Bildschirm ausgibt. Der Dialog soll folgendermaßen ablaufen:
Bitte geben Sie eine Zahl ein: 5
3 16 9 22 15
20 8 21 14 2
7 25 13 1 19
24 12 5 18 6
11 4 17 10 23
Testen Sie Ihr Programm mit Werten n < 4
Meine Lösung wäre folgende - für n=3 funktioniert das auch wunderbar aber ab 4 dauert es ewig
darf das sein?
ist das programm überhaupt rekursiv usw?
wäre echt nett wenn sich das jemand anschauen und verbessern bzwmir verbesserungsvorschläge geben kann
Java:
import java.util.Scanner;
public class MagicSquare {
// Anfang Attribute
private int[][] square;
private int n;
// Ende Attribute
/**
* Konstruktor für ein magisches Quadrat der Groesse n
* @param n Groesse des magischen Quadrats
*/
public MagicSquare(int n) {
this.n = n;
square = new int[n][n];
createMagicSquare(1);
}
/**
* Gibt das Quadrat auf der Console aus.
*/
public void print() {
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
System.out.print(""+square[x][y]+"\t");
}
System.out.println("");
}
System.exit();
}
/**
* Prueft, ob das Quadrat magisch gefuellt ist.
* @return true falls das Quadrat magisch gefuellt ist, andernfalls false
*/
public boolean isMagicSquare() {
int x,y;
int sollwert, summe;
boolean result= true;
sollwert= (n * (n*n+1)) / 2; // Summe, die jede Zeile erhalten muss
for (x= 0; x < n; x++){
// Spalten testen
summe= 0;
for (y= 0; y < n; y++) summe= summe + square[x][y];
result= result && (summe == sollwert);
}
for (y= 0; y < n; y++){
// Zeilen testen
summe= 0;
for (x= 0; x < n; x++) summe= summe + square[x][y];
result= result && (summe == sollwert);
}
summe= 0;
// Abwärts-Diagonale testen
for (x= 0; x < n; x++) summe= summe + square[x][x];
result= result && (summe == sollwert);
summe= 0;
// Aufwärts-Diagonale testen
for (x= 0; x < n; x++) summe= summe + square[x][n-x-1];
result= result && (summe == sollwert);
return result;
}
/**
* Fuellt das Quadrat magisch
* @param digit gibt an, welche Zahl gerade eingetragen wird.
*/
public void createMagicSquare(int digit) {
int x,y;
if ((digit > n*n) && isMagicSquare())
print();
else {
for (x = 0; x < n; x++) {
for (y = 0; y < n; y++) {
if (square[x][y] == 0) {
square[x][y] = digit;
createMagicSquare(digit + 1);
square[x][y] = 0;
}
}
}
}
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Bitte gib eine Zahl n ein:");
int n = sc.nextInt();
MagicSquare mag = new MagicSquare(n);
mag.print();
}
}
