模拟图灵机运行过程,实现XN*2

  • Post author:
  • Post category:其他




一,题目分析:

模拟图灵机的运算过程,运用图灵机的基本指令和编码方式实现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.转化成图灵机扩展二进制编码:


出现错误,通过对代码修改调整


扩展二进制编码可以正确输出,但所在数组有些值出现乱码,检查发现多用了++符号,


导致数组出现空值,


调整后数组值正确



测试:

测试图灵机命令运算是否正确:



运行结果:



五,经验归纳:



所遇问题:

  1. 由于不足够细心导致一些语法问题;
  2. 二进制无法正确的转化成扩展二进制编码;
  3. 输出了正确的扩展二进制编码,但图灵运算指令依旧不能实现;



解决:

  1. 单独测试图灵机运算指令代码块,发现其可以正确实现;
  2. 检查发现扩展二进制编码程序块思路及算法没有问题,将二进制的倒序输出改成正序输出,并通过for循环输出,实现正确结果。
  3. 利用debug调试,发现扩展二进制编码虽然可以正确输出,但其所在数组存储不对,没有依次存储,导致有乱码情况,检查发现是++运算符的使用有误,导致数组出现空值,通过对其修改实现正确输出。



归纳:

一次次的修改,一次次的完善,就离成功实现更进一步,中途切莫放弃,出现问题要充分利用调试知道问题所在,如此可更有目的的解决问题,懂得变通,多尝试几种方法,切莫钻牛角尖,抓住一处不放,多和朋友沟通探讨,集思广益,发现问题,并有效解决。



版权声明:本文为c2607119981原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。