009
14.09.2002, 21:31 Uhr
~NemoEimi
Gast
|
Hi,
> Von diesen Startpunkten aus sind jeweils 44 Wege möglich.
Mein Java-Programm findet 120 Wege pro Startpunkt. Hier ist es:
| C++: |
import java.util.*;
public class nikolaus {
public static void main(String[] args) {
int AnzahlLoesungen = 0;
for (int i = 0; i < 6; i++) {
HausProblem haus = new HausProblem(i);
haus.ShowAllSolutions();
AnzahlLoesungen = AnzahlLoesungen + haus.AnzahlGefundenerLoesungen;
}
System.out.println("Es wurden " + AnzahlLoesungen + " Loesungen gefunden.");
}
}
abstract class ProblemSolver {
public int AnzahlGefundenerLoesungen = 0;
public abstract void ZugAusfuehren(int n);
public abstract void ZugZurueck();
public abstract void LoesungZeigen();
public abstract boolean EndknotenErreicht();
public abstract int ErzeugeZugliste();
public abstract boolean LoesungGefunden();
public int AnzahlZugmoeglichkeiten() {
int n = ErzeugeZugliste();
return(n);
}
public void ShowAllSolutions() {
if (LoesungGefunden()) {LoesungZeigen(); AnzahlGefundenerLoesungen++; return;}
if (EndknotenErreicht()) {return;}
int n = AnzahlZugmoeglichkeiten();
for (int i = 0; i < n; i++) {
ZugAusfuehren(i);
ShowAllSolutions();
ZugZurueck();
}
return;
}
}
class HausProblem extends ProblemSolver {
private int Variantentiefe = 0;
private int StiftPosition;
private int StartPosition;
private int[] GegenwaertigUntersuchteVariante = new int[11];
private int[][] ZugListe = new int[5][11];
private char[][] VerbindungsMatrix =
{
{0,1,1,1,0,0},
{1,0,1,0,1,0},
{1,1,0,1,1,0},
{1,0,1,0,1,1},
{0,1,1,1,0,1},
{0,0,0,1,1,0}
};
public void ZugAusfuehren(int n) {
int k = ZugListe[n][Variantentiefe]; Variantentiefe = Variantentiefe + 1;
VerbindungsMatrix[k][StiftPosition]=0; VerbindungsMatrix[StiftPosition][k]=0;
StiftPosition = k;
GegenwaertigUntersuchteVariante[Variantentiefe] = k;
}
public void ZugZurueck() {
Variantentiefe = Variantentiefe - 1;
int k = GegenwaertigUntersuchteVariante[Variantentiefe];
VerbindungsMatrix[k][StiftPosition]=1; VerbindungsMatrix[StiftPosition][k]=1;
StiftPosition = k;
}
public void LoesungZeigen() {
for (int i = 0; i <= 10; i++)
System.out.print(GegenwaertigUntersuchteVariante[i]);
System.out.print("\n");
}
public boolean EndknotenErreicht() {
for (int i = 0; i < 6; i++)
if (VerbindungsMatrix[StiftPosition][i]==1) return(false);
return(true);
}
public int ErzeugeZugliste() {
int AnzahlZuege = 0;
for (int i = 0; i < 6; i++)
if (VerbindungsMatrix[StiftPosition][i]==1) {ZugListe[AnzahlZuege][Variantentiefe]=i;AnzahlZuege=AnzahlZuege+1;}
return(AnzahlZuege);
}
public boolean LoesungGefunden() {
for (int i = 0; i < 6; i++)
for (int j = 0; j < 6; j++)
if (VerbindungsMatrix[i][j]==1) return(false);
return(true);
}
public HausProblem(int n) {
StiftPosition=n;
StartPosition=n;
GegenwaertigUntersuchteVariante[Variantentiefe]=n;
}
}
|
Bei der Ausgabe der Wege steht eine Null für den Punkt ganz links unten, eine 1 für den Punkt rechts unten, eine zwei für den Punkt in der Mitte, usw.
Die Tatsache, daß wir verschiedene Lösungszahlen haben hängt vermutlich mit dem Umstand zusammen, daß ich im Mittelpunkt eine Wegänderung erlaube.
Das Programm ist sehr primitiv, insbesondere die Endknotenbestimmung in der HausProblem-Klasse ist auf trivialem Wege verbesserbar.
Wenn ich mal Zeit habe, werde ich vielleicht versuchen, mir zu überlegen, ob man die Anzahl der Wege auch analytisch herausfinden kann  .
Grüße,
NemoEimi |
