T*******r
发帖数: 30 | 1 这道题好像是道微软的面试题
一列士兵横排站开，军官第一秒喊口令"about face"，然后士兵有的会左转有的会右
转，这样转完后一些士兵会面对面，然后下一秒这些面对面的士兵会向后转。再下一秒
仍是如此。问最后会不会结束。证明。如果能结束的话所花时间的上界。
不难给结束的时间一个O(n^2)的上界，但我觉得sharp bound应该是(n-1)。请问各位高
手有没有办法证明。
拜谢！ |
S*********g
发帖数: 5298 | 2 每向后转一次，面对面的对数减少一对
【在 T*******r 的大作中提到】
: 这道题好像是道微软的面试题
: 一列士兵横排站开，军官第一秒喊口令"about face"，然后士兵有的会左转有的会右
: 转，这样转完后一些士兵会面对面，然后下一秒这些面对面的士兵会向后转。再下一秒
: 仍是如此。问最后会不会结束。证明。如果能结束的话所花时间的上界。
: 不难给结束的时间一个O(n^2)的上界，但我觉得sharp bound应该是(n-1)。请问各位高
: 手有没有办法证明。
: 拜谢！
|
d********t
发帖数: 9628 | 3
n/(n+1), same as the ants going through the bridge problem
【在 T*******r 的大作中提到】
: 这道题好像是道微软的面试题
: 一列士兵横排站开，军官第一秒喊口令"about face"，然后士兵有的会左转有的会右
: 转，这样转完后一些士兵会面对面，然后下一秒这些面对面的士兵会向后转。再下一秒
: 仍是如此。问最后会不会结束。证明。如果能结束的话所花时间的上界。
: 不难给结束的时间一个O(n^2)的上界，但我觉得sharp bound应该是(n-1)。请问各位高
: 手有没有办法证明。
: 拜谢！
|
T*******r
发帖数: 30 | 4 如果用1表示面右，-1表示面左
那么 1 1 -1 -1 的情形不符合大侠所说
或者大侠所说的面对面的情形是指 所有的 1和-1组成的对，这样的话每一次转身都会
至少减少一个这样的对，但这样给出的时间是O(n^2)
ring (小芝麻和小包包他爹) 的大作中提到: 】 |
C*O
发帖数: 389 | 5 有些不清楚
什么是结束条件.
先开始大家站在一排，面朝前
转了以后，有的朝左，有的朝右.
面对面的朝后转， 是不是 A朝右，B朝左， 转完了 就是 A朝左，B向右了.
其他的会继续朝左，朝右转， 成为 朝上，朝下呢？
【在 T*******r 的大作中提到】
: 这道题好像是道微软的面试题
: 一列士兵横排站开，军官第一秒喊口令"about face"，然后士兵有的会左转有的会右
: 转，这样转完后一些士兵会面对面，然后下一秒这些面对面的士兵会向后转。再下一秒
: 仍是如此。问最后会不会结束。证明。如果能结束的话所花时间的上界。
: 不难给结束的时间一个O(n^2)的上界，但我觉得sharp bound应该是(n-1)。请问各位高
: 手有没有办法证明。
: 拜谢！
|
E*****T
发帖数: 1193 | 6 归纳一下就得到了吧。若干1，若干-1，目的是把相邻的左1右-1交换直到-1全在左边，
1全在右边。
n=2成立，1次就成了
假设n个正负1时需n-1次
那么n+1个正负1时
情况（1）最左边是-1：这个-1就不会动了，剩下的n个数n-1次搞定
情况（2）最左边是1，-1，一次交换后变成情况（1），总共n次必然搞定
情况（3）最左边是1，1，每一次交换后，这两个1之间都不可能插入两个-1，也就是最
左边的1最多多换一次就能和左二的1相邻，左二的1最多n-1步后换过所有的-1，最左的
1最多n步就行了。 |
d*****o
发帖数: 34 | 7
我的想法：
（n-1）应该不是O(n^2)吧。
如果有两个士兵的话，如果不算“about face”时的转向，那么最多需要转1次；
假设about face之后的情况是面对面，标记为：01，转向停止时的状态为10
（转向会在10，11，00时停止）
如果有三个士兵的话，如果不算“about face”时的转向，那么最多需要转2次；
about face之后的情况是：01+1，转向停止时的状态为110
如果有四个士兵的话，最多需要转3次，about face之后的情况是：011+1，转向停止时
的状态为
1110
如果有n个士兵，最多需要转n-1次，about face之后的情况是：011...1，转向停止时
的状态为11...10
当有n+1个士兵，最多的转动次数的情况应该是011...1+1，转向停止时的状态为11...1
+10
【在 T*******r 的大作中提到】
: 这道题好像是道微软的面试题
: 一列士兵横排站开，军官第一秒喊口令"about face"，然后士兵有的会左转有的会右
: 转，这样转完后一些士兵会面对面，然后下一秒这些面对面的士兵会向后转。再下一秒
: 仍是如此。问最后会不会结束。证明。如果能结束的话所花时间的上界。
: 不难给结束的时间一个O(n^2)的上界，但我觉得sharp bound应该是(n-1)。请问各位高
: 手有没有办法证明。
: 拜谢！
|
T*******r
发帖数: 30 | 8 这个应该能成，赞
【在 E*****T 的大作中提到】
: 归纳一下就得到了吧。若干1，若干-1，目的是把相邻的左1右-1交换直到-1全在左边，
: 1全在右边。
: n=2成立，1次就成了
: 假设n个正负1时需n-1次
: 那么n+1个正负1时
: 情况（1）最左边是-1：这个-1就不会动了，剩下的n个数n-1次搞定
: 情况（2）最左边是1，-1，一次交换后变成情况（1），总共n次必然搞定
: 情况（3）最左边是1，1，每一次交换后，这两个1之间都不可能插入两个-1，也就是最
: 左边的1最多多换一次就能和左二的1相邻，左二的1最多n-1步后换过所有的-1，最左的
: 1最多n步就行了。
|
T*******r
发帖数: 30 | 9 第一次转90°，以后都转180°
【在 C*O 的大作中提到】
: 有些不清楚
: 什么是结束条件.
: 先开始大家站在一排，面朝前
: 转了以后，有的朝左，有的朝右.
: 面对面的朝后转， 是不是 A朝右，B朝左， 转完了 就是 A朝左，B向右了.
: 其他的会继续朝左，朝右转， 成为 朝上，朝下呢？
|
T*******r
发帖数: 30 | 10 我一直在试图找invariants，不知道这条路走不走的通
【在 E*****T 的大作中提到】
: 归纳一下就得到了吧。若干1，若干-1，目的是把相邻的左1右-1交换直到-1全在左边，
: 1全在右边。
: n=2成立，1次就成了
: 假设n个正负1时需n-1次
: 那么n+1个正负1时
: 情况（1）最左边是-1：这个-1就不会动了，剩下的n个数n-1次搞定
: 情况（2）最左边是1，-1，一次交换后变成情况（1），总共n次必然搞定
: 情况（3）最左边是1，1，每一次交换后，这两个1之间都不可能插入两个-1，也就是最
: 左边的1最多多换一次就能和左二的1相邻，左二的1最多n-1步后换过所有的-1，最左的
: 1最多n步就行了。
|
|
|
E*****T
发帖数: 1193 | 11 其实只有一个半不变量，其实也是估计的关键，就是两个人间的距离。
譬如说，你有k个1，分别在a_1
的距离初始为a_{i+1}-a_i，且在整个移动过程不会超过a_{i+1}-a_i+1.
第k个1到达n需要n-a_k步，这时第k-1个1距离n最多为a_k-a_{k-1}+1,所以之后
第k-1个1到达n-1需要之多a_k-a_{k-1}步，同理之后
第k-2个1到达n-2需要之多a_{k_1}-a_{k-2}步,......
求个和就会发现总共最多n-a_1<=n-1步，等号只有在1全在左，-1全在右取得。
不变量很难有，因为毕竟是个不等式。 |
E*****T
发帖数: 1193 | 12 如果你能找到好的计数方法，合理定义让hit到右边界的1继续移动，这个不变量应该是
存在的，不过这个定义也不好找。 |
s***e
发帖数: 267 | 13 Interesting problem.
Start with the partial sum sequence of those 1 and -1 numbers. If you plot
the partial sum sequence as a function of position, then for the FINAL STATE
, it goes all the way down and then all the way up to the end point which is
(n, #_of_1 - #_of_-1).
For any intermediate state, the start/end point will be the same, and the
function will have at least one local maximum. Every exchange will at least suppress
the each local maximum by 1, and the last step will reduce it by 2. From there
you can see that you need at most (n-1) steps...
【在 E*****T 的大作中提到】
: 如果你能找到好的计数方法，合理定义让hit到右边界的1继续移动，这个不变量应该是
: 存在的，不过这个定义也不好找。
|
E*****T
发帖数: 1193 | 14 如果你只用local maximum的值，那么初始不超过#of 1，经过#of-1步达到#of 1- #of
-1,但这并不是结束条件，结束条件还有local maximum只有一个。 |
s***e
发帖数: 267 | 15 The initial local max can not be greater than #_of_1, and before the final
move, the local max value is
- #_of_-1 + 2
So the max # of steps is #_of_1 - (- #_of_-1 + 2) + 1 = n - 1
of
【在 E*****T 的大作中提到】
: 如果你只用local maximum的值，那么初始不超过#of 1，经过#of-1步达到#of 1- #of
: -1,但这并不是结束条件，结束条件还有local maximum只有一个。
|
r**d
发帖数: 316 | 16 这个问题似乎等价于仅有0和1两个值的数组的冒泡排序。所以O（n^2)应该是不能再小
了吧？
【在 T*******r 的大作中提到】
: 这道题好像是道微软的面试题
: 一列士兵横排站开，军官第一秒喊口令"about face"，然后士兵有的会左转有的会右
: 转，这样转完后一些士兵会面对面，然后下一秒这些面对面的士兵会向后转。再下一秒
: 仍是如此。问最后会不会结束。证明。如果能结束的话所花时间的上界。
: 不难给结束的时间一个O(n^2)的上界，但我觉得sharp bound应该是(n-1)。请问各位高
: 手有没有办法证明。
: 拜谢！
|
E*****T
发帖数: 1193 | 17 这就对啦，要严谨，哈哈。
【在 s***e 的大作中提到】
: The initial local max can not be greater than #_of_1, and before the final
: move, the local max value is
: - #_of_-1 + 2
: So the max # of steps is #_of_1 - (- #_of_-1 + 2) + 1 = n - 1
:
: of
|
k*****y
发帖数: 744 | 18 同一时刻，能同时换所有的01对，不是一对一对来。
【在 r**d 的大作中提到】
: 这个问题似乎等价于仅有0和1两个值的数组的冒泡排序。所以O（n^2)应该是不能再小
: 了吧？
|
M*******r
发帖数: 165 | 19 正解
【在 d********t 的大作中提到】
:
: n/(n+1), same as the ants going through the bridge problem
|
T**B
发帖数: 1 | 20 f(K)定义为第k秒从左向右第一个面向右且对面有相向的人的位置，则f(K)严格递增，
因为向左的人不会再转，K秒之后f（k)向左。 |
a*******8
发帖数: 2299 | |
