Ü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

gilt

• 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}$

gilt

Wobei R = Kreisradius.

Problemstellung

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

Beispiel 1

Eintreten

S = “RURDLR”
R = 2

Ausgabe

yes

Anleitung

Untersequenz „RR“ auswählen -

Anfangs (0, 0) + R -> (1, 0) + R -> (2, 0).

Umfang kann 2² + 02 = 4 = R²

sein

Beispiel 2

Eintreten

S = “UUUUU”
R = 6

Ausgabe

no

Anleitung

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 0² + 5² = 25 R²

Methode 1: Brute-Force-Cracking

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 x² + y² = R², um zu überprüfen, ob der Endpunkt auf dem Umfang liegt.

Pseudocode

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

Beispiel: C++-Implementierung

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;
}

Ausgabe

yes

Methode 2: Optimierungsmethode

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.

Pseudocode

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

Das Folgende ist die C++-Implementierung,

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;
}

Ausgabe

no

Fazit

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!