s********d
发帖数: 36 | 1 机器人可以接受一串指令，指令只有三种：
G 走一步 L 左转 R 右转
要求判断一串指令是否造成死循环 比如 R 会造成死循环 GLGR则不会
目前想到可以分情况简化指令:
RRRR, LLLL, RL, LR 用 ‘’ 替换
RRR 用 L 替换
LLL 用 R 替换
LR, RL用U替换 表示u turn
最后可以简化成一些固定的排列组合，省略开头的G语句，因为对死循环与否没有影响
固定排列组合为 RG LG UG
然后问题来了如何判断是否死循环
没有G语句显然是死循环
不知道其他的方面怎么去思考比较好，另外感觉这个算法复杂度也比较高。
谢谢！ |
s********l
发帖数: 998 | 2 这题怎么定义死循环啊
是原地不动 还是走了一圈回到原点？ |
s********d
发帖数: 36 | 3 死循环指活动范围在一个固定的range里面 比如在一个1万歩的框里转圈也算 |
l******s
发帖数: 3045 | 4 At least a 2-d bool array or List can do it. Need more optimized ideas. |
m*********t
发帖数: 527 | 5 如果一串指令结束后，
1）没有位移，
2）或者有位移但是前进方向改变 （比如转了90 或者 180 度）
那么这串指令一定会让机器人回到原点并且保持原来的前进方向。证明是这样的：
如果位移的距离用一个矢量 s 表示, 转动可以用一个 矩阵 g 来表示，那么当这串指
令执行很多次以后，机器人的位移是：
(1 + g + g^2 + g^3 + ...) * s
如果是转动 90 度， 那么 (1 + g + g^2 + g^3) == 0，也就是说四次这串指令一定
让机器人回到原位，并且 4 次指令一定会让机器人的方向转回原位。如果是转动 180
度那么只需要 2 次。 除非 g = e （没有转动）并且 s != 0。这些属于 D4 群的性质
，而且可以扩展到其他情形。比如说允许转动比如 30 60 90 120 等等这些角度，那么
对应的是 D6 群的性质。
总之，你只需要把指令扫一遍，track 最后的 位移和是否有转动方向就行了。 |
b***e
发帖数: 1419 | 6 把这个指令序列执行4遍，如果回到原点，则循环，否则无循环。
【在 s********d 的大作中提到】
: 机器人可以接受一串指令，指令只有三种：
: G 走一步 L 左转 R 右转
: 要求判断一串指令是否造成死循环 比如 R 会造成死循环 GLGR则不会
: 目前想到可以分情况简化指令:
: RRRR, LLLL, RL, LR 用 ‘’ 替换
: RRR 用 L 替换
: LLL 用 R 替换
: LR, RL用U替换 表示u turn
: 最后可以简化成一些固定的排列组合，省略开头的G语句，因为对死循环与否没有影响
: 固定排列组合为 RG LG UG
|
s********d
发帖数: 36 | 7 所以说就是扫描一遍 检测是否有至少有一个G 和 R和L的数量是否相等？因为只有R和L
数量相等才能抵消旋转，否则在若干次旋转后都会循环？
其实当时也试了这个算法，结果有一些test case还是没过。因为看不见test case所以
也不知道怎么回事。
180
【在 m*********t 的大作中提到】
: 如果一串指令结束后，
: 1）没有位移，
: 2）或者有位移但是前进方向改变 （比如转了90 或者 180 度）
: 那么这串指令一定会让机器人回到原点并且保持原来的前进方向。证明是这样的：
: 如果位移的距离用一个矢量 s 表示, 转动可以用一个 矩阵 g 来表示，那么当这串指
: 令执行很多次以后，机器人的位移是：
: (1 + g + g^2 + g^3 + ...) * s
: 如果是转动 90 度， 那么 (1 + g + g^2 + g^3) == 0，也就是说四次这串指令一定
: 让机器人回到原位，并且 4 次指令一定会让机器人的方向转回原位。如果是转动 180
: 度那么只需要 2 次。 除非 g = e （没有转动）并且 s != 0。这些属于 D4 群的性质
|
s********d
发帖数: 36 | 8 这个好像有道理 回到原点应该指的是执行第1，2，3，4遍完整程序时刚好回到原点？
【在 b***e 的大作中提到】
: 把这个指令序列执行4遍，如果回到原点，则循环，否则无循环。
|
r******y
发帖数: 21 | 9 这道题其实解法不难。
假设walk()为执行一次所有的指令。那么：
do{
walk();
}while(direction != north)
return current_Coordiante == origin;
因为方向只会变化90度，这个循环最多执行4次就结束了。 |
m*********t
发帖数: 527 | 10 如果 R 和 L 数量不相等你也可以转回原来的方向，比如 L L L L 就行了。至少有
一个 G 也不能保证你有 不为 0 的位移。
直接计算每个基本指令之后，走到哪里了，面朝哪里，这个不难。
上面很多人说的是，把指令串执行四次。但实际上你只需要执行一次就行了。4 次完全
没有必要。
和L
【在 s********d 的大作中提到】
: 所以说就是扫描一遍 检测是否有至少有一个G 和 R和L的数量是否相等？因为只有R和L
: 数量相等才能抵消旋转，否则在若干次旋转后都会循环？
: 其实当时也试了这个算法，结果有一些test case还是没过。因为看不见test case所以
: 也不知道怎么回事。
:
: 180
|
|
|
l******s
发帖数: 3045 | 11 赞
180
【在 m*********t 的大作中提到】
: 如果一串指令结束后，
: 1）没有位移，
: 2）或者有位移但是前进方向改变 （比如转了90 或者 180 度）
: 那么这串指令一定会让机器人回到原点并且保持原来的前进方向。证明是这样的：
: 如果位移的距离用一个矢量 s 表示, 转动可以用一个 矩阵 g 来表示，那么当这串指
: 令执行很多次以后，机器人的位移是：
: (1 + g + g^2 + g^3 + ...) * s
: 如果是转动 90 度， 那么 (1 + g + g^2 + g^3) == 0，也就是说四次这串指令一定
: 让机器人回到原位，并且 4 次指令一定会让机器人的方向转回原位。如果是转动 180
: 度那么只需要 2 次。 除非 g = e （没有转动）并且 s != 0。这些属于 D4 群的性质
|
s********d
发帖数: 36 | 12 机器人可以接受一串指令，指令只有三种：
G 走一步 L 左转 R 右转
要求判断一串指令是否造成死循环 比如 R 会造成死循环 GLGR则不会
目前想到可以分情况简化指令:
RRRR, LLLL, RL, LR 用 ‘’ 替换
RRR 用 L 替换
LLL 用 R 替换
LR, RL用U替换 表示u turn
最后可以简化成一些固定的排列组合，省略开头的G语句，因为对死循环与否没有影响
固定排列组合为 RG LG UG
然后问题来了如何判断是否死循环
没有G语句显然是死循环
不知道其他的方面怎么去思考比较好，另外感觉这个算法复杂度也比较高。
谢谢！ |
s********l
发帖数: 998 | 13 这题怎么定义死循环啊
是原地不动 还是走了一圈回到原点？ |
s********d
发帖数: 36 | 14 死循环指活动范围在一个固定的range里面 比如在一个1万歩的框里转圈也算 |
l******s
发帖数: 3045 | 15 At least a 2-d bool array or List can do it. Need more optimized ideas. |
m*********t
发帖数: 527 | 16 如果一串指令结束后，
1）没有位移，
2）或者有位移但是前进方向改变 （比如转了90 或者 180 度）
那么这串指令一定会让机器人回到原点并且保持原来的前进方向。证明是这样的：
如果位移的距离用一个矢量 s 表示, 转动可以用一个 矩阵 g 来表示，那么当这串指
令执行很多次以后，机器人的位移是：
(1 + g + g^2 + g^3 + ...) * s
如果是转动 90 度， 那么 (1 + g + g^2 + g^3) == 0，也就是说四次这串指令一定
让机器人回到原位，并且 4 次指令一定会让机器人的方向转回原位。如果是转动 180
度那么只需要 2 次。 除非 g = e （没有转动）并且 s != 0。这些属于 D4 群的性质
，而且可以扩展到其他情形。比如说允许转动比如 30 60 90 120 等等这些角度，那么
对应的是 D6 群的性质。
总之，你只需要把指令扫一遍，track 最后的 位移和是否有转动方向就行了。 |
b***e
发帖数: 1419 | 17 把这个指令序列执行4遍，如果回到原点，则循环，否则无循环。
【在 s********d 的大作中提到】
: 机器人可以接受一串指令，指令只有三种：
: G 走一步 L 左转 R 右转
: 要求判断一串指令是否造成死循环 比如 R 会造成死循环 GLGR则不会
: 目前想到可以分情况简化指令:
: RRRR, LLLL, RL, LR 用 ‘’ 替换
: RRR 用 L 替换
: LLL 用 R 替换
: LR, RL用U替换 表示u turn
: 最后可以简化成一些固定的排列组合，省略开头的G语句，因为对死循环与否没有影响
: 固定排列组合为 RG LG UG
|
s********d
发帖数: 36 | 18 所以说就是扫描一遍 检测是否有至少有一个G 和 R和L的数量是否相等？因为只有R和L
数量相等才能抵消旋转，否则在若干次旋转后都会循环？
其实当时也试了这个算法，结果有一些test case还是没过。因为看不见test case所以
也不知道怎么回事。
180
【在 m*********t 的大作中提到】
: 如果一串指令结束后，
: 1）没有位移，
: 2）或者有位移但是前进方向改变 （比如转了90 或者 180 度）
: 那么这串指令一定会让机器人回到原点并且保持原来的前进方向。证明是这样的：
: 如果位移的距离用一个矢量 s 表示, 转动可以用一个 矩阵 g 来表示，那么当这串指
: 令执行很多次以后，机器人的位移是：
: (1 + g + g^2 + g^3 + ...) * s
: 如果是转动 90 度， 那么 (1 + g + g^2 + g^3) == 0，也就是说四次这串指令一定
: 让机器人回到原位，并且 4 次指令一定会让机器人的方向转回原位。如果是转动 180
: 度那么只需要 2 次。 除非 g = e （没有转动）并且 s != 0。这些属于 D4 群的性质
|
s********d
发帖数: 36 | 19 这个好像有道理 回到原点应该指的是执行第1，2，3，4遍完整程序时刚好回到原点？
【在 b***e 的大作中提到】
: 把这个指令序列执行4遍，如果回到原点，则循环，否则无循环。
|
r******y
发帖数: 21 | 20 这道题其实解法不难。
假设walk()为执行一次所有的指令。那么：
do{
walk();
}while(direction != north)
return current_Coordiante == origin;
因为方向只会变化90度，这个循环最多执行4次就结束了。 |
|
|
m*********t
发帖数: 527 | 21 如果 R 和 L 数量不相等你也可以转回原来的方向，比如 L L L L 就行了。至少有
一个 G 也不能保证你有 不为 0 的位移。
直接计算每个基本指令之后，走到哪里了，面朝哪里，这个不难。
上面很多人说的是，把指令串执行四次。但实际上你只需要执行一次就行了。4 次完全
没有必要。
和L
【在 s********d 的大作中提到】
: 所以说就是扫描一遍 检测是否有至少有一个G 和 R和L的数量是否相等？因为只有R和L
: 数量相等才能抵消旋转，否则在若干次旋转后都会循环？
: 其实当时也试了这个算法，结果有一些test case还是没过。因为看不见test case所以
: 也不知道怎么回事。
:
: 180
|
l******s
发帖数: 3045 | 22 赞
180
【在 m*********t 的大作中提到】
: 如果一串指令结束后，
: 1）没有位移，
: 2）或者有位移但是前进方向改变 （比如转了90 或者 180 度）
: 那么这串指令一定会让机器人回到原点并且保持原来的前进方向。证明是这样的：
: 如果位移的距离用一个矢量 s 表示, 转动可以用一个 矩阵 g 来表示，那么当这串指
: 令执行很多次以后，机器人的位移是：
: (1 + g + g^2 + g^3 + ...) * s
: 如果是转动 90 度， 那么 (1 + g + g^2 + g^3) == 0，也就是说四次这串指令一定
: 让机器人回到原位，并且 4 次指令一定会让机器人的方向转回原位。如果是转动 180
: 度那么只需要 2 次。 除非 g = e （没有转动）并且 s != 0。这些属于 D4 群的性质
|
b********r
发帖数: 620 | 23 大牛，您的解答一开始都看不懂。后来用自己还没有还给老师的坐标变化，画了图（分
90，180， 270）才明白你的意思。
请问这是这是物理，还是计算几何知识？还请问您的背景，是计算机，数学，物理？
180
【在 m*********t 的大作中提到】
: 如果一串指令结束后，
: 1）没有位移，
: 2）或者有位移但是前进方向改变 （比如转了90 或者 180 度）
: 那么这串指令一定会让机器人回到原点并且保持原来的前进方向。证明是这样的：
: 如果位移的距离用一个矢量 s 表示, 转动可以用一个 矩阵 g 来表示，那么当这串指
: 令执行很多次以后，机器人的位移是：
: (1 + g + g^2 + g^3 + ...) * s
: 如果是转动 90 度， 那么 (1 + g + g^2 + g^3) == 0，也就是说四次这串指令一定
: 让机器人回到原位，并且 4 次指令一定会让机器人的方向转回原位。如果是转动 180
: 度那么只需要 2 次。 除非 g = e （没有转动）并且 s != 0。这些属于 D4 群的性质
|
q****e
发帖数: 793 | 24 这是群论吧？代数的知识，放狗搜下group theory, d4
【在 b********r 的大作中提到】
: 大牛，您的解答一开始都看不懂。后来用自己还没有还给老师的坐标变化，画了图（分
: 90，180， 270）才明白你的意思。
: 请问这是这是物理，还是计算几何知识？还请问您的背景，是计算机，数学，物理？
:
: 180
|
