描述:
写一个图灵机模拟程序,该程序输入专用图灵机指令集及用户输入,模拟执行
图灵机程序,产生输出。
输入说明:
输入第一行为一个整数 n,表示专用图灵机指令集有 n 条指令。
接下来是 n+1 行
1)前 n 行为 n 条指令,每条指令由 5 个部分构成,每个部分用空格分隔,如下
所示:
当前状态 输入符号 输出符号 纸带移动方向 新状态
例如:ADD 0 1 L RETURN
其中,
“当前状态”和“新状态”为一个长度不超过 20 个字符的字符串
“输入符号”和“输出符号”各是一个字符,输入和输出符号有‘’,
‘0’,‘1’三种,其中‘’表示分界符,两个‘’之内的部分是有效
输入/输出。纸带其余部分填充‘#’表示空白
“纸带移动方向”也是一个字符,有三种可能:‘L’表示左移,‘R’表
示右移,‘N’表示不动
2)最后一行为一个长度不超过 100 的字符串,表示图灵机输入
该字符串由若干‘#’,两个‘’和若干‘0’,‘1’字符构成,‘#’表示纸
带上的空白,‘’表示输入分界符,‘0’和‘1’表示有效输入,如下所示:
#####101####
注意:有两种状态是固定字符串:“INIT”表示初始状态,“STOP”表示停机
状态,图灵机一开始处于初始状态(INIT),纸带的读写头位于输入字符串的
得个''位置(右分界符)。
输出说明:
根据输入数据执行图灵机程序,在一行上打印出执行后的输出,只输出有效部
分,不输出‘#’,‘*’。
输入样例:
12
INIT * * N START
START * * R ADD
ADD 0 1 L RETURN
ADD 1 0 R CARRY
ADD * * L STOP
CARRY 0 1 L RETURN
CARRY 1 0 R CARRY
CARRY * 1 R OVERFLOW
OVERFLOW # * L RETURN
RETURN 1 1 L RETURN
RETURN 0 0 L RETURN
RETURN * * N STOP
##########101##########
输出样例:
110
样例说明:
该样例为执行二进制加 1 操作 y=x+1 的专用图灵机程序,输入为 101,输出为
110
对于任意给定的一台Turing机和任意给定的字符串w ( w不含空格),编程模拟此Turing机的运行过程,要求输出从开始运行起的每一步骤的结果。
#include<iostream>
#include<string.h>
using namespace std;
int main()
{ int i,j,l;
int inter=0;
string a;
cin>>a;
l=a.length();
for(i=0;i<l;i++)
{ //图灵机的基本实现步骤
if(inter==0&&a[i]==48)
{
inter=0;
a[i]='0';
cout<<"(1) ";
for(int k=0;k<l;k++)
cout<<a[k]<<" ";
}
if(inter==0&&a[i]==49)
{
inter=1;
a[i]='1';
cout<<endl<<"(2) ";
for(int k=0;k<l;k++)
cout<<a[k]<<" ";
}
if(inter==1&&a[i]==48)
{
inter=0;
a[i]='1';
cout<<endl<<"(3) ";
for(int k=0;k<l;k++)
cout<<a[k]<<" ";
cout<<endl<<"最终结果:";
break;
}
if(inter==1&&a[i]==49)
{
inter=1;
a[i]='1';
cout<<endl<<"(4) ";
for(int k=0;k<l;k++)
cout<<a[k]<<" ";
}
}
for(int k=0;k<l;k++)
cout<<a[k]<<" ";
return 0;
}
不知道对你有没有用呢,如果有用,采纳一下吧