圆的周长可以定义为圆的外边界。它是圆的周长。圆周围的每个点都遵循某些属性，如下所示 –
点 (x,y) 位于圆内，使得 $mathrm{x^2 + y^2
点 (x,y) 位于圆上，使得 $mathrm{x^2 + y^2 = R^2}$
点 (x,y) 位于圆外，使得 $mathrm{x^2 + y^2 > R^2}$
其中 R = 圆的半径。
问题陈述
给定一个表示一系列移动（L、R、U、D）的字符串 S 和一个表示圆半径的整数 R。检查是否可以通过选择从S开始的任何移动子序列来到达以原点为半径为R的圆的圆周上的任何点。每个移动的操作如下所示，
L = 减少 x 坐标
R = 增量 x 坐标
U = y 坐标增量
D = 递减 y 坐标
示例 1
输入
S = “RURDLR”R = 2
输出
Yes
说明
选择子序列“RR” –
最初，(0, 0) + R -> (1, 0) + R -> (2, 0)。
周长可能为 22 + 02 = 4 = R2
示例 2
输入
S = “UUUUU”R = 6
输出
No
说明
选择最大的子序列“UUUU” –
最初，(0, 0) + U -> (0, 1) + U -> (0, 2) + U -> (0, 3) + U -> (0, 4) + U -> (0, 5)。
不可能达到圆周，因为 02 + 52 = 25 R2
方法 1：暴力破解
问题的解决方法是找到字符串S的所有可能的子序列，然后检查每个子序列是否可以到达圆周。通过维护 x 和 y 的计数器来检查这些条件，其中 x 在每个 L 上递减并在每个 R 上递增。类似地，y 在每个 D 上递减并在每个 U 上递增。然后检查 x2 + y2 = R2 检查终点是否在圆周上。
伪代码
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 procedureprocedure 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 falseend procedureprocedure reachCircumference (S, R): v = [] subsequence(S, "", v) for str in v: if checkSeq(str, R) return "yes" end if return "no"end procedure
示例：C++ 实现
在下面的程序中，创建字符串 S 的所有可能的子序列，并检查它们是否到达圆的圆周。
#include using namespace std;// Function to create all the possible subsequence of string Svoid subsequence(string S, string sub, vector &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 Rbool 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 circlestring reachCircumference(string S, int R){ vector 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 Codeint main(){ string S = "RURDLR"; int R = 2; cout << reachCircumference(S, R) << endl; return 0;}
输出
yes
方法2：优化方法
解决该问题的一个有效方法是检查使用（L、R、U 或 D）的任意一对 x 和 y 的 x 和 y 的平方和是否等于半径的平方。
首先，我们计算每个步骤的最大出现次数，并检查是否有任何一个等于 R。如果不相等，则我们检查是否有任何数量的 L 或 R 以及 U 或 D 的对可以导致等于 R 的距离起源。
伪代码
procedure reachCircumference (S, R) cL = 0 cR = 0 cD = 0 cU = 0 for move in S doif move == 'L' thenx = x - 1else if move == 'R' thenx = x + 1else if move == 'U' theny = y + 1else if move == 'D' theny = y - 1end ifif x^2 + y^2 = R^2 thenreturn trueend ifend for if max(max(cL, cR), max(cD, cU)) >= R return “yes” maxLR = max(cL, cR)maxUD = max(cU, cD)Initialise unordered map mpsq = R * Rfor 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 ifend forreturn “no”end procedure
下面是 C++ 实现，
在下面的程序中，我们使用映射来检查是否存在通向圆周长的子序列。
#include using namespace std;// Function to check if any subsequence of string S leads to any point on the circumference of the circlestring 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 mp; int sq = R * R; for (int i = 1; i * i = 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 Codeint main(){ string S = "RURDLR"; int R = 5; cout << reachCircumference(S, R) << endl; return 0;}
输出
no
结论
总之，为了找出是否可以使用字符串 S 中的步骤子序列来获得以原点为中心的圆的周长，可以使用上述任何方法。第二种方法是更快的方法，但使用额外的空间，而第一种方法是强力方法，效率不是很高，但易于理解。
以上就是检查是否可能从原点到达给定圆的周长上的任意点的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444039.html
微信扫一扫 
支付宝扫一扫 
