Heim > Artikel > Backend-Entwicklung > Überprüft, ob es möglich ist, vom Ursprung aus jeden Punkt auf dem Umfang eines gegebenen Kreises zu erreichen
Der Umfang eines Kreises kann als äußere Grenze des Kreises definiert werden. Es ist der Umfang des Kreises. Jeder Punkt um den Kreis herum folgt bestimmten Eigenschaften, wie unten gezeigt -
Punkt (x,y) liegt innerhalb des Kreises, sodass $mathrm{x^2 + y^2
Punkt (x,y) liegt auf dem Kreis, so dass $mathrm{x^2 + y^2 = R^2}$
Punkt (x,y) liegt außerhalb des Kreises, sodass $mathrm{x^2 + y^2 > R^2}$
Wobei R = Kreisradius.
Gegeben sei eine Zeichenfolge S, die eine Folge von Bewegungen (L, R, U, D) darstellt, und eine ganze Zahl R, die den Radius eines Kreises darstellt. Prüfen Sie, ob ein beliebiger Punkt auf dem Umfang eines Kreises mit dem Radius R mit dem Ursprung erreicht werden kann, indem Sie eine Teilfolge von Bewegungen ausgehend von S auswählen. Die Funktionsweise jeder Bewegung ist wie folgt:
L = x-Koordinate reduzieren
R = inkrementelle x-Koordinate
U = Y-Koordinateninkrement
D = Abnehmende Y-Koordinate
Eintreten
S = “RURDLR” R = 2
Ausgabe
Yes
Untersequenz „RR“ auswählen -
Anfangs (0, 0) + R -> (1, 0) + R -> (2, 0).
Umfang kann 22 + 02 = 4 = R2
seinEintreten
S = “UUUUU” R = 6
Ausgabe
No
Wählen Sie die größte Teilsequenz „UUUU“ aus –
Anfangs (0, 0) + U -> (0, 1) + U -> (0, 2) + U -> (0, 3) + U -> (0, 4) + U -> (0 , 5).
Es ist unmöglich, den Umfang zu erreichen, weil 02 + 52 = 25 R2
Die Lösung des Problems besteht darin, alle möglichen Teilfolgen der Zeichenfolge S zu finden und dann zu prüfen, ob jede Teilfolge den Kreis erreichen kann. Diese Bedingungen werden überprüft, indem Zähler für x und y verwaltet werden, wobei x bei jedem L dekrementiert und bei jedem R erhöht wird. Ebenso nimmt y mit jedem D ab und mit jedem U zu. Überprüfen Sie dann x2 + y2 = R2, um zu überprüfen, ob der Endpunkt auf dem Umfang liegt.
procedure subsequence (S, sub, vec): if S is empty add sub to vec return end if subsequence(S.substring(1), sub + S[0], vec) subsequence(S.substring(1), sub, vec) end procedure procedure checkSeq (S, R) x = 0 y = 0 for move in S do if move == 'L' then x = x - 1 else if move == 'R' then x = x + 1 else if move == 'U' then y = y + 1 else if move == 'D' then y = y - 1 end if if x^2 + y^2 = R^2 then return true end if end for return false end procedure procedure reachCircumference (S, R): v = [] subsequence(S, "", v) for str in v: if checkSeq(str, R) return "yes" end if return "no" end procedure
Erstellen Sie im folgenden Programm alle möglichen Teilfolgen der Zeichenfolge S und prüfen Sie, ob sie den Umfang des Kreises erreichen.
#include <bits/stdc++.h> using namespace std; // Function to create all the possible subsequence of string S void subsequence(string S, string sub, vector<string> &vec){ // Base Case if (S.empty()) { vec.push_back(sub); return; } // Subsequence including the character subsequence(S.substr(1), sub + S[0], vec); // Subsequence excluding the character subsequence(S.substr(1), sub, vec); } // Function to check if a given sequence of steps lead to the circumference of the circle with radius R bool checkSeq(string S, int R){ // Initialising centre of circle as (0, 0) int x = 0, y = 0; for (char move : S) { if (move == 'L') { x -= 1; } else if (move == 'R') { x += 1; } else if (move == 'U') { y += 1; } else if (move == 'D') { y -= 1; } // Check to find if (x, y) lie on circumference using the circle equation if (x*x + y*y == R*R) { return true; } } return false; } // function to check if any subsequence of string S leads to any point on the circumference of the circle string reachCircumference(string S, int R){ vector <string> v; string sub = ""; // Storing all subsequence in vector v subsequence(S, sub, v); // Checking the condition for each subsequence for (auto str: v) { if(checkSeq(str, R)) { return "yes"; break; } } return "no"; } // Driver Code int main(){ string S = "RURDLR"; int R = 2; cout << reachCircumference(S, R) << endl; return 0; }
yes
Eine effiziente Möglichkeit, dieses Problem zu lösen, besteht darin, mithilfe von (L, R, U oder D) zu überprüfen, ob die Summe der Quadrate von x und y dem Quadrat des Radius für jedes Paar von x und y entspricht.
Zuerst zählen wir die maximale Häufigkeit jedes Schritts und prüfen, ob einer davon gleich R ist. Wenn nicht gleich, prüfen wir, ob eine beliebige Anzahl von Paaren von L oder R und U oder D zu einem Distanzursprung gleich R führen kann.
procedure reachCircumference (S, R) cL = 0 cR = 0 cD = 0 cU = 0 for move in S do if move == 'L' then x = x - 1 else if move == 'R' then x = x + 1 else if move == 'U' then y = y + 1 else if move == 'D' then y = y - 1 end if if x^2 + y^2 = R^2 then return true end if end for if max(max(cL, cR), max(cD, cU)) >= R return “yes” maxLR = max(cL, cR) maxUD = max(cU, cD) Initialise unordered map mp sq = R * R for i = 1 till i * i = sq if sq - i*i is not in the map if maxLR>= mp[sq - i * i] and maxUD >= i return “yes” end if if maxLR >= i && maxUD >= mp[sq - i * i] return “yes” end if end if end for return “no” end procedure
Im folgenden Programm verwenden wir eine Karte, um zu prüfen, ob es eine Teilfolge gibt, die zum Umfang eines Kreises führt.
#include <bits/stdc++.h> using namespace std; // Function to check if any subsequence of string S leads to any point on the circumference of the circle string reachCircumference (string S, int R){ // Counting total occurrenceof each L, R, U, D int cL = 0, cR = 0, cD = 0, cU = 0; for (char move : S) { if (move == 'L') { cL++; } else if (move == 'R') { cR++; } else if (move == 'U') { cU++; } else if (move == 'D') { cD++; } } // Checking for a path to circumference using only one type of move if (max(max(cL, cR), max(cD, cU)) >= R) { return "yes"; } int maxLR = max(cL, cR), maxUD = max(cU, cD); unordered_map<int, int> mp; int sq = R * R; for (int i = 1; i * i <= sq; i++) { mp[i * i] = i; if (mp.find(sq - i * i) != mp.end()) { // Checking if it is possible to reach (± mp[r_square - i*i], ± i) if (maxLR>= mp[sq - i * i] && maxUD >= i) return "yes"; // Checking if it is possible to reach (±i, ±mp[r_square-i*i]) if (maxLR >= i && maxUD >= mp[sq - i * i]) return "yes"; } } return "no"; } // Driver Code int main(){ string S = "RURDLR"; int R = 5; cout << reachCircumference(S, R) << endl; return 0; }
no
Zusammenfassend lässt sich sagen, dass Sie eine der oben genannten Methoden verwenden können, um herauszufinden, ob Sie eine Teilfolge von Schritten in der Zeichenfolge S verwenden können, um den Umfang eines Kreises mit Mittelpunkt im Ursprung zu ermitteln. Die zweite Methode ist schneller, benötigt aber zusätzlichen Speicherplatz, während die erste Methode eine Brute-Force-Methode ist, die nicht sehr effizient, aber leicht zu verstehen ist.
Das obige ist der detaillierte Inhalt vonÜberprüft, ob es möglich ist, vom Ursprung aus jeden Punkt auf dem Umfang eines gegebenen Kreises zu erreichen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!