M
momba
Gast
Hallo liebe community,
ich muss ein Programm für den Informatik-GK an meiner Schule programmieren.
Die Aufgabe lautet : "Gesucht ist eine Zahl - bestehend aus den Ziffern 1-9, bei der die Zahl, die aus den ersten i Ziffern gebildet werden kann, und durch i teilbar ist (i = 1-9)"
Diese Aufgabe soll mit Hilfe eines Backtracking Algorithmus programmiert werden. Als Grundlage haben wir von unserem Lehrer ein Backtracking Programm zum 8-Damen Problem erhalten :
Ich bin der totale Trottel, wenn es sich um Java handelt. Für schnelle Hilfe wäre ich sehr dankbar.
MfG momba
ich muss ein Programm für den Informatik-GK an meiner Schule programmieren.
Die Aufgabe lautet : "Gesucht ist eine Zahl - bestehend aus den Ziffern 1-9, bei der die Zahl, die aus den ersten i Ziffern gebildet werden kann, und durch i teilbar ist (i = 1-9)"
Diese Aufgabe soll mit Hilfe eines Backtracking Algorithmus programmiert werden. Als Grundlage haben wir von unserem Lehrer ein Backtracking Programm zum 8-Damen Problem erhalten :
Java:
public class Search
{
private int dim = 8;
private MainWindow mainWindow; // Fenster fuer Ausgabe
private boolean[][] belegt; // gibt an, ob auf Feld x,y eine Dame steht
public Search( MainWindow win )
{
mainWindow = win;
// Thread starten
}
// Hauptfunktion des Threads
public void sucheNext() // Muss unbedingt public sein !!!
{
erfolgreich = false;
//belegt = new boolean[dim][dim]; // Arrays initialisieren
for (int x=0; x<dim; x++)
{
for (int y=0; y<dim; y++)
belegt[x][y] = false;
}
recSearch(0); // Suche starten
}
// rekursive Suche Backtracking
private boolean erfolgreich = false;
private void recSearch(int spalte)
{
int zeile = -1;
while (zeile < dim-1 && !erfolgreich)
//weitere wahl möglich und noch nicht erfolgreich
{
zeile++;
if (isFieldOk (spalte, zeile))
//wahl annehmbar
{
setQueen (spalte, zeile);
//lösungsversuch aufzeichnen
if (spalte < dim-1)
//weitere wahl möglich
{
recSearch (spalte + 1);
//rekursiver aufruf auf tieferer stufe: trial
if (!erfolgreich)
// kein erfolg auf tieferer stufe: error
clearQueen (spalte, zeile);
//rücknahme des lösungsversuches
}
else
//keine weitere wahl möglich, also lösung gefunden
{
erfolgreich = true;
}
}
}
}
// Test, ob auf Feld x,y eine Dame platziert werden darf
boolean isFieldOk(int x, int y)
{
int zaehler = 0;
while (zaehler<=x)
{
if (belegt[x][zaehler] || belegt[zaehler][y])
return false; // Bedrohung senkrecht bzw. waagerecht
if (y-(x-zaehler)>=0 && y-(x-zaehler)<dim)
if (belegt[zaehler][y-(x-zaehler)])
return false; // Bedrohung diagonal von links oben
if (y+(x-zaehler)<dim && y+(x-zaehler)>=0)
if (belegt[zaehler][y+(x-zaehler)])
return false; // Bedrohung diagonal von links unten
zaehler++;
}
return true; // keine Bedrohung gefunden, Feld erlaubt
}
// Dame auf Feld setzen und Array anpassen
void setQueen( int x, int y )
{
if (!belegt[x][y])
{
belegt[x][y] = true;
mainWindow.setQueen(x ,y); // Grafik-Ausgabe
}
}
// Dame von Feld entfernen und Array anpassen
void clearQueen(int x, int y)
{
if (belegt[x][y])
{
belegt[x][y] = false;
mainWindow.clearQueen(x ,y); // Grafik-Ausgabe
}
}
}Ich bin der totale Trottel, wenn es sich um Java handelt. Für schnelle Hilfe wäre ich sehr dankbar.
MfG momba
