第二次上机总结---图灵机
作者:A.y.
日期:2019/3/23
运行环境:Visual C++ 6.0
一、问题描述:对于XN×2型图灵机和任意给定字符串w(w不含空格),编程模拟此图灵机的运行过程,要求输出从开始运行起的每一步骤的结果。(要求掌握图灵机的基本概念和基本结构,理解图灵机的基本指令和编码方式;掌握图灵机的编程方法)
二、算法设计思路:
1.定义两个字符数组a[],b[]分别用来存储操作数的二进制表示和磁带码表示;
2.调用exchange1()函数将操作数转换为二进制数输出并保存到数组a[]中;
3.调用exchange2()函数将二进制数转换为磁带码输出并保存到数组b[]中;
4.调用newarray()函数将磁带码进行运算并将新的磁带码输出并保存到数组b[]中;
5.调用disaplay1()函数将运算后的磁带码转换为二进制数输出并保存到数组a[]中
6.调用display2()函数将运算后的二进制数转换为十进制数即运行结果然后输出。
算法设计流程图:
三、代码实现:
#include<stdio.h>
#define MAX 100
int length1,length2; /*二进制数组和磁带数组长度*/
void Init(char a[],char b[]) /*初始化数组a[],b[]*/
{
for(int i=0;i<MAX;i++)
{
a[i]=0;
b[i]=0;
}
}
void exchange1(int m,char a[]) /*十进制数转换为二进制数函数*/
{
int i,temp;
length1=0;
for(i=0;i<MAX;i++) /*给二进制数组赋值*/
{
a[i]=m%2;
m=m/2;
if(m!=0||a[i]!=0)
length1++;
}
for(i=0;i<length1/2;i++)
{
temp=a[i];
a[i]=a[length1-1-i];
a[length1-1-i]=temp;
}
printf("\n\t转化后的二进制数为:"); /*输出转换后的二进制数*/
for(i=0;i<length1;i++)
printf("%d",a[i]);
printf("\n\n");
}
void exchange2(char a[],char b[]) /*二进制位用磁带码表示函数*/
{
int i;
length2=0;
for(i=0;i<length1;i++) /*给磁带码数组赋值*/
{
if(a[i]==1)
{
b[length2]=0;
b[++length2]=1;
b[++length2]=0;
}
if(a[i]==0)
{
b[length2]=0;
b[++length2]=0;
}
}
b[++length2]=1;
b[++length2]=1;
for(i=length2+1;i<MAX;i++) /*将未赋值的数组元素初始化为0*/
b[i]=0;
printf("\t转化后的磁带码:"); /*输出初始磁带码*/
for(i=0;i<=length2+1;i++)
printf("%d",b[i]);
printf("\n\n");
}
void newarray(char b[]) /*磁带×2运算指令*/
{
int symbol=0;
for(int i=0;i<=MAX;i++) /*进行运算并将结果重新赋值给磁带码数组*/
{
if(b[i]==0)
{
if(symbol==1)
{
symbol=0;
b[i]=1;
}
else if(symbol==2)
{
symbol=3;
b[i]=1;
}
else if(symbol==3)
{
symbol=0;
b[i]=1;
b[i+1]=0;
break;
}
}
else if(b[i]==1)
if(symbol==0)
{
symbol=1;
b[i]=0;
}
else if(symbol==1)
{
symbol=2;
b[i]=0;
}
}
printf("\t运算后的磁带码为:"); /*输出运算后的磁带码*/
for(i=0;i<=length2+3;i++)
printf("%d",b[i]);
printf("\n\n");
}
void display1(char a[],char b[]) /*运算后磁带码转换为二进制数的函数*/
{
int i,symbol=0;
length1=0;
for(i=0;i<MAX;i++)
{
if(b[i]==1)
{
a[length1++]=1;
symbol=1;
break;
}
}
for(;i<MAX;i++)
{
if(b[i]==0)
{
if(b[i+1]==0)
a[length1++]=0;
else if(b[i+1]==1)
if(b[i+2]==1)
{
printf("\t运算后的二进制数为:");
for(i=0;i<length1;i++)
printf("%d",a[i]);
printf("\n\n");
return;
}
else
a[length1++]=1;
}
}
}
void display2(char a[]) /*将运算后的二进制数转换为十进制数*/
{
int i,j,temp=0;
for(i=0;i<length1;i++)
{
for(j=length1-1;j>i;j--)
a[i]=a[i]*2;
temp=temp+a[i];
}
printf("\t运算结果为:");
printf("%d\n",temp);
}
int main()
{
int m;
char a[MAX],b[MAX]; /*定义字符数组a[],b[]*/
Init(a,b);
printf("\t请输入进行操作的十进制数:");
scanf("%d",&m); /*输入进行操作的十进制数*/
exchange1(m,a);
exchange2(a,b);
newarray(b);
display1(a,b);
display2(a);
return 0;
}
四、调试截图:
Init()函数调试(初始化二进制数组和磁带码数组):
exchange1()函数调试,当输入十进制数为7时(将十进制数转换为二进制数存入数组a[]中):
exchange2()函数调试(二进制数转换为磁带码存入数组b[]中):
newarray()函数调试(将磁带码运算成新的磁带码并存入数组b[]中):
display1()函数调试(将新的磁带码转换为二进制数并存入数组a[]中):
五、测试截图:
exchang1()函数:
代码截图:
运行截图:
exchange2()函数:
代码截图:
运行截图:
newarray()函数:
代码截图:
运行截图:
display1()函数:
代码截图:
运行截图:
display2()函数:
代码截图:
运行截图:
六、源代码运行截图:
个人总结
通过两天的编码的调试,详细了解了图灵机XN×2的基本原理和基本结构,对于十进制二进制之间转换该如何编码也有了更深的理解。