pytho实现图灵机XN*2命令过程

一．题目名称：

“图灵机”

二．题目内容

对于任意给定的一台turing机和任意给定的字符串w(w不含空格)，编程模拟turing机的运行过程，要求输出从开始运行起的每一步的结果。用C/C++/Java/Python实现程序解决问题。

三．算法设计

1.输入数字
2.使用内置方法bin()将数字转化为二进制付给字符串
3.将二进制写为扩展形式.读到1输出加上10，否则加0，最后加110
4.将扩展形式转化为命令过程，定义一个index表示内态，利用for i in range()做循环字符串读取，在循环使用条件选择语句模拟命令规则

5.将命令结果缩略为二进制的扩展形式，遇到01或者10输出1，遇到00输出0，遇到110输出2
6.将扩展形式化为标准二进制数
7.将二进制数还原为十进制
python代码

import math
#从键盘输入十进制数
print("请输入一个十进制数：")
w = int(input())

#使用内置方法bin(),将十进制转为二进制
a = bin(w)
str1 = str(a)
print("该数的二进制数为：%s"%str1)

#将二进制转化为扩展形式
def expand(str1):
    str2 = str()
    for i in range(len(str1)):
        if(str1[i] == "1"):
            str2 = str2+"10"
        else:
            str2 = str2+"0"
    str2+="110"
    str2=str2[1:]
    return str2

#将扩展形式转化为命令过程
def command(str2):
    print("您输入数字二进制扩展形式图灵机XN*2命令过程为：" )
    str2=str2+"00"
    print(str2)
    str3 = str()
    index = 0     #内态
    for i in range(1,len(str2)):
        if(index == 0 and int(str2[i])==0):    #内态为0输出为0———>内态为0输出为0右移一位
            str3 = str2[:i] + "0" +str2[i+1:]
            print(str3)
            str2=str3
        elif(index ==0 and int(str2[i])==1):   #内态为0输出为1———>内态为1输出为0右移一位
            index = 1
            str3 = str2[:i] + "0" + str2[i+1:]
            print(str3)
            str2=str3
        elif(index==1 and int(str2[i])==0):   #内态为1输出为0———>内态为0输出为1右移一位
            index = 0
            str3 = str2[:i] + "1" + str2[i + 1:]
            print(str3)
            str2=str3
        elif(index==1 and int(str2[i])==1):   #内态为1输出为1———>内态为10输出为0右移一位
            index = 10
            str3 = str2[:i] + "0" + str2[i + 1:]
            print(str3)
            str2=str3
        elif (index == 10 and  int(str2[i]) == 0):   #内态为10输出为0———>内态为11输出为1右移一位
            index = 11
            str3 = str2[:i] + "1" + str2[i + 1:]
            print(str3)
            str2=str3
        elif(index == 11 and int(str2[i]) == 0):    #内态为11输出为0———>内态为0输出为1停机
            index == 0
            str3 = str2[:i] + "1" + str2[i + 1:]
            print(str3)
            print("STOP")
            break
    return str3

#将命令结果缩写为二进制的扩展形式
def contract(str3):
    str4=str()
    for i in range(1,len(str3)-4,2):
        if(str3[i]+str3[i+1] == "01" or str3[i]+str3[i+1] == "10"):
            str4=str4+"1"
        elif(str3[i]+str3[i+1] == "00"):
            if(str3[i+2]=="0"):
                str4=str4+"00"
            else:
                str4=str4+"0"
    return str4
#将二进制的扩展形式转化为缩略形式
def restore(str4):
    str5=str()
    for i in range(len(str4)):
        if(str4[i]!="2"):   #没有读到2的时候将值赋给str5,读到2的时候break
            str5 += str4[i]
        else:
            break
    return str5

str2=expand(str1)
print("您输入数字的二进制扩展形式为：%s"%str2)
str3=command(str2)
print("命令转化结果为：%s"%str3)
str4=contract(str3)
print("将命令转化结果缩写为二进制的扩展形式为：%s"%str4)
str5=restore(str4)
print("二进制的缩略形式为:%s"%str5)

#将二进制还原为十进制
num = int(str5, 2)   #要转化的字符串为str5,进制数为2进制
print("二进制进制转化为十进制为：%d"%num)
print("恭喜您 图灵机XN*2命令转换成功")
print("您已完成%d的倍数计算"%w)

四.运行结果