模拟图灵机XN*2的原理，输入一个数，输出这个数*2的结果。
一、 题目分析
1. 输入一个十进制数
2. 把十进制数转化为二进制数，并用数组存放每一个0和1。
3. 把二进制数转化为扩展编码，用新的数组存放。并且规定第一个数是0，末尾是110。
4. 按照图灵机XN*2的步骤，对扩展编码遍历。输出每一步的结果，再把最后得到的编码存放到一个新的数组中。
5. 将新的编码还原成二进制编码。
6. 把二进制数转化成十进制数，输出结果。
二、 算法构造
1. 实现把十进制数转化成二进制数：
采用除2取余法，把十进制数不断除以2取余数，把每一个余数放入一个足够长的数组当中。再把数组的数倒置，结果就是二进制的表示。
j=0;
while(number>0)
{
array[j]=number%2;
number=number/2; //循环除2取余存入数组
j++;
}
for(int i=0;i<j/2;i++)
{
temp=array[i];
array[i]=array[j-1-i]; //把数组倒置，得到正常的二进制。
array[j-1-i]=temp;
}
- 把二进制数转换成扩展编码：
建立一个新的数组，默认第一个数是0，再从头开始遍历二进制数组，当二进制数组里的数为0时，就往新的数组中添加一个0。当二进制数组里的数为1时。就往新的数组中添加一个1和一个0。把二进制数组遍历完成后。再在新的数组的末尾添加两个1和一个0。
int array1[999];
array1[0]=0; // 默认第一个数是0
int k=1;
for(i=0;i<j;i++) //遍历二进制数组
{
if(array[i]==1)
{
array1[k]=1;k++;
array1[k]=0;k++; //遇到1就添加10
}
if(array[i]==0) //遇到0就添加0
{
array1[k]=0;k++;
}
}
array1[k]=1;
array1[k+1]=1;
array1[k+2]=0; //把数组最后三位数变成110
- 根据XN*2的规则，按步骤把扩展编码转化成新的扩展编码
定义内态变量inside，内态为0是，赋值为0，内态为1时，赋值为1；内态为10时，赋值为2,；内态为11时，赋值为3。再定义一个新数组存放转换后的数据。用if语句判断内态和输入值的情况，并作出相应变化。
int array2[999];
for(i=0;i<k+3;i++)
array2[i]=array1[i]; //定义新的数组并复制扩展编码的数组
int inside=0; //内态
i=0;
int time=0; //统计步骤
while(i<k+3)
{
if(inside==0&&array1[i]==0) //00->00 R
{
inside=0;
array2[i]=0;
i++;
time++;
printf("第%d次的结果：",time);
for(int m=0;m<k+3;m++)
printf("%d ",array2[m]);
printf("\n");
}
if(inside==0&&array1[i]==1) //01->10 R
{
inside=1;
array2[i]=0;
i++;
time++;
printf("第%d次的结果：",time);
for(int m=0;m<k+3;m++)
printf("%d ",array2[m]); //每次变化后用for语句遍历新的
数组，得到每一步的结果。
printf("\n");
}
if(inside==1&&array1[i]==1) //11->10 0 R
{
inside=2;
array2[i]=0;
i++;
time++;
printf("第%d次的结果：",time);
for(int m=0;m<k+3;m++)
printf("%d ",array2[m]);
printf("\n");
}
if(inside==1&&array1[i]==0) //10->01 R
{
inside=0;
array2[i]=1;
i++;
time++;
printf("第%d次的结果：",time);
for(int m=0;m<k+3;m++)
printf("%d ",array2[m]);
printf("\n");
}
if(inside==2&&array1[i]==0) //10 0->11 1 R
{
inside=3;
array2[i]=1;
i++;
time++;
printf("第%d次的结果：",time);
for(int m=0;m<k+3;m++)
printf("%d ",array2[m]);
printf("\n");
}
if(inside==3&&array1[i]==0) // 11 0-> 01 STOP
{
inside=0;
array2[i]=1;
time++;
printf("第%d次的结果：",time);
for(int m=0;m<k+3;m++)
printf("%d ",array2[m]);
printf("\n");
break; //用break跳出循环实现STOP
}
- 译码过程，把扩展编码翻译成二进制数：
定义一个新数组存放译码的结果。从第一个数开始遍历数组，遇到当前数为0并且下一个数为1时，往数组里添加一个1，记号移动两个单位。否则往数组添加一个0，记号移动一个单位。由于扩展编码数组最后是110，因此变化后的数组最后为01，因此无意义。所以遍历到倒数第三个数是结束。即可得到*2后的二进制编码。
int array3[999]; // 定义新数组存放译码后的二进制数
int a=0; // 新数组存放数的起始下标
int count=1; // 记号变量，从第二个数开始遍历
while(count<i-2) //遍历到倒数第3个数结束
{
if(array2[count]==0&&array2[count+1]==1)
{
array3[a]=1;
a++;
count+=2;
}
else
{
array3[a]=0;
a++;
count++;
}
}
- 把二进制数转化成十进制数
从头开始遍历数组，第一个数2的数组长度-1次方。第二个数2的数组长度-2次方。依次类推。再把每一个结果相加。添加头文件<math.h>，引用pow（2，x）函数来计算幂函数。最后输出结果。
for(int n=0;n<a;n++)
printf("%d ",array3[n]);
printf("\n");
int len=a; //获取二进制数组的长度
int number1=0; //表示最终的十进制数
for(i=0;i<len;i++)
{
a--;
number1=number1+array3[i]*pow(2,a);
}
三、调试结果