Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Schachbrett König von A1 bis H8, anz. Möglichkeiten
Hey, Ich überlege schon seit einer Ewigkeit wie man das Prolem lösen könnte.
Könnte ich eien Tipp haben ?
Aufgabe:
Gegeben sei ein Schachbrett mit einem König aufdem Feld A1. Nun ist die Frage, wieviele Möglichkeiten es gibt,
mit genau k Zügen den König auf das Feld H8 zu bewegen (naturlich nur mit korrekten Zügen).
Schreiben Sie ein Programm, um die Anzahl der Möglichkeiten zu berechnen.
Geben Sie die genaue Zahl für k = 10 sowie k = 13 an. Für k = 2^50 geben Sie die Lösung modulo 2^30 an.
Hinweis: Betrachten Sie die Adjazenzmatrix des Graphen, der durch die Zugmöglichkeiten des Königs de niert
wird.
Meine Fragen:
Wie ist das mit der Adjazenzmatrix gemeint?
Und wie könnte das System ausehen?
Der König kann von einem Feld nur auf erlaubte Felder, das sind die Nachbarfelder (wenn ich mich mit Schach nicht toal irre ist das gerade und diagonal mit abstand = 1).
Das Schachbrett mit seinen Nachbarschaften an sich als Graphen darstellen dürfte ziemlich langweilig sein. Was da rauskommt ist nämlich ... ... *tadaaa* ein Schachbrett
Die Adjazenzmatrix würde man nicht für das Schachbrett an sich aufstellen, sondern für die Erreichbarkeit von Feldern. Bei einem Schachbrett der Größe 3x3
Die erste Spalte ist schon ausgefüllt: Die besagt, VON welchem Feld (Spalte) man ZU welchem Feld (Zeile) ziehen kann: Von A1 kann man nach A2, B1 und B2. So kann man die übrigen Spalten auch noch füllen.
Wenn du dir das oben verlinkte Paper durchgelesen hast, weißt du, was du damit anfangen kannst.
Ich wußte schon, dass du das sofort ausklappst
Wenn du dir das oben verlinkte Paper durchgelesen (oder schonmal anderweitig drüber nachgedacht) hast, weißt du, dass man durch Multiplizieren zweier Adjazenzmatrizen Wege beschreiben kann. Wenn man so eine Matrix A hat, die besagt, welche Felder man mit einem Schritt erreichen kann, dann beschreibt die Matrix A*A eben, welche Felder man mit zwei Schritten erreichen kann. Und die Matrix A^n besagt, welche Felder man mit n Schritten erreichen kann. Praktischerweise sind die Einträge dieser Matrizen gleichzeitig die Anzahl der Wege, die es zwischen den jeweiligen Feldern gibt.
Java:
class Matrix
{
private int n;
private long a[][];
public Matrix(int n)
{
this.n = n;
a = new long[n][n];
}
public long get(int r, int c)
{
return a[r][c];
}
public void set(int r, int c, long v)
{
a[r][c] = v;
}
public Matrix mult(Matrix other)
{
Matrix result = new Matrix(n);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
for(int k = 0; k < n; k++)
{
result.a[i][j] += a[i][k] * other.a[k][j];
}
}
}
return result;
}
public String createString()
{
StringBuilder sb = new StringBuilder();
for (int r=0; r<n; r++)
{
for (int c=0; c<n; c++)
{
sb.append(String.format("%12s", a[r][c]));
}
sb.append("\n");
}
return sb.toString();
}
}
public class KingMoveCounter
{
public static void main(String[] args)
{
int n = 8;
Matrix m = new Matrix(n*n);
for (int r0=0; r0<n; r0++)
{
for (int c0=0; c0<n; c0++)
{
for (int dr=-1; dr<=1; dr++)
{
for (int dc=-1; dc<=1; dc++)
{
if (dr != 0 || dc != 0)
{
int r1 = r0+dr;
int c1 = c0+dc;
if (r1 >= 0 && r1 < n && c1 >= 0 && c1 < n)
{
int i0 = c0+r0*n;
int i1 = c1+r1*n;
m.set(i0, i1, 1);
}
}
}
}
}
}
int k=13;
Matrix c = m;
for (int i=1; i<=k; i++)
{
System.out.println("With "+i+" steps there are "+c.get(n*n-1, 0)+" paths");
//System.out.println(c.createString());
c = c.mult(m);
}
}
}
Für die Sache mit dem 2^50 muss man entweder laaange rechnen oder sich was geschicktes überlegen. Irgendwie läßt sich das modulo vielleicht mit der Matrix-Multiplikation verwursten, so dass da das meiste wegfällt .... andernfalls muss man mal schauen, ob man was mit BigInteger#modPow machen kann.
Für die Sache mit dem 2^50 muss man entweder laaange rechnen oder sich was geschicktes überlegen. Irgendwie läßt sich das modulo vielleicht mit der Matrix-Multiplikation verwursten, so dass da das meiste wegfällt
for (int k = 0; k < n; k++) {
result.a[i][j] += ((a[i][k] * other.a[k][j]) % mod);
}
result.a[i][j] = result.a[i][j] % mod;
machen, dann bleiben die Zahlen immer in dem gewünschten Bereich. Müsste eigentlich mathematisch stimmen.
Darüber hinaus muss man ja nicht immer *A rechnen. Wenn man z.B. A*A=B gerechnet hat, d.h. Ergebnis für 2 Züge, dann kann man direkt mit B*B=C Ergebnis für 4 Züge, C*C für 8 usw. Und in der Aufgabenstellung sind schon praktischer Weise 2er-Potenz angegeben, so dass man nach 50 Rechenoperationen das Ergebnis bekommt. Sowas wie:
Java:
Matrix c = m;
for (int i = 1; i <= 50; i++) {
c = c.mult(c);
System.out.println("With 2^" + i + " steps there are " + c.get(n * n - 1, 0) + " paths");
}
for (int k = 0; k < n; k++) {
result.a[i][j] += ((a[i][k] * other.a[k][j]) % mod);
}
result.a[i][j] = result.a[i][j] % mod;
machen, dann bleiben die Zahlen immer in dem gewünschten Bereich. Müsste eigentlich mathematisch stimmen.
Darüber hinaus muss man ja nicht immer *A rechnen. Wenn man z.B. A*A=B gerechnet hat, d.h. Ergebnis für 2 Züge, dann kann man direkt mit B*B=C Ergebnis für 4 Züge, C*C für 8 usw. Und in der Aufgabenstellung sind schon praktischer Weise 2er-Potenz angegeben, so dass man nach 50 Rechenoperationen das Ergebnis bekommt. Sowas wie:
Java:
Matrix c = m;
for (int i = 1; i <= 50; i++) {
c = c.mult(c);
System.out.println("With 2^" + i + " steps there are " + c.get(n * n - 1, 0) + " paths");
}
Ja, sicher würde man Exponentiation by squaring - Wikipedia, the free encyclopedia verwenden, aber BigInteger bräuchte man da dann trotzdem noch. Ob deine vorgeschlagene Verwendung von % stimmt, habe ich nicht nachvollzogen, aber sowas in der Art meinte ich, und es sieht plausibel aus (und dann würde es natürlich ohne BigInteger gehen)
