在反转后其无限重复不同的最短位串
马文·明斯基在我的口试中问了我以下问题：
当蚂蚁行走时，它每次迈出一步就打印一个二进制数(例如101)。最小长度(以数字为单位)是多少?二进制数可以用来判断蚂蚁的移动方向，而不必看字符串的开头或结尾？蚂蚁告诉你二进制数。
例如:蚂蚁的二进制数是101，因此，蚂蚁留下的轨迹如下:101101101101101101101101。注意，没有办法知道蚂蚁是往哪条路走的。因此，这个特定的数字不能工作(但可能有一个三位数的二进制数)。
例如:蚂蚁的二进制数是011，因此，蚂蚁留下了如下所示的轨迹: 011011011011011011。同样，如果不看绳子的末端，就无法判断蚂蚁往哪个方向移动。
这个问题的答案是什么？请注意，答案不能仅仅是一个工作的二进制数字的例子。答案需要包括一个证明，长度小于n-1的二进制数都不能工作，其中n是工作的示例二进制数的长度。通过详尽的列举证明是可以的，但令人不快。:)
回答 2
Stack Overflow用户
发布于 2009-07-22 14:56:59
另一种方法是脱离二进制数。将问题重新表述为“如果允许使用任意数量的唯一符号，那么最短的可能模式是什么？”
这里的答案是3(例如A;B;C或#;&;@)，因为2不起作用。所以，当你有了像ABC这样的模式时，蚂蚁的行走方向就变得清晰了。
要么...CABCABCABCABCAB..。(从左到右)或...CBACBACBACBACBA.(从右到左)
现在，我们需要多少个二进制数字才能在三元(基-3)中写出一个由3个符号组成的图案？
两个二进制数字允许您编写单个第四纪(基-4)数字，这是高于或等于3的第一个基数。
因此：(每个符号2位)乘以(3个符号)=6位二进制数字.
Stack Overflow用户
发布于 2009-07-21 18:58:29
ChssPly76在上面的评论中有正确的答案。
6位数，示例100110。
https://stackoverflow.com/questions/1145148
复制相似问题
腾讯云开发者
