题目内容

对于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循环实现了这一运算。总的来说在这次程序编写过程中，没有遇到什么太大问题，但在程序编写这方面还需要进一步优化。