奶牛在长栅栏中寻找空隙的算法
Algorithm for cow to find the gap in a long fence
我正在看这个挑战：
A shortsighted cow, named Sam, cannot find enough grass on its current pasture. It remembers that the pasture’s enclosing fence has a gap. Unfortunately, the fence is very long: for a full circle, it takes Sam steps to walk along the fence. Sam can only see the gap if it is right next to it(remember the cow is shortsighted).
In this question, you will design different algorithms that will enable Sam to find the gap that is steps away from its current position. Sam is always located next to the fence. We call its start position origin. You may assume that is much greater than . Design an algorithm that requires O() time efficiency to find a gap and show that its efficiency is indeed O(). You do not need to write the algorithm in pseudocode (you can if you want), but you have to describe the algorithm clearly. is unknown. Sam can only walk along the fence.
我想不出任何方法来解决这个问题，因为是未知的而且似乎时间复杂度总是与而不是有关。
顺时针走1步
逆时针走2步
顺时针走4步...
每次你改变方向，你都会覆盖你已经看到的相同区域，再加上整个区域，所以平均 一半 时间花在检查新部分上栅栏的两侧交替。
您将在大约 4k 步后到达间隙。
为了找到不涉及N的解，假设N无限大，即栅栏不是圆形，它是一条直线，向两个方向无限延伸。
现在我们解决了这个问题，很明显 任何 成功的算法都必须检查两个方向。所以这意味着在朝一个方向走了一段时间，但没有成功之后，必须决定回到起点，然后再朝另一个方向走。一直朝一个方向一直走下去，从来都不是一个好的选择，因为很可能差距在另一个方向，因此搜索将不会成功。
所以剩下的就是决定什么时候回到起点，再往另一个方向看。
一个不错的选择是 double 每次你将在两个方向中的任何一个方向上离开原点的最大距离。如果您在任一侧都找不到间隙，则将最大距离加倍并重复该过程。也可以是另一个大于1的因子（比如3）...原理是一样的
让我们将两个可能的方向命名为“左”和“右”。所以牛会移动如下：
- 将距离设置为 1。
- 先向左移动那个距离
- 然后向右移动两倍的距离，所以你最终会到达原点右侧的镜像位置。
- 然后将该距离向左移动，这样您就可以到达原点。
- 如果在此过程中的任何时候我们发现差距，我们将停止算法
- 否则，将距离加倍，然后重复。
迭代后总行进距离为：
iteration
travelled in last iteration
travelled in total
1
4
4
2
8
12
3
16
28
4
32
60
..
..
..
2+1
Σi=1..2+1 = 2+2 − 4
这个循环的每次迭代我们都会移动当前设置距离的 4 倍。
如果间隙距离原点较远，那么我们需要 1+ceil(log2) 次迭代，最后一次迭代不会完全完成，因为它会发现差距时被打断。
所以行进的距离将小于 2+2 − 4 with = 1 + ceil(log2):
2ceil(log2)+3 − 4
...小于或等于：
8( + 1) − 4
因此行进距离在
中是线性的
我正在看这个挑战：
A shortsighted cow, named Sam, cannot find enough grass on its current pasture. It remembers that the pasture’s enclosing fence has a gap. Unfortunately, the fence is very long: for a full circle, it takes Sam steps to walk along the fence. Sam can only see the gap if it is right next to it(remember the cow is shortsighted).
In this question, you will design different algorithms that will enable Sam to find the gap that is steps away from its current position. Sam is always located next to the fence. We call its start position origin. You may assume that is much greater than . Design an algorithm that requires O() time efficiency to find a gap and show that its efficiency is indeed O(). You do not need to write the algorithm in pseudocode (you can if you want), but you have to describe the algorithm clearly. is unknown. Sam can only walk along the fence.
我想不出任何方法来解决这个问题，因为是未知的而且似乎时间复杂度总是与而不是有关。
顺时针走1步
逆时针走2步
顺时针走4步...
每次你改变方向，你都会覆盖你已经看到的相同区域，再加上整个区域，所以平均 一半 时间花在检查新部分上栅栏的两侧交替。
您将在大约 4k 步后到达间隙。
为了找到不涉及N的解，假设N无限大，即栅栏不是圆形，它是一条直线，向两个方向无限延伸。
现在我们解决了这个问题，很明显 任何 成功的算法都必须检查两个方向。所以这意味着在朝一个方向走了一段时间，但没有成功之后，必须决定回到起点，然后再朝另一个方向走。一直朝一个方向一直走下去，从来都不是一个好的选择，因为很可能差距在另一个方向，因此搜索将不会成功。
所以剩下的就是决定什么时候回到起点，再往另一个方向看。
一个不错的选择是 double 每次你将在两个方向中的任何一个方向上离开原点的最大距离。如果您在任一侧都找不到间隙，则将最大距离加倍并重复该过程。也可以是另一个大于1的因子（比如3）...原理是一样的
让我们将两个可能的方向命名为“左”和“右”。所以牛会移动如下：
- 将距离设置为 1。
- 先向左移动那个距离
- 然后向右移动两倍的距离，所以你最终会到达原点右侧的镜像位置。
- 然后将该距离向左移动，这样您就可以到达原点。
- 如果在此过程中的任何时候我们发现差距，我们将停止算法
- 否则，将距离加倍，然后重复。
迭代后总行进距离为：
| iteration | travelled in last iteration | travelled in total |
|---|---|---|
| 1 | 4 | 4 |
| 2 | 8 | 12 |
| 3 | 16 | 28 |
| 4 | 32 | 60 |
| .. | .. | .. |
| 2+1 | Σi=1..2+1 = 2+2 − 4 |
这个循环的每次迭代我们都会移动当前设置距离的 4 倍。
如果间隙距离原点较远，那么我们需要 1+ceil(log2) 次迭代，最后一次迭代不会完全完成，因为它会发现差距时被打断。
所以行进的距离将小于 2+2 − 4 with = 1 + ceil(log2):
2ceil(log2)+3 − 4
...小于或等于：
8( + 1) − 4
因此行进距离在
中是线性的