如何判断输入中1的数量是否是0数量的一半

问题描述 投票：0回答：3

我遇到了这个问题：

输入时给出了 9 位二进制代码，我们必须在输出中打印“0” 如果值为“1”的位数少于两倍 值为“0”的位，如果此条件为假，我们必须打印 输出为“1”。

我的想法是引入一个计数器，然后对值为1的位进行计数，然后根据该计数器进行输出。但有人告诉我，有一条路没有柜台，我选择了最难的路。有人知道确定输出内容的更好方法吗？

algorithm discrete-mathematics turing-machines
3个回答
3
投票

当TM读取输入位时，状态数必须捕获所看到的位数，从0到9，以便我们可以识别何时到达末尾，以及所看到的1位的数量，以及相关情况为 0、1、2、3 和 >=4。

编码所有相关可能性所需的状态少于 10*5=50 个。 当机器进入表示已看到 9 个输入位的状态之一时，如果表示已看到 3 个 1，则写入 0，否则写入 1，然后停止。

请注意，我们不需要使用磁带进行存储——输入语言是规则的，因此可以通过有限状态机来决定，并且不需要无限存储。

0
投票

虽然 Matt 是正确的，但您可以使用存储将此问题推广到任意输入大小。

  1. 转到磁带开头
  2. 向前寻找未标记的
    1
    。标记它。
    • 如果找不到未标记的 
      1
      ，请转到步骤 7。
  3. 回到磁带开头
  4. 寻找未标记的
    0
    。标记它。
    • 如果找不到未标记的 
      0
      ，请转到步骤 9。
  5. 寻找另一个未标记的
    0
    。标记它。
    • 如果找不到未标记的 
      0
      ，请转到步骤 9。
  6. 转到步骤1
  7. 转到输入内容的开头。
  8. 寻找未标记的
    0
    。
    • 如果没有找到，则输出
      0
      。停下来。
  9. 输出
    1
    。停下来。

这适用于任何输入大小。直观上，我们为输入中的每个 

0
寻找 2 个 
1
，确保 
0
位的数量是 
1
位的两倍。

0
投票

由于输入有9个符号，当正好有3个时，1的数量只能是O数量的一半。定义以下状态：

  • q0
    ：到目前为止我们发现了零个“1”
  • q1
    ：到目前为止我们找到了一个“1”
  • q2
    ：到目前为止我们发现了两个“1”
  • q3
    ：到目前为止我们发现了三个“1”

如果到达输入的末尾并且状态为

q3
，那么我们可以接受输入。在所有其他情况下，输入都会被拒绝（TM 在非接受状态下停止）。请注意，这不会验证输入是否包含 9 个符号。这是给出作为事实。

这是带有转换表的片段。使用您选择的输入运行它：

createTuring({
    transitions: [
        { state: "q0", read: "0", move: "R", nextState: "q0"  },
        { state: "q0", read: "1", move: "R", nextState: "q1"  },
        { state: "q1", read: "0", move: "R", nextState: "q1"  },
        { state: "q1", read: "1", move: "R", nextState: "q2"  },
        { state: "q2", read: "0", move: "R", nextState: "q2"  },
        { state: "q2", read: "1", move: "R", nextState: "q3"  },
        { state: "q3", read: "0", move: "R", nextState: "q3"  },
        { state: "q3", read: "_", move: "L", nextState: "accept" },
    ],
    initState: "q0",
    logState: "print",
    tape: "001010110",
});
<script src="https://trincot.github.io/turing.js"></script>

最新问题
© www.soinside.com 2019 - 2025. All rights reserved.