一,题目分析:
模拟图灵机的运算过程,运用图灵机的基本指令和编码方式实现XN*2。
二,算法构造:
图灵机在扩展二进制位实现(XN*2)的运算指令:
00→00R,
01→10R,
10→01R,
11→100R,
100→111R,
110→01STOP。
算法思路:
1,输入一个十进制,将十进制转化成二进制;
2,将二进制转化成图灵机扩展的二进制编码;
3,通过图灵机XN*2运算指令输出每一步的运算结果。
三,算法实现:
源程序:
#include<stdio.h>
void main()
{
int i=0,j=0,x=0,c=0;
int a[30],s[30],b[30];
int len,temp,k;
printf("请输入一个十进制数:",x);//输入一个十进制数
scanf("%d",&x);
while(x>0)//将十进制数转化成二进制的倒序
{
temp=x%2;
s[i++]=temp;//将十进制除2的余数放进数组s[]
x/=2;
}
k=i;
printf("转化为二进制为:\n");
for(j=0;j<k;j++)
{
if(i>0)
{
a[j]=s[--i];//将倒序的二进制倒着赋值给数组a[]
printf("%d",a[j]);//输出二进制的正序
}
}
printf("\n");
printf("转化成扩展的二进位编码为:\n");//转化成扩展的二进位编码
for(j=0;j<k;j++)
{
if(a[j]==1)
{
if(j==0)
{ b[c]=0;
c++;
b[c]=a[j];
c++;
b[c]=0;
}
else
{
b[c]=a[j];
c++;
b[c]=0;
}
c++;
}
else if(a[j]==0)
{
b[c]=a[j];
c++;
}
}
int u[4]={1,1,0,0};//在扩展二进制编码后加上{1,1,0,0},{1,1,0}表示逗号,多余的0为了计算需要
for(int d=0;d<4;d++)
{
b[c++]=u[d];
}
len=c+1;
for (c=0; c<len; c++)
{
if (b[c] == 0 || b[c] == 1)
{
printf("%d", b[c]); //输出图灵扩展二进制编码c[]
}
}
printf("\n");
printf("图灵计算过程为:\n");
c=c-1;
int n=0;
for(i=0;i<c;i++)//模拟图灵机的运算过程,并输出每一步运行结果
{
if(n==0)
{
if(b[i]==0)
{n=0;b[i]=0;}
else
{n=1;b[i]=0;}
}
else if(n==1)
{
if(b[i]==0)
{n=0;b[i]=1;}
else
{n=10;b[i]=0;}
}
else if(n==10&&b[i]==0)
{
n=11;b[i]=1;
}
else if(n==11&&b[i]==0)
{
n=0;b[i]=1;
}
for(j=0;j<c;j++)
{
printf("%d",b[j]);
}
printf("\n");
}
}
四,
调试,测试及运行结果:
调试:
1.转化成二进制:
2.转化成图灵机扩展二进制编码:
出现错误,通过对代码修改调整
扩展二进制编码可以正确输出,但所在数组有些值出现乱码,检查发现多用了++符号,
导致数组出现空值,
调整后数组值正确
测试:
测试图灵机命令运算是否正确:
运行结果:
五,经验归纳:
所遇问题:
- 由于不足够细心导致一些语法问题;
- 二进制无法正确的转化成扩展二进制编码;
- 输出了正确的扩展二进制编码,但图灵运算指令依旧不能实现;
解决:
- 单独测试图灵机运算指令代码块,发现其可以正确实现;
- 检查发现扩展二进制编码程序块思路及算法没有问题,将二进制的倒序输出改成正序输出,并通过for循环输出,实现正确结果。
- 利用debug调试,发现扩展二进制编码虽然可以正确输出,但其所在数组存储不对,没有依次存储,导致有乱码情况,检查发现是++运算符的使用有误,导致数组出现空值,通过对其修改实现正确输出。
归纳:
一次次的修改,一次次的完善,就离成功实现更进一步,中途切莫放弃,出现问题要充分利用调试知道问题所在,如此可更有目的的解决问题,懂得变通,多尝试几种方法,切莫钻牛角尖,抓住一处不放,多和朋友沟通探讨,集思广益,发现问题,并有效解决。