问一道interview street题目判断机器人指令是否造成死循环 - 未名空间MITBBS历史存档

问一道interview street题目判断机器人指令是否造成死循环# JobHunting - 待字闺中

s*d2015-07-26 07:07

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*l2015-07-26 07:07

2 楼

这题怎么定义死循环啊
是原地不动还是走了一圈回到原点？

s*d2015-07-26 07:07

3 楼

死循环指活动范围在一个固定的range里面比如在一个1万歩的框里转圈也算

l*s2015-07-26 07:07

4 楼

At least a 2-d bool array or List can do it. Need more optimized ideas.

m*t2015-07-26 07:07

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*e2015-07-26 07:07

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*d2015-07-26 07:07

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*d2015-07-26 07:07

8 楼

这个好像有道理回到原点应该指的是执行第1，2，3，4遍完整程序时刚好回到原点？

【在 b***e 的大作中提到】

: 把这个指令序列执行4遍，如果回到原点，则循环，否则无循环。

r*y2015-07-26 07:07

9 楼

这道题其实解法不难。
假设walk()为执行一次所有的指令。那么：
do{
walk();
}while(direction != north)
return current_Coordiante == origin;
因为方向只会变化90度，这个循环最多执行4次就结束了。

m*t2015-07-26 07:07

10 楼

如果 R 和 L 数量不相等你也可以转回原来的方向，比如 L L L L 就行了。至少有
一个 G 也不能保证你有不为 0 的位移。
直接计算每个基本指令之后，走到哪里了，面朝哪里，这个不难。
上面很多人说的是，把指令串执行四次。但实际上你只需要执行一次就行了。4 次完全
没有必要。

和L

【在 s********d 的大作中提到】

: 所以说就是扫描一遍检测是否有至少有一个G 和 R和L的数量是否相等？因为只有R和L
: 数量相等才能抵消旋转，否则在若干次旋转后都会循环？
: 其实当时也试了这个算法，结果有一些test case还是没过。因为看不见test case所以
: 也不知道怎么回事。
:
: 180

l*s2015-07-26 07:07

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*d2015-07-26 07:07

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*l2015-07-26 07:07

13 楼

这题怎么定义死循环啊
是原地不动还是走了一圈回到原点？

s*d2015-07-26 07:07

14 楼

死循环指活动范围在一个固定的range里面比如在一个1万歩的框里转圈也算

l*s2015-07-26 07:07

15 楼

At least a 2-d bool array or List can do it. Need more optimized ideas.

m*t2015-07-26 07:07

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*e2015-07-26 07:07

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*d2015-07-26 07:07

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*d2015-07-26 07:07

19 楼

这个好像有道理回到原点应该指的是执行第1，2，3，4遍完整程序时刚好回到原点？

【在 b***e 的大作中提到】

: 把这个指令序列执行4遍，如果回到原点，则循环，否则无循环。

r*y2015-07-26 07:07

20 楼

这道题其实解法不难。
假设walk()为执行一次所有的指令。那么：
do{
walk();
}while(direction != north)
return current_Coordiante == origin;
因为方向只会变化90度，这个循环最多执行4次就结束了。

m*t2015-07-26 07:07

21 楼

如果 R 和 L 数量不相等你也可以转回原来的方向，比如 L L L L 就行了。至少有
一个 G 也不能保证你有不为 0 的位移。
直接计算每个基本指令之后，走到哪里了，面朝哪里，这个不难。
上面很多人说的是，把指令串执行四次。但实际上你只需要执行一次就行了。4 次完全
没有必要。

和L

【在 s********d 的大作中提到】

: 所以说就是扫描一遍检测是否有至少有一个G 和 R和L的数量是否相等？因为只有R和L
: 数量相等才能抵消旋转，否则在若干次旋转后都会循环？
: 其实当时也试了这个算法，结果有一些test case还是没过。因为看不见test case所以
: 也不知道怎么回事。
:
: 180

l*s2015-07-26 07:07

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*r2015-07-26 07:07

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*e2015-07-26 07:07

24 楼

这是群论吧？代数的知识，放狗搜下group theory, d4

【在 b********r 的大作中提到】

: 大牛，您的解答一开始都看不懂。后来用自己还没有还给老师的坐标变化，画了图（分
: 90，180， 270）才明白你的意思。
: 请问这是这是物理，还是计算几何知识？还请问您的背景，是计算机，数学，物理？
:
: 180