题目内容
对于XN+1或XN*2图灵机进行模拟,任意给定的十进制数a,转换为收缩扩展二进制的编码,再编程模拟此Turing机的运行过程,要求输出从开始运行起的每一步骤的结果。
算法分析
(1)把输入的十进制数转化为二进制;
(2)再将二进制数转化为拓展二进制;
(3)根据如下运算指令实现图灵机运算。
0 0 ->0 0 R,
0 1 ->1 0 R,
1 0 ->0 1 R,
1 1 ->10 0 R,
10 0 ->11 1 R,
11 0 ->0 1 STOP。
概要设计
利用多个for循环求出输入十进制数的二进制和拓展二进制,再利用for循环和if条件句的嵌套使用模拟图灵机的运算过程。
算法流程图如下:
代码实现
程序源代码如下:
#include<iostream>
#define MAX 32
using namespace std;
int main() {
int a[MAX], b[MAX], c[MAX]; //用数组c存放二进制,数组a存放拓展二进制
int N, temp = 0, temp1 = 0;
int flag = 0; //内态变量flag
cout << "请输入一个十进制数:";
cin >> N;
for (int i = 0; i < MAX; i++) { //求二进制
b[i] = N % 2;
N = N / 2;
temp1++;
if (N == 0)
break;
}
for (int i = 0, j = temp1 - 1; i < temp1; i++, j--) {
c[j] = b[i];
}
cout << "转换为二进制为:" << endl;
for (int i = 0; i < temp1; i++) {
cout << c[i];
}
cout << endl;
int n = 1;
for (int i = 0; i < temp1; i++) { //二进制转换为拓展二进制
if (c[i] == 1) {
a[n] = 1;
a[n + 1] = 0;
n = n + 2;
temp = temp + 2;
} else if (c[i] == 0) {
a[n] = 0;
n = n + 1;
temp = temp + 1;
}
}
//拓展二进制前后补0和110
a[0] = 0;
a[temp + 1] = 1;
a[temp + 2] = 1;
a[temp + 3] = 0;
a[temp + 4] = 0;
cout << "转换为拓展二进制为:" << endl;
for (int i = 0; i < temp + 5; i++) {
cout << a[i];
}
cout << endl;
cout << "图灵机(XN*2)计算过程为:" << endl;
//图灵机运算过程
for (int i = 1; i < temp + 5; i++) {
if (flag == 0 && a[i] == 0) //00->00R
{
flag = 0;
a[i] = 0;
for (int i = 0; i < temp + 5; i++) {
cout << a[i];
}
cout << endl;
} else if (flag == 0 && a[i] == 1) //0 1->1 0R
{
a[i] = 0;
flag = 1;
for (int i = 0; i < temp + 5; i++) {
cout << a[i];
}
cout << endl;
} else if (flag == 1 && a[i] == 0) //1 0->0 1R
{
a[i] = 1;
flag = 0;
for (int i = 0; i < temp + 5; i++) {
cout << a[i];
}
cout << endl;
} else if (flag == 1 && a[i] == 1) //1 1->10 0R
{
a[i] = 0;
flag = 10;
for (int i = 0; i < temp + 5; i++) {
cout << a[i];
}
cout << endl;
} else if (flag == 10 && a[i] == 0) //10 0R->11 1R
{
a[i] = 1;
flag = 11;
for (int i = 0; i < temp + 5; i++) {
cout << a[i];
}
cout << endl;
} else if (flag == 11 && a[i] == 0) //11 0R->0 1 STOP
{
a[i] = 1;
flag = 0;
for (int i = 0; i < temp + 5; i++) {
cout << a[i];
}
cout << endl;
}
}
return 0;
}
测试结果
(1)输入十进制数4对程序进行测试,测试结果如下:
(2)输入十进制数7进行测试,测试结果如下:
心得体会
在这次程序设计过程中,首先遇到的问题就是二进制的转换,刚开始存放二进制数时,存放顺序不对,后来用定义新的c数组相反存放b数组的数据,解决了二进制转换问题。然后就是图灵机运算程序,一开始摸不着头脑,后来想到用if条件句多次利用,把图灵机运算指令分条编写,外加上for循环实现了这一运算。总的来说在这次程序编写过程中,没有遇到什么太大问题,但在程序编写这方面还需要进一步优化。