Ein Freund brauchte einen Algorithmus, mit dem er die Elemente einer NxM-Matrix durchlaufen konnte (N und M sind ungerade). Ich habe eine Lösung gefunden, aber ich wollte sehen, ob meine SO'-Kollegen eine bessere Lösung finden können.
Ich poste meine Lösung als Antwort auf diese Frage.
Beispielausgabe:
Für eine 3x3-Matrix sollte die Ausgabe sein:
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1 )
Darüber hinaus sollte der Algorithmus nicht quadratische Matrizen unterstützen, sodass die Ausgabe beispielsweise für eine 5x3-Matrix wie folgt lauten sollte:
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1 ) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1)
Antworten:
Hier ist meine Lösung (in Python):
quelle
C ++ jemand? Schnelle Übersetzung aus Python, der Vollständigkeit halber veröffentlicht
quelle
Es wurden viele Lösungen für dieses Problem vorgeschlagen, die in verschiedenen Programmiersprachen geschrieben wurden, aber alle scheinen aus demselben verschlungenen Ansatz zu stammen. Ich werde das allgemeinere Problem der Berechnung einer Spirale betrachten, die durch Induktion präzise ausgedrückt werden kann.
Basisfall: Beginnen Sie bei (0, 0), bewegen Sie sich 1 Feld vorwärts, biegen Sie links ab, bewegen Sie sich 1 Feld vorwärts, biegen Sie links ab. Induktiver Schritt: Bewegen Sie sich vorwärts n + 1 Quadrate, biegen Sie links ab, bewegen Sie sich vorwärts n + 1 Quadrate, biegen Sie links ab.
Die mathematische Eleganz, dieses Problem auszudrücken, legt nahe, dass es einen einfachen Algorithmus geben sollte, um die Lösung zu berechnen. Unter Berücksichtigung der Abstraktion habe ich mich entschieden, den Algorithmus nicht in einer bestimmten Programmiersprache zu implementieren, sondern als Pseudocode.
Zuerst werde ich einen Algorithmus betrachten, um nur 2 Iterationen der Spirale unter Verwendung von 4 Paaren von while-Schleifen zu berechnen. Die Struktur jedes Paares ist ähnlich, jedoch eigenständig. Dies mag zunächst verrückt erscheinen (einige Schleifen werden nur einmal ausgeführt), aber Schritt für Schritt werde ich Transformationen durchführen, bis wir zu 4 Paaren von Schleifen gelangen, die identisch sind und daher durch ein einzelnes Paar innerhalb einer anderen Schleife ersetzt werden können. Dies bietet uns eine allgemeine Lösung für die Berechnung von Iterationen ohne Verwendung von Bedingungen.
Die erste Transformation, die wir durchführen werden, ist die Einführung einer neuen Variablen d für die Richtung, die entweder den Wert +1 oder -1 enthält. Die Richtung wechselt nach jedem Schleifenpaar. Da wir den Wert von d an allen Punkten kennen, können wir jede Seite jeder Ungleichung damit multiplizieren, die Richtung der Ungleichung entsprechend anpassen und alle Multiplikationen von d mit einer Konstanten zu einer anderen Konstante vereinfachen. Dies lässt uns folgendes übrig.
Nun stellen wir fest, dass sowohl x * d als auch die RHS ganze Zahlen sind, sodass wir jeden reellen Wert zwischen 0 und 1 von der RHS subtrahieren können, ohne das Ergebnis der Ungleichung zu beeinflussen. Wir ziehen es vor, 0,5 von den Ungleichungen jedes zweiten Paares von while-Schleifen zu subtrahieren, um ein besseres Muster zu erhalten.
Wir können jetzt eine weitere Variable m für die Anzahl der Schritte einführen, die wir bei jedem Paar von while-Schleifen ausführen.
Schließlich sehen wir, dass die Struktur jedes Paares von while-Schleifen identisch ist und auf eine einzelne Schleife reduziert werden kann, die innerhalb einer anderen Schleife platziert ist. Um die Verwendung von reellen Zahlen zu vermeiden, habe ich den Anfangswert von m multipliziert. der Wert m wird erhöht um; und beide Seiten jeder Ungleichung um 2.
Dies führt zu der am Anfang dieser Antwort gezeigten Lösung.
quelle
Hier ist eine O (1) -Lösung, um die Position in einer quadratischen Spirale zu finden: Geige
quelle
if (n === 0) return [0, 0, r]; --n;
Siehe Fiddle: jsfiddle.net/Wishmesh/nwd9gt1s/2Ich liebe Pythons Generatoren.
Testen mit:
Du erhältst:
quelle
Java-Spiralversuch "Code Golf", basierend auf der C ++ - Variante.
quelle
Hier ist eine C ++ - Lösung, die zeigt, dass Sie die nächsten (x, y) Koordinaten direkt und einfach aus den vorherigen berechnen können - ohne die aktuelle Richtung, den Radius oder irgendetwas anderes verfolgen zu müssen:
Wenn Sie nur versuchen, die ersten N Punkte in der Spirale zu generieren (ohne die Einschränkung des ursprünglichen Problems, einen N x M-Bereich zu maskieren), wird der Code sehr einfach:
Der Trick besteht darin, dass Sie x und y vergleichen können, um festzustellen, auf welcher Seite des Quadrats Sie sich befinden, und dass Sie wissen, in welche Richtung Sie sich bewegen müssen.
quelle
TDD in Java.
SpiralTest.java:
Spiral.java:
quelle
Hier ist meine Lösung (In Ruby)
quelle
Haskell, treffen Sie Ihre Wahl:
quelle
Dies ist in C.
Ich habe zufällig schlechte Variablennamen gewählt. In den Namen T == oben, L == links, B == unten, R == rechts. Also ist tli oben links i und brj ist unten rechts j.
quelle
Ich habe eine Open-Source-Bibliothek, Pixelscan , eine Python-Bibliothek, die Funktionen zum Scannen von Pixeln in einem Raster in verschiedenen räumlichen Mustern bietet. Die enthaltenen räumlichen Muster sind kreisförmig, Ringe, Gitter, Schlangen und zufällige Spaziergänge. Es gibt auch verschiedene Transformationen (z. B. Clip, Swap, Rotate, Translate). Das ursprüngliche OP-Problem kann wie folgt gelöst werden
das ergibt die Punkte
Die Bibliotheksgeneratoren und -transformationen können verkettet werden, um die Punkte in einer Vielzahl von Ordnungen und räumlichen Mustern zu ändern.
quelle
Hier ist eine Lösung in Python 3 zum Drucken aufeinanderfolgender Ganzzahlen im Uhrzeigersinn und gegen den Uhrzeigersinn.
Erläuterung
Eine Spirale besteht aus konzentrischen Quadraten, zum Beispiel sieht ein 5x5-Quadrat mit Drehung im Uhrzeigersinn folgendermaßen aus:
(
>>>>>
bedeutet "5-mal nach rechts gehen" oder Spaltenindex 5-mal erhöhen, Zeilenindex nachv
unten oder erhöhen usw.)Alle Quadrate sind bis zu ihrer Größe gleich, ich habe die konzentrischen Quadrate durchlaufen.
Für jedes Quadrat hat der Code vier Schleifen (eine für jede Seite). In jeder Schleife erhöhen oder verringern wir den Spalten- oder Zeilenindex. Wenn
i
es sich um den Zeilenindex undj
den Spaltenindex handelt, kann ein 5x5-Quadrat erstellt werden durch: - Inkrementierenj
von 0 auf 4 (5 Mal) - Inkrementiereni
von 1 auf 4 (4 Mal) - Dekrementierenj
von 3 auf 0 (4 Mal) - Dekrementiereni
von 3 bis 1 (3 mal)Für die nächsten Quadrate (3x3 und 1x1) machen wir dasselbe, verschieben jedoch den Anfangs- und den Endindex entsprechend. Ich habe
k
für jedes konzentrische Quadrat einen Index verwendet , es gibt n // 2 + 1 konzentrische Quadrate.Zum Schluss noch ein bisschen Mathe zum hübschen Drucken.
So drucken Sie die Indizes:
quelle
Hier ist c #, linq'ish.
Das erste Beispiel der Frage (3x3) wäre:
Das zweite Beispiel der Frage (5x3) wäre:
quelle
Dies ist eine etwas andere Version - versucht,
recursion
unditerators
in LUA zu verwenden. Bei jedem Schritt steigt das Programm weiter in die Matrix und die Schleifen ab. Ich habe auch eine zusätzliche Flagge zu Spiraleclockwise
oder hinzugefügtanticlockwise
. Die Ausgabe beginnt in den unteren rechten Ecken und verläuft rekursiv zur Mitte.quelle
// PHP-Implementierung
quelle
Hier ist eine iterative JavaScript (ES6) -Lösung für dieses Problem:
So verwenden Sie es:
spiralMatrix(0, 0, 1, 100);
Dies erzeugt eine nach außen gerichtete Spirale, beginnend bei den Koordinaten (x = 0, y = 0) mit Schritt 1 und einer Gesamtzahl von Elementen gleich 100. Die Implementierung startet die Bewegung immer in der folgenden Reihenfolge - oben, rechts, unten, links.
Bitte beachten Sie, dass diese Implementierung quadratische Matrizen erstellt.
quelle
Hier ist eine Antwort in Julia: Mein Ansatz besteht darin, die Punkte in konzentrischen Quadraten ('Spiralen') um den Ursprung herum zuzuweisen
(0,0)
, wobei jedes Quadrat eine Seitenlängem = 2n + 1
hat, um ein geordnetes Wörterbuch mit Positionsnummern (beginnend mit 1 für den Ursprung) als Schlüssel zu erstellen und die entsprechende Koordinate als Wert.Da die maximale Position pro Spirale bei liegt
(n,-n)
, können die restlichen Punkte gefunden werden, indem einfach von diesem Punkt aus rückwärts gearbeitet wird, dh von der unteren rechten Ecke nachm-1
Einheiten, und dann für die senkrechten 3 Segmente von wiederholt wirdm-1
Einheiten .Dieser Prozess wird unten in umgekehrter Reihenfolge geschrieben, entsprechend dem Verlauf der Spirale und nicht diesem umgekehrten Zählprozess, dh das
ra
Segment [rechts aufsteigend] wird um dekrementiert3(m+1)
, dann umla
[links aufsteigend]2(m+1)
usw. - hoffentlich ist dies selbsterklärend .Wenn Sie also für Ihr erstes Beispiel
m = 3
die Gleichung eingeben , um n zu findenn = (5-1)/2 = 2
, erhalten Siewalk(2)
ein geordnetes Wörterbuch mit Positionen für Koordinaten, das Sie durch Zugriff auf dasvals
Feld des Wörterbuchs in ein Array von Koordinaten umwandeln können:Beachten Sie, dass es für einige Funktionen [z. B.
norm
] vorzuziehen ist, die Koordinaten in ArraysTuple{Int,Int}
zu belassen(x,y)
, anstatt sie hier in Tupel umzuwandeln - wie gewünscht, unter Verwendung des Listenverständnisses.Der Kontext für „Unterstützung“ eine nicht-quadratische Matrix nicht angegeben ist ( man beachte , dass diese Lösung immer noch die Off-Grid - Werte berechnet), aber wenn Sie filtern mögen nur auf den Bereich
x
vony
(hierx=5
,y=3
) nach der vollständigen Spirale Berechnung dannintersect
diese Matrix gegen die Werte vonwalk
.quelle
Ihre Frage sieht aus wie eine Frage namens Spiralspeicher. In diesem Problem wird jedes Quadrat auf dem Gitter in einem Spiralmuster beginnend mit der Nummer 1 zugewiesen, die sich am Ursprung befindet. Und dann hochzählen, während wir uns nach außen drehen. Beispielsweise:
Meine Lösung zur Berechnung der Koordinaten jeder Zahl nach diesem Spiralmuster ist unten aufgeführt:
quelle
Dies basiert auf Ihrer eigenen Lösung, aber wir können klüger sein, wenn es darum geht, die Ecken zu finden. Auf diese Weise können Sie leichter erkennen, wie Sie die Bereiche außerhalb überspringen können, wenn M und N sehr unterschiedlich sind.
und eine generatorbasierte Lösung, die besser als O ist (max (n, m) ^ 2). Es ist O (nm + abs (nm) ^ 2), weil ganze Streifen übersprungen werden, wenn sie nicht Teil der Lösung sind.
quelle
quelle
Dies ist meine sehr, sehr schlechte Lösung, die aus minimalen Java-Kenntnissen besteht. Hier muss ich Einheiten spiralförmig auf ein Feld legen. Einheiten können nicht auf anderen Einheiten oder auf Bergen oder im Ozean platziert werden.
Deutlich sein. Dies ist keine gute Lösung. Dies ist eine sehr schlechte Lösung, die zum Spaß anderer Leute hinzugefügt wurde, um darüber zu lachen, wie schlecht es gemacht werden kann
Ein großes Lob an alle, die dies tatsächlich lesen können
Bonusfrage: Was ist die Laufzeit dieses "Algorithmus"? : P.
quelle
Lösung für AutoIt
quelle
Ich hatte kürzlich eine ähnliche Herausforderung, bei der ich ein 2D-Array erstellen und einen Spiralmatrix-Algorithmus verwenden musste, um die Ergebnisse zu sortieren und zu drucken. Dieser C # -Code funktioniert mit einem N, N 2D-Array. Es ist aus Gründen der Klarheit ausführlich und kann wahrscheinlich an Ihre Bedürfnisse angepasst werden.
quelle
Ich habe dieses mit einem Freund gemacht, der die Spirale an das Seitenverhältnis der Leinwand in Javascript anpasst. Die beste Lösung für eine Bildentwicklung Pixel für Pixel, die das gesamte Bild ausfüllt.
Hoffe es hilft jemandem.
Sie können es auf http://jsfiddle.net/hitbyatruck/c4Kd6/ sehen . Stellen Sie nur sicher, dass Sie die Breite und Höhe der Zeichenfläche in den Javascript-Variablen und in den Attributen im HTML ändern.
quelle
Nur zum Spaß in Javascript:
quelle
C # -Version, auch nicht quadratische Größen.
quelle
Ich teile diesen Code, den ich für einen anderen Zweck entworfen habe. Es geht darum, die Spaltennummer "X" und die Zeilennummer "Y" des Array-Elements @ Spiral-Index "Index" zu finden. Diese Funktion verwendet die Breite "w" und Höhe "h" der Matrix sowie den erforderlichen "Index". Natürlich kann diese Funktion verwendet werden, um die gleiche erforderliche Ausgabe zu erzeugen. Ich denke, es ist die schnellstmögliche Methode (da sie über Zellen springt, anstatt sie zu scannen).
quelle
Python-Schleifen-Spiralcode im Uhrzeigersinn mit der Antwort von Can Berk Güder .
quelle
Davidonts hervorragende Lösung in VB.Net
quelle