图灵机模拟XN*2
1、 题目分析
对于任意给定的一台Turing机和任意给定的字符串w(w不含空格),编程模拟此Turing机的运行过程,要求输出从开始起的每一步骤的结果。
要求:掌握图灵机的概念和基本结构,理解图灵机的基本指令和编码方式;掌握图灵机的编程方法。
2、 算法构造
模拟图灵机XN*2,其指令如下:
0 0 -> 0 0 R,
0 1 -> 1 0 R,
1 0 -> 0 1 R,
1 1 -> 10 0 R,
10 0 -> 11 1 R,
11 0 -> 0 1 STOP。
首先输入一个十进制正整数,通过编码将十进制正整数转换成二进制数;
接着将二进制数转换成二进制扩展编码,并在末尾加上110,表示逗号;
将扩展后的二进制编码存放在数组a中,从a[0]~a[n]依次遍历,按如上所示指令转换,将每一步结果输出。
3、 算法实现
#include<iostream>
using namespace std;
int main()
{
int n,i,j;
int temp,k,len;
int m=0;
int a[20],arr[20];
int flag=0;
cout<<"请输入一个正整数";
cin>>n;
while(n>0)
{
arr[i]=n%2; //获取余数
n=n/2;
i++;
}
k=i;
for(j=0;j<i/2;j++)
{
temp=arr[j];
arr[j]=arr[i-j-1];
arr[i-j-1]=temp;
}
cout<<"正整数转换为二进制的结果为:";
for(i=0;i<k;i++)
{
cout<<arr[i];
}
cout<<"扩展的二进位编码为:"<<endl;//扩展的二进位编码
for(j=0;j<k;j++)
{
if(arr[j]==1)
{
if(j==0)
{ a[m]=0;
m++;
a[m]=arr[j];
m++;
a[m]=0;
}
else
{
a[m]=arr[j];
m++;
a[m]=0;
}
m++;
}
else if(arr[j]==0)
{
a[m]=arr[j];
m++;
}
}
int array[6]={1,1,0,0,0,0};//{1,1,0}表示逗号,为了计算方便需要在后面多加一些0
for(int x=0;x<6;x++)
{
a[m++]=array[x];
}
len=m+1;
for (m=0; m<len; m++)
{
if (a[m] == 0 || a[m] == 1)
{
cout<< a[m]; //输出a[]
}
}
cout<<endl;
for(i=0;i<m;i++)
{
if(flag==0&&a[i]==0) // 内态为0输入为0时,內态变为0输入变为0
{
flag=0;
a[i]=0;
}
else if(flag==0&&a[i]==1) //内态为0输入为1时,内态变为1输入变为0
{
flag=1;
a[i]=0;
}
else if(flag==1&&a[i]==0) //内态为1输入为0时,内态变为0输入变为1
{
flag=0;
a[i]=1;
}
else if(flag==1&&a[i]==1) //内态为1输入为1时,内态变为10输入变为0
{
flag=10;
a[i]=0;
}
else if(flag==10&&a[i]==0) //内态为10输入为0时,内态变为11输入变为1
{
flag=11;
a[i]=1;
}
else if(flag==10&&a[i]==1) //内态为10输入为1时,内态变为0输入变为0
{
flag=0;
a[i]=0;
}
else if(flag==11&&a[i]==0) //内态为11输入为0时,内态变为0输入变为1
{
flag=0;
a[i]=1;
}
else if(flag==11&&a[i]==1) //内态为11输入为1时,内态变为0输入变为0
{
flag=0;
a[i]=0;
}
cout<<"运行结果:";
for(j=0;j<m;j++)
{
cout<<a[j];
}
cout<<endl;
}
return 0;
}
4、 调试、测试几运行结果
程序运行截图
程序测试截图:
测试数据第一个输入一个负数,观察结果可以发现结果出错,再输入一个符合要求的正整数,结果正确。
程序调试截图:
5、归纳总结
本次上机任务是模拟图灵机指令对正整数乘以2的操作,熟悉了图灵机的基本指令和简单的编码方式,在本次程序编写中,我遇到的困难是如何把一个正整数转换成二进制的扩展编码,经过考虑,运用了数组来实现这一转换。这次的程序全部写在main函数中,看起来不美观并且很容易出错,输出的结果是二进制扩展编码,没有