雄安移动网上营业厅/开鲁网站seo转接
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函数中，看起来不美观并且很容易出错，输出的结果是二进制扩展编码，没有