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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 机器人可以接受一串指令,指令只有三种: : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果一串指令结束后, : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把这个指令序列执行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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 所以说就是扫描一遍 检测是否有至少有一个G 和 R和L的数量是否相等?因为只有R和L : 数量相等才能抵消旋转,否则在若干次旋转后都会循环? : 其实当时也试了这个算法,结果有一些test case还是没过。因为看不见test case所以 : 也不知道怎么回事。 : : 180
|
|
|
l******s 发帖数: 3045 | 11 赞
180
【在 m*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果一串指令结束后, : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 机器人可以接受一串指令,指令只有三种: : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果一串指令结束后, : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把这个指令序列执行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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 所以说就是扫描一遍 检测是否有至少有一个G 和 R和L的数量是否相等?因为只有R和L : 数量相等才能抵消旋转,否则在若干次旋转后都会循环? : 其实当时也试了这个算法,结果有一些test case还是没过。因为看不见test case所以 : 也不知道怎么回事。 : : 180
|
l******s 发帖数: 3045 | 22 赞
180
【在 m*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果一串指令结束后, : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果一串指令结束后, : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大牛,您的解答一开始都看不懂。后来用自己还没有还给老师的坐标变化,画了图(分 : 90,180, 270)才明白你的意思。 : 请问这是这是物理,还是计算几何知识?还请问您的背景,是计算机,数学,物理? : : 180
|