首页 文章

除以N二进制时钟序列算法？

提问于
浏览 次
2

我不太清楚如何描述我的意思，所以让我试着通过例子解释（忍受我） .

当你只是递增一个整数时，你得到一个像这样的二进制序列（假设这个问题为8位）：

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 1
0 0 0 0 0 1 1 0 
0 0 0 0 0 1 1 1
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 1
0 0 0 0 1 0 1 0
0 0 0 0 1 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 1
0 0 0 0 1 1 1 0 
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 1 0 0 1 0
0 0 0 1 0 0 1 1
0 0 0 1 0 1 0 0
0 0 0 1 0 1 0 1
0 0 0 1 0 1 1 0 
0 0 0 1 0 1 1 1
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 1
0 0 0 1 1 0 1 0
0 0 0 1 1 0 1 1
0 0 0 1 1 1 0 0
0 0 0 1 1 1 0 1
0 0 0 1 1 1 1 0 
0 0 0 1 1 1 1 1
[ ... etc ... ]

可视化的一种方法是每列代表一个“时钟” . 每个时钟/列的频率是其右邻居的一半 .

所以最右边的时钟有一个 0 后跟一个 1 等 . 下一个时钟有两个 0 s后跟两个 1 等等等......

我对一系列二进制字符串很感兴趣，其中每个时钟都是其邻居的整数除法 .

所以最右边的时钟仍然是一个 0 ，一个 1 ，下一个时钟仍然是两个 0 s，两个 1 s，但第三个时钟是三个 0 s和三个 1 等等 .

而不是 /1 /2 /4 /8 /16 ... 现在 /1 /2 /3 /4 /5 ... .

序列现在看起来像这样：

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 1 1 1
0 0 0 0 1 1 0 0
0 0 0 1 1 1 0 1
0 0 1 1 1 0 1 0
0 1 1 1 1 0 1 1
1 1 1 1 0 0 0 0
1 1 1 1 0 1 0 1
1 1 1 0 0 1 1 0
1 1 1 0 0 1 1 1
1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 1
1 0 0 0 1 0 1 0
1 0 0 1 1 1 1 1
0 0 0 1 0 1 0 0
0 0 0 1 0 1 0 1
0 0 1 1 0 0 1 0
0 0 1 1 0 0 1 1
[ ... etc ... ]

Question ：是否有一个操作/算法可以在 i-1 给出 i 的值？

换句话说，让's say I' m在第4步（ 0 0 0 0 0 1 1 1 ） . 我可以对此数字执行某些操作以获取第5步（ 0 0 0 0 1 1 0 0 ）的值，并且类似地执行任何其他步骤吗？

在除以2的情况下，你只需增加数字（ i++ ），但在除以N的情况下，我似乎无法找出从一个到另一个的类似方式 . 我错过了一些明显的东西吗

我已经尝试将排序转换为十进制，但该模式是 0, 1, 2, 7, 12, 29, 58, etc ，这对我来说并不突出 .

我现在正在做的蛮力方式是我有一个计数器阵列（每个列/时钟一个），当达到相应列的“周期”时，我独立地重置每个计数（因此第一列为2） ，3为下一个，等） . 但这感觉很难看 .

我喜欢直接在号码上这样做而不需要一系列计数器 . 这甚至可能吗？这是一个已知的序列吗？我甚至不确定谷歌要说实话 . 我很欣赏这方面的任何线索 . 我很乐意在一些指导下走下兔洞 .

UPDATE

根据@ borrible的观察，对于给定的 i ， i-1 有多个值，所以事实证明我原来问题的解决方案是模棱两可的 . 所以我将扩展我的问题以允许 i 作为输入（除了 i-1 th值 .

c algorithm binary computer-science clock

2 回答

  • 1

    在不知道 i 的情况下，如果该序列唯一地暗示 i （以比特序列的数量为模），则您将能够生成给定序列的后继 . 如果不是这种情况，则给定序列的后继者是不明确的 .

    让我们考虑3位的前几个序列：

    0 0 0
0 0 1
0 1 0
1 1 1
1 0 0
1 0 1
0 1 0
0 1 1

    请注意 0 1 0 由 1 1 1 和 0 1 1 继承;即它含糊不清 . 鉴于 0 1 0 但不是 i ，您无法推断出下一个序列 . 对于 0 1 1 1 等，您可以在4位序列中看到类似的歧义...

    换句话说，在不知道 i 的情况下，您的问题通常无法解决 .

    回复于
  • 4

    此序列可以视为一组状态机，每个状态机具有 2,4,6,...,16 状态 . 2,4,6,...,16 的最小公倍数，即序列的长度，是1680.八位只允许我们表示256个值，所以即使我们被允许选择状态编码（我们也不能唯一地识别所有可能的状态 .

    如果我们知道索引 i （或者，因为序列长度是1680，知道索引模1680就足够了）， (i mod (2 * j)) / j 给出了数字 j .

    回复于

相关问题