Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Backtracking SS14
Hi,
da es noch keine “Musterlösung” hier auf der FSI Seite zur Batracking Aufgabe vom 24.7.2014 gibt, stelle ich meinen Ansatz hier mal hoch und hoffe auf Verbesserungen und Kritik 
public class BacktrackingAufgabe4Klausur240714 {
public static void main(String args[]){
}
// Teilaufgabe a):
boolean exists(boolean[][]brd, int r, int c){
if(brd[r]==null){
return false;
}if(brd[r][c]==false||brd[r][c]==true){
return true;
}
return false;
}
//Teilaufgabe b
int[][] allocateSolutionArray(boolean[][]brd, int mrl){
int [][]sol=null;
sol=new int[mrl][];
for(int i=0;i<sol.length;i++){
for(int j=0;j<brd[i].length;j++){
if(exists(brd,i,j)==true&&brd[i][j]==true){
sol[i][j]=0;
}
else{sol[i][j]=-1;
}
}
}
return sol;
}
//Teilaufgabe c
boolean solve (boolean[][]brd, int[][]sol, int tf, int r, int c, int n){
int[][] jumps={{r+2,c-1},{r+1,c-2},{r-1,c-2},{r-2,c-1},{r-2,c+1},{r-1,c+2},{r+1,c+2},{r+2,c+2}};
if(brd==null){
return false;
}
if(sol==null){
sol= allocateSolutionArray(brd, brd.length);
}
if(n==tf){
return true;
}
for(int k=0; k<jumps.length;k++){
n=n++;
r=jumps[k][0];
c=jumps[k][1];
if(exists(brd,r,c)){
sol[r][c]=n;
}
if(solve(brd,sol,tf,r,c,n)==true){
return true;
}else{
sol[r][c]=0;
//n--;
}
}
return false;
}
}
Ohne jetzt weiter über die Aufgabe geschaut zu haben:
Du greifst auf [m]brd[r][/m] und [m]brd[r][c][/m] zu, ohne Grenzen überprüft zu haben. Das ganze stirbt natürlich, wenn [m]r[/m] und [m]c[/m] nicht innerhalb der Array-Grenzen liegen.
Außerdem ist die Bedingung:
immer erfüllt. Ist zwar im Sinne dieser Aufgabe anscheinend nicht falsch, sieht aber sehr seltsam aus.
Edit:
Davon abgesehen sind Vergleiche mit [m]true[/m] oder [m]false[/m] eher schlechter Stil (Auch wenn vielleicht für Anfänger leichter lesbar.)
[m]B == true[/m] ist äquivalent zu [m]B[/m] und [m]B == false[/m] zu [m]!B[/m]. Kann man sich leicht anhand einer Wahrheitstabelle veranschaulichen.
Hi Volschaf … Ich bin der Lernkollege von Kelakrat und wir haben den Code uns zusammen überlegt… Mit der Null Abfrage hatten wir ursprünglich auch bezweckt eine Null Pointer Exception zu umgehen für den Fall dass r und c über den Arrayrand hinausläuft … Ist das nicht ausreichend ? Beziehungsweise wieso nicht und wie kann man das Besser machen ?
Danke im Voraus
In diesem Fall tritt eine ArrayIndexOutOfBoundsException auf. Du musst also auch sicherstellen, dass r und c nicht zu groß (und nicht kleiner 0) sind.
Hi,
da es noch keine “Musterlösung” hier auf der FSI Seite zur Batracking Aufgabe vom 24.7.2014 gibt, stelle ich meinen Ansatz hier mal hoch und hoffe auf Verbesserungen und Kritik
public class BacktrackingAufgabe4Klausur240714 {
public static void main(String args[]){
}
// Teilaufgabe a):
boolean exists(boolean[][]brd, int r, int c){
if(brd[r]==null){
return false;
}if(brd[r][c]==false||brd[r][c]==true){
return true;
}
return false;
}[color=crimson]if (r <0 || c <0) {
return false}
if (r>=brd.length || c>=brd[r].lenght) {
return false;
}
Das sollte noch rein um zu testen ob des die Fehler überhaupt gibt.
Die Frage die sich mir jetzt aber stellte ist wie man den Aufgabentext zu verstehen hatte, denn es steht ja dort ob ein solches “Feld existiert” d.h. die Frage die jetzt mir kam war “Ist mit exisitiert gemeint, dass das Feld von dem Springer betreten werden kann?” (dann müsste das Feld ja true sein) oder ist mit exisitiert gemeint, dass es das Feld überhaupt in diesem boolean array gibt? (dann ist es ja egal ob false oder true, hauptsache es ist da).
[/color]
//Teilaufgabe b
int[][] allocateSolutionArray(boolean[][]brd, int mrl){
int [][]sol=null;
sol=new int[mrl][];
for(int i=0;i<sol.length;i++){
for(int j=0;j<brd[i].length;j++){
if(exists(brd,i,j)==true&&brd[i][j]==true){
sol[i][j]=0;
}
else{sol[i][j]=-1;
}
}
}
return sol;
}int [][] sol = new int [brd.length][mrl] habe ich, aber ansonsten habe ich das gleiche.
//Teilaufgabe c
boolean solve (boolean[][]brd, int[][]sol, int tf, int r, int c, int n){
int[][] jumps={{r+2,c-1},{r+1,c-2},{r-1,c-2},{r-2,c-1},{r-2,c+1},{r-1,c+2},{r+1,c+2},{r+2,c+2}};
if(brd==null){
return false;
}
if(sol==null){
sol= allocateSolutionArray(brd, brd.length);
}
if(n==tf){
return true;
}
for(int k=0; k<jumps.length;k++){
n=n++;
r=jumps[k][0];
c=jumps[k][1];
if(exists(brd,r,c)){
sol[r][c]=n;
}
if(solve(brd,sol,tf,r,c,n)==true){
return true;
}else{
sol[r][c]=0;
//n--;
}
}
return false;
}
}schaut gut aus!
habs mal ausprobiert, funktioniert so
static boolean exists(boolean[][]brd, int r, int c){
if (r > brd.length-1 || r < 0 || null == brd[r] || c > brd[r].length-1 || c < 0) {
return false;
}
return brd[r][c];
}
static int[][] allocateSolutionArray(boolean[][]brd, int mrl){
int[][] sol = new int [brd.length][mrl];
for(int i=0;i<brd.length;i++){
for(int j=0;j<mrl;j++){
if(exists(brd,i,j)) {
sol[i][j]=0;
}
else{
sol[i][j]=-1;
}
}
}
return sol;
}
static boolean solve (boolean[][]brd, int[][]sol, int tf, int r, int c, int n){
int[][] jumps={{r+2,c-1},{r+1,c-2},{r-1,c-2},{r-2,c-1},{r-2,c+1},{r-1,c+2},{r+1,c+2},{r+2,c+1}};
if (sol[r][c] >= 1) {
return false;
}
if(n==tf){
sol[r][c] = n;
return true;
}
sol[r][c]=n;
for(int k=0; k<jumps.length;k++){
if(exists(brd,jumps[k][0], jumps[k][1])){
if(solve(brd,sol,tf, jumps[k][0], jumps[k][1], n+1)) {
return true;
}
}
}
sol[r][c] = 0;
return false;
} Das ist ein gefährlicher Fehler - der Wert von n wird dadurch nicht verändert! Besser: n++;
Wuerde die letzte Zeile auf return true; aendern, den es soll ja rueckmelden ob ein feld existiert, der inhalt des feldes kann aber False sein,ist zumindest so im beispiel, und in diesem Fall soll ja trotzdem true zurueckgegeben werde…
Mal ne Frage zum aufgabentext a)…, die ueberprueft, ob das Schachbrett brd ueberhaupt einen Eintrag… hat. Man kann ja wie beim voirherigen vorschlag ein bei einer feld das zwar exisitiert aber eben False gespeichert hat, dann diesen wert mit return brd[r][c] zurueckgeben, aber ich wuede die aufgabe so interpretieren das auch ein feld welches false gespeichert hat, dazu fuehrt das exists ein true zurueckgibt, da ja auch ein feld mit false als inhalt, trotzdem exisitert… wuerden beide ansaetze punkte bringen oder was waere hier richtig?