XN*2图灵机C++模拟实现

题目内容

对于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条件句的嵌套使用模拟图灵机的运算过程。
算法流程图如下:
XN*2图灵机C++模拟实现

代码实现

程序源代码如下:

#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对程序进行测试,测试结果如下:
XN*2图灵机C++模拟实现
(2)输入十进制数7进行测试,测试结果如下:
XN*2图灵机C++模拟实现

心得体会

在这次程序设计过程中,首先遇到的问题就是二进制的转换,刚开始存放二进制数时,存放顺序不对,后来用定义新的c数组相反存放b数组的数据,解决了二进制转换问题。然后就是图灵机运算程序,一开始摸不着头脑,后来想到用if条件句多次利用,把图灵机运算指令分条编写,外加上for循环实现了这一运算。总的来说在这次程序编写过程中,没有遇到什么太大问题,但在程序编写这方面还需要进一步优化。

上一篇:Python mysql 操作小类,供大家用用


下一篇:算法提高 概率计算