通用图灵机实现疑问：向量规则跳转与循环限制下的逻辑优化

我们需要实现一台通用图灵机，输入文件包含纸带数量、初始输入、初始位置以及规则。目前读取文件的逻辑没问题，已经把所有规则存入vector<rule>结构体数组，但卡在图灵机的核心运行逻辑上：初始状态固定为0，从该状态开始匹配规则，但不知道状态切换后如何正确找到对应规则，也不清楚怎么在vector上设计合适的规则查找机制，对vector的使用比较陌生，需要把它应用到算法里。

限制条件：算法最多只能使用两个循环，打印文本或读取文件的循环不计入在内。

当前代码如下：

#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <Windows.h>

struct rule {
    std::string qstate;                                                         // 当前状态
    char csymbol;                                                               // 当前符号
    char nsymbol;                                                               // 新符号
    char direction;                                                             // 磁头移动方向
    std::string nstate;                                                         // 新状态
};

void printingText(std::vector<char> input, int position, long long steps);
void searchingForASymbolOrState(std::vector<rule> rules, std::vector<char> input, std::string state, int position, int& cursorPos);

int main()
{
    int tapeCount, position;
    long long steps = 0;
    std::string tape;

    std::ifstream file("1.txt");
    file >> tapeCount >> tape >> position;

    std::vector <char> input(tape.begin(), tape.end());
    std::vector <rule> rules;

    rule temp;

    while (file >> temp.qstate) {
        file >> temp.csymbol;
        file >> temp.nsymbol;
        file >> temp.direction;
        file >> temp.nstate;
        rules.push_back(temp);
    }

    file.close();

    position--;                                                                             // 由于数组从0开始计数，因此将初始位置减1（原初始位置从1开始）
    int cursorPos = 0;                                                                      // 保存对应状态规则的起始位置
    std::string state = "0";                                                                // 保存当前状态，以便知晓当前所处状态

    // 图灵机核心算法
    
    while (true) {
        printingText(input, position, steps);
        if (state == rules[cursorPos].qstate) {
            if (input[position] == rules[cursorPos].csymbol) {
                if (input[position] != rules[cursorPos].nsymbol) {
                    input[position] = rules[cursorPos].nsymbol;
                    if (rules[cursorPos].direction == 'L') {
                        position--;
                        steps++;
                    }
                    else if (rules[cursorPos].direction == 'R') {
                        position++;
                        steps++;
                    }
                    if (rules[cursorPos].nstate != state) {
                        state = rules[cursorPos].nstate;
                    }
                }
                else if (input[position] == rules[cursorPos].nsymbol) {
                    if (rules[cursorPos].direction == 'L') {
                        position--;
                        steps++;
                    }
                    else if (rules[cursorPos].direction == 'R') {
                        position++;
                        steps++;
                    }
                    if (rules[cursorPos].nstate != state) {
                        state = rules[cursorPos].nstate;
                    }
                }
            }
            else if (input[position] != rules[cursorPos].csymbol) {
                searchingForASymbolOrState(rules, input, state, position, cursorPos);
            }
        }
        else if (state != rules[cursorPos].qstate) {
            searchingForASymbolOrState(rules, input, state, position, cursorPos);
        }                                                                                                       // 计数步数
        // std::cout << cursorPos << " " << position << " " << state << " " << rules[cursorPos].qstate;                 // 用于调试的语句
        Sleep(100);
        system("cls");
    }
    
    // 算法结束
}

void printingText(std::vector<char> input, int position, long long steps) {

    std::cout << "磁头位置用''符号标记\n\n";

    for (int i = 0; i < input.size(); i++) {
        if (i == position) {
            std::cout << "'" << input[i] << "'";
        }
        else {
            std::cout << input[i];
        }
    }

    std::cout << "\n\n步数: " << steps;
}

void searchingForASymbolOrState(std::vector<rule> rules, std::vector<char> input, std::string state, int position, int& cursorPos) {
    for (int i = 0; i < rules.size(); i++) {
        if (rules[i].qstate == state) {
            if (rules[i].csymbol == input[position]) {
                cursorPos = i;
            }
        }
        if (rules[cursorPos].qstate != state) {
            if (rules[i].qstate == state) {
                cursorPos = i;
            }
        }
    }
}

我知道.eof()或system("cls")并非最佳实现，但认为在本项目中可以正常使用，如有错误请指正。

编辑：已经尝试了一些实现，但不确定是否有更高效的方式。代码尚未完成，缺少停机逻辑和错误检查等，欢迎提供意见和建议。

问题分析与优化方案 #

1. 核心逻辑重构思路 #

当前代码的规则查找逻辑冗余且易出错，完全可以简化成主循环+单次规则遍历循环的结构，满足最多两个循环的限制：

• 去掉cursorPos的冗余维护，直接根据当前状态和纸带符号遍历规则找匹配项
• 补充停机逻辑：无匹配规则时终止运行
• 完善纸带边界处理：磁头越界时自动补充空白符（通常用_表示）

2. 优化后的核心算法代码 #

替换原主函数中的核心算法部分：

// 图灵机核心算法
while (true) {
    printingText(input, position, steps);
    const rule* matchedRule = nullptr;

    // 遍历规则找匹配项（第二个循环，满足限制）
    for (const auto& r : rules) {
        if (r.qstate == state && r.csymbol == input[position]) {
            matchedRule = &r;
            break;
        }
    }

    // 无匹配规则则停机
    if (!matchedRule) {
        std::cout << "\n\n停机：无匹配规则";
        break;
    }

    // 执行规则操作
    input[position] = matchedRule->nsymbol;
    if (matchedRule->direction == 'L') {
        if (position > 0) {
            position--;
        } else {
            // 左侧越界，补充空白符
            input.insert(input.begin(), '_');
        }
    } else if (matchedRule->direction == 'R') {
        position++;
        if (position >= input.size()) {
            // 右侧越界，补充空白符
            input.push_back('_');
        }
    }
    state = matchedRule->nstate;
    steps++;

    Sleep(100);
    system("cls");
}
// 算法结束

3. 其他优化点 #

• 删除冗余的searchingForASymbolOrState函数，简化代码结构
• 优化printingText函数参数：将std::vector<char>改为const std::vector<char>&，避免不必要的拷贝开销
• 如果规则中的状态都是数字字符串，可以把state改为整数类型，提升匹配效率
• 可以添加错误检查：比如读取文件时验证规则格式、初始位置是否合法等

内容的提问来源于stack exchange，提问作者righN