Prüfen Sie, Ob es existiert ein Kreis
Wurde ich gebeten, dies bei einem Google-Interview.
Wir sind eine Zeichenfolge, die aus Buchstaben - F -, L -, R. - und das ist die Anweisung, einen Roboter folgt
F - geht vorwärts mit einem Schritt.
L-biegen Sie Links ab.
R - rechts.
String-Länge kann bis zu 2500 Zeichen.
Den string selbst läuft, unendlich oft. Wir müssen sagen, wenn es einen Kreis mit einem radius r( r ist eine beliebige reelle Zahl), so dass der Roboter nie aus dem Kreis.
Ich hing an dieser Stelle.Ich dachte, der Verwendung von konvexen Hülle, aber wie es zu überprüfen für unendliche Zeiten.Erklärung mit code, werden geschätzt. Bitte helfen Sie. Vielen Dank im Voraus
- Untersuchen Sie das Thema der random walks auf Gittern.
- Falsche Frage oder nicht, die Menschen die Zeit genommen, Sie zu beantworten. Sie können Fragen, eine neue, wenn Sie wollen, aber bitte nicht diese entfernen.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ist die Anzahl der möglichen Richtungen ist 4. Also, nach dem ausführen der simulation 4-mal sieht es aus in der gleichen Richtung, wie Sie es Tat zunächst(jede reiben dreht es sich um den selben Winkel).
Deshalb die folgenden 4 läuft einfach verschieben, indem ein Vektor ohne rotation.
So, wir können nur das ausführen der simulation 4 mal in einer Reihe und sehen, ob es blieb in der ursprünglichen Stelle. Wenn es getan hat, finden wir die Mindest-Kreis mit seinen Pfad. Sonst kein solcher Kreis existiert.
Führen Sie 1 iteration zur Berechnung der neuen position, sagen, newx, newy.
Dann würden Sie berechnen Sie 4 Iterationen, um zu sehen, ob der Roboter ist wieder newx-newy. Wenn dem so ist, dann ist der Kreis vorhanden ist, sonst nicht.
Den radius wäre der maximale Abstand der Roboter wagte sich in seine iteration.
Code-Implementierung -
F
, undL
machen Sie nicht den move, also in deinemswitch
Blöcke für diese Befehle nurdir
geändert werden sollte. Aber diese Ungenauigkeit ändert aber nichts an der kompletten AlgorithmusFühren Sie die saite, sehen, wo der Roboter am Ende ist und in welche Richtung es schaut.
Wenn es zurück an den Ursprung, die maximale Entfernung vom Ursprung es hatte, während der Ausführung und zu vergleichen, um r.
Wenn es nicht zurück in den Ursprung, dann überprüfen Sie seine Orientierung:
Wenn es hat die gleiche Ausrichtung wie in der Anfang, dann wird es eine Bewegung Weg vom Ursprung auf unbestimmte Zeit, so dass kein solches r existiert.
Wenn es eine andere Orientierung als in den Anfang, dann wird es wieder zu dem Ursprung nach 4 oder 2 Iterationen der Zeichenfolge, je nachdem, ob es ausgerichtet ist auf die Links/rechts von der ursprünglichen Ausrichtung, oder das Gegenteil von ihm ist, jeweils. Nehmen Sie nun den maximalen Abstand, den er hatte nach 2 Ausführungen der Zeichenfolge. (Einfache groß - /Kleinschreibung wird zeigen, dass es besucht haben, seine maximale Entfernung, nach 2 Ausführungen, egal ob die Periode 2 oder 4 Ausführungen.)
}
F
, nichtG
.Dies funktionieren könnte:
Durchlaufen der angegebenen Zeichenfolge einmal und notieren Sie die Verschiebung und die Richtung, in der Sie am Ende. Wenn die Verschiebung ist nicht null, und die Start-und End-Anweisungen sind die gleichen für die Roboter für die einzelne iteration, Ihren Roboter nicht enthalten sein, in einem Kreis, sonst kann es sein.
Abbildung:
In der Abbildung wird davon ausgegangen, dass der Roboter fährt von Punkt A zu Punkt B, nach einer einzigen iteration der angegebenen Zeichenfolge. Nun, der Winkel ABC ist (90 - theta), der Winkel ABD gleich 90 Grad. Mit allen Seiten gleich, und jeder Winkel gleich 90 Grad, viereck ABDE ist ein Quadrat. Dies gilt für jeden Wert von theta (Spitzen oder stumpfen). Der Beweis wäre ähnlich, wenn das Ende Richtung nach einer einzigen iteration ist Links. Für die Süd -, die Roboter schwingen wird zwischen den Punkten A und B.
Daher, wie eine Lösung für Ihr problem, Sie konnte nur prüfen, ob die Start-und End-Richtung sind die gleichen, und dass die Start-und die Endposition nicht gleich sind, nachdem der Roboter abgeschlossen wird eine iteration der angegebenen Zeichenfolge.