Turing UN*2

1.题目分析

（1）题目：对于任意给定的一台Turing机和任意给定的字符串w ( w不含空格)，编程模拟此Turing机的运行过程，要求输出从开始运行起的每一步骤的结果。（本次实验模拟了UN*2 Turing 机，输入正整数，经过转化后，Turing机对其编码执行操作，最后再经转化输出一个正整数。）

（2）分析：

         步骤1：输入一个正整数，调用transformation()函数将其转换成二进制，然后将其转换成字符串，在字符串后添加“，”，将字符串中的“1”用“01”替代，将“，”用“0110”替代，“0”可保持不变，因此输出图灵机可识别的二进制位码；

步骤2：将字符串分割成字符数组，让二进制位码存入字符数组中，让图灵机执行可识别的编码，输出结果；

步骤3：将输出结果转换成二进制，然后再转换成十进制，最终输出一个正整数。

2.算法设计思路

算法设计思路：

（1）本次程序设计采用c++编程语言。首先，输入一个正整数，将其转换成二进制；然后运用<sstream>库中的类ostringstream将int型转换成字符串，运用<string>库中的append()函数在字符串末尾添加一个“，”，再使用replace函数将字符串中的“1”用“01”替代，将“，”用“0110”替代，“0”可保持不变，再使用append函数在其末尾添加两个0，以便后面运算；

（2）接着定义一个字符数组，运用strcpy()函数将字符串分割成字符数组；然后使用for循环，在for循环中使用if...else...嵌套语句让图灵机对可执行编码进行操作，最后将输出结果转换为string 类型；

（3）最后，将运行结果收缩为二进制，将字符串中的“0110”清空；将“01”用“1”替代，“0”保持不变，然后在调用transformatin1()将二进制转换为十进制。

3.代码

//title:Turing UN*2
//author:qiuerduoer
//time:2019/03/23#include <iostream>
#include <math.h>
#include <string>
#include <sstream>
#include <stdlib.h>
using namespace std;
int transformation(int num)//将十进制转换成二进制
{   int result=0,n=1,i,temp;temp=num;while(temp){  i=temp%2;result=n*i+result;n*=10;temp=temp/2;}return result;
}
//来源网上(string_replace()函数，可将字符串中的某个字符用其它字符替代)
void string_replace( std::string &strBig, const std::string &strsrc, const std::string &strdst) 
{std::string::size_type pos = 0;std::string::size_type srclen = strsrc.size();std::string::size_type dstlen = strdst.size();while( (pos=strBig.find(strsrc, pos)) != std::string::npos ){strBig.replace( pos, srclen, strdst );pos += dstlen;}
}
int transformation1( string ss)//将二进制转换为十进制
{  char c[4];strcpy(c,ss.c_str());//将字符串型分割成字符数组int l = atoi(c);//将字符串数组的数字转换为int型,方便后面运算cout<<"去掉开头多余0后的二进制:"<<l<<endl;int count=0,i=1,temp,r=0; //将数字中的每一位存入数组，以便将二进制转换为十进制int a[10]={0};temp=l;while(temp!=0) {  temp/=10;count++;}while((l/10)!=0){  a[count-i]=l%10;l/=10;i++;}a[0]=l;for(int j=0;j<count;j++){  r+=a[j]*(pow(2,(count-1)-j));//求十进制}return (r);
}
int main()
{   int m,t1;cout<<"请输入数据：";cin>>m;t1=transformation(m);ostringstream myos;//将int型转换成string型myos<<t1;string s=myos.str();cout<<"转换为二进制："<<s<<endl;string b=",";s.append(b);//在字符串后添加一个’，’string_replace(s,"1","01");//将二进制收缩，“1”用‘01’替代string_replace(s,"0","0");//‘0’用‘0’替代，这步可省略string_replace(s,",","0110");//‘，’用‘0110’替代string n="00";//在末尾处添加0以便计算cout<<"扩展后的结果:"<<s<<endl;s.append(n);char c[20];strcpy(c,s.c_str());//将字符串型分割成字符数组int in_state=0;//内态char input;//输入string str;for( int i=0;i<20;i++){   input=c[i];if (in_state==0 && input=='0')//内态为0，输入为0{  in_state=0;//内态为0c[i]='0';//输出为0}else if(in_state==0 && input=='1')//内态为0，输入为1{   in_state=1;//内态为1c[i]='0';//输出为0}else if(in_state==1 && input=='0')//内态为1，输入为0{      in_state=0;//内态为0c[i]='1';//输出为1}else if(in_state==1 && input=='1')//内态为1，输入为1{ in_state=10;//内态为10c[i]='0';//输出为0}else if(in_state==10 && input=='0')//内态为10，输入为0{      in_state=11;//内态为11c[i]='1';//输出为1}else if(in_state==11 && input=='0')//内态为11，输入为0{      in_state=0;//内态为0c[i]='1';//输出为1}//将字符数组转为string类型str = c;cout<<"运行结果"<<i<<":"<<str<<endl;//在原有基础上添加可以用str += ch;}//将位码转换为二进制string_replace(str,"0110","");//将'0110'清空string_replace(str,"01","1");//将'01'用'1'替代string_replace(str,"0","0");//将'0'用'0'替代cout <<"运行结果（二进制）为:"<< str << endl; int t3;t3=transformation1(str);//将二进制转换为十进制cout<<"最终结果（十进制）为:"<<t3<<endl;return 0;
}

4.运行结果

5.收获与总结

（1）收获

通过本次实验，我收获颇多。首先，我学会了如何将int型转化为string型，还查询到append（）函数可以在字符串中添加字符；然后在查询资料时还发现了replace()函数，它可将字符串中的某些字符用其它字符替换；还有学会如何使用strcpy()将字符串分割成字符数组等。

总之，在编写程序过程中遇到许多不会的及难以解决的小问题，我均通过网上搜索解决了诸多问题。所以遇到问题千万不要马上放弃，可以查查有没有解决的方法。

（2）不足

我觉得我的程序好繁杂，可读性不强，就一直在int型和string型和数组中转来转去的，因为就按照自己的思路写下来   的，我自己可以理解，但供别人看可能有点儿难理解吧。

还有就是将图灵机每一次运行结果输出的那块地方，因为我设的的数组长度是20，它就会输出20次运行结果，实际上 就例如输入正整数3，只要输出8次就可以得到结果。之前我尝试了在内态为“11”，输入为“0”时使用break跳出循环（因为图灵机遇到“110”要stop）,但是结果是错误的，然后我就删掉了break，因此结果得出现20次。