状态数只允许最多100啊Caravel 写了： 2025年 3月 3日 12:41 我知道这是类似图灵机啊
计数不是很容易实现吗，每次右移一位状态加一
状态数空间有限制么？
只要状态数够大，你可以encode任何数字，
这玩意跟高级语言编程没有本质区别，只是极其缓慢
呃。。。我重新仔细看了下题，我居然漏看了题目限制输入长度为1-10个符号。我以为是任意长度! 这就改变了游戏规则啊
在这个范围内，你说的方法确实理论上可行：
10个位置，状态完全够用来计数
前半部分最多5位，2^5=32种可能组合，100个状态也能应付
不过实现起来可能还是有点绕：
需要同时用状态编码"我在哪一位"和"已看到什么内容"
比较阶段还要从状态中解码出之前存的内容
状态转换表会相当复杂...
等等，关于输入内容，我注意到前一题说符号可以是0, 1或A-Z范围内的字母，这个题没有修改这个规定。
如果输入只限于0和1（从示例看似乎如此），那你的方法在10个符号的限制下理论上可行，是我漏看了这个长度限制。
但如果输入也可以包含字母，那计算就完全不同了：
即使只有4种可能的符号，5位前缀的组合数就是4^5=1024
这远超出100个状态的限制，你的方法就无法编码所有可能的前缀内容
不管怎样，即使只有0和1，实现起来仍然很绕：同时用状态编码位置和内容信息，然后在比较阶段还要从状态中提取这些信息...
这破玩意是不是让我们忆苦思甜的啊，草
