java实现图灵机模型（XN*2）
一、算法介绍
Java实现XN x 2该图灵机模型指令如下 (其中未加粗正体的是当前内态，斜体加粗为输入态，R代表右移，STOP代表停止)
1. 0 ***0*** --> 0 ***0***，R
2. 0 ***1*** --> 1 ***0***，R
3. 1 ***0*** --> 0 ***1***，R
4. 1 ***1*** --> 10 ***0***，R
5. 10 ***0*** --> 11 ***1***，R
6. 11 ***0*** --> 0 ***1***，STOP
二、算法分析
- 首先需要将需要进行XN2指令的数转换成二进制*
- 在将得到的二进制转换成二进制编码。例如二进制11,的二进制编码就是01010110
-
然后根据指令再依次进行操作
此处上图演示
此过程也是本文中程序的运行实例结果
三、代码实现
(代码实现笔者用了两个类实现，下面我将两个类分开列出)
注：代码实现的主要思路在代码中的注释可以详细揣摩
1、Solution,java：
import java.util.ArrayList;
import java.util.List;
/**
* Produce: <br>
* 类Solution是类Result的父类主要。该类中有各种指令的执行方法和<br>
* 和界面的主要打印方法,以及这个项目的数据。且对数据进行了封装工作。<br>
* <br>
* Detail: <br>
* 方法public void processPrint(int input, int ergodicNum)是打印命令过程。<br>
* 方法public void listPrint()是打印二进制编码。<br>
* 方法public void instruct_1 (int input, int ergodicNum)是当内态为0的时候做指令。<br>
* 方法public void instruct_2 (int input, int ergodicNum)是当内态为1的时候做指令。<br>
* 方法public void instruct_3 (int input, int ergodicNum)是当内态为10的时候做指令。<br>
* 方法public void instruct_4 (int input, int ergodicNum)适当内态为11的时候做指令。<br>
* <br>
* Date:2019年3月17日
*/
class Solution {
private int internalStatus; //当前的内态
private String binaryCoding; //二进制编码
List<Integer> list = new ArrayList<Integer>(); //用list作图灵机工作时的可变二进制编码
public Solution() {
// TODO 自动生成的构造函数存根
internalStatus = 0;
binaryCoding = "0";
}
//对private 字段生成的getter和settet方法
public void setInternalStatus (int internalStatus) {
this.internalStatus = internalStatus;
}
public int getInternalStatus() {
return internalStatus;
}
public void setBinaryCoding(String binaryCoding) {
this.binaryCoding = binaryCoding;
}
public String getBinaryCoding() {
return binaryCoding;
}
/**
* 方法public void listPrint()是打印二进制编码。
*/
public void listPrint() {
for(int i = 0; i < list.size(); i++) {
System.out.print(list.get(i));
}
System.out.println();
}
/**
* 方法public void processPrint(int input, int ergodicNum)是打印命令过程。
* @param input 输入态
* @param ergodicNum 遍历次数
*/
public void processPrint(int input, int ergodicNum) {
String string = "";//用于判断此处执行到哪个地方
for(int i = 0; i < ergodicNum; i++) {
string += " ";
}
string += "|";//标记执行处
System.out.println(string);
//输出内态和输入态
System.out.print("此处内态为" + getInternalStatus());
System.out.println(",输入态为" + input);
}
/**
* 方法public void instruct_1 (int input, int ergodicNum)是当内态为0的时候做指令。
* @param input 输入态
* @param ergodicNum 遍历次数
*/
public void instruct_1 (int input, int ergodicNum) {
//参数ergodicNum是指遍历次数
System.out.print("step" + (ergodicNum + 1) + ":");//打印步骤
listPrint();//打印未经指令工作时的二进制编码
System.out.print(" ");
if(input < 0 || input > 1) {
//判断指令以防出错
System.out.println("输入态指令错误!");
return ;//若出错直接跳出程序
}
//当内态为0,且输入态也为0，内态和输入态都不做变换
if(input == 0) {
processPrint(input,ergodicNum);//打印指令过程
//打印经过指令后的内态和输入
System.out.print("经过指令处理之后此处的内态为" + getInternalStatus());
System.out.print(",输入态为" + list.get(ergodicNum));
System.out.println(",R(右移)");
System.out.print("处理后的结果为:");
listPrint();//打印经过指令之后的二进制编码
}
//当内态为0,且输入态为1时
if(input == 1) {
processPrint(input, ergodicNum);
setInternalStatus(1);//内态变为1
list.set(ergodicNum, 0);//输入态变为0
System.out.print("经过指令处理之后此处的内态为" + getInternalStatus());
System.out.print(",输入态为" + list.get(ergodicNum));
System.out.println(",R(右移)");
System.out.print("处理后的结果为:");
listPrint();
}
System.out.println();
System.out.println();
}
/**
* 方法public void instruct_2 (int input, int ergodicNum)是当内态为1的时候做指令。
* @param input 输入态
* @param ergodicNum 遍历次数
*/
public void instruct_2 (int input, int ergodicNum) {
//如方法instruct_1(int input, int ergodicNum)中的注释
System.out.print("step" + (ergodicNum + 1) + ":");
listPrint();
if(input < 0 || input > 1) {
//保护程序代码块
System.out.println("输入态指令错误!");
return ;
}
System.out.print(" ");
//内态为1且输入态为0
if(input == 0) {
//过程打印如方法instruct_1(int input, int ergodicNum)注释
processPrint(input, ergodicNum);
setInternalStatus(0);//把内态置为0
list.set(ergodicNum, 1);//输入态置为1
//过程打印如方法instruct_1(int input, int ergodicNum)注释
System.out.print("经过指令处理之后此处的内态为" + getInternalStatus());
System.out.print(",输入态为" + list.get(ergodicNum));
System.out.println(",R(右移)");
System.out.print("处理后的结果为:");
listPrint();
}
//内态为1且输入态为1
if(input == 1) {
//过程打印如方法instruct_1(int input, int ergodicNum)注释
processPrint(input, ergodicNum);
setInternalStatus(10);//把内态置为10
list.set(ergodicNum, 0);//输入态置为0
//过程打印如方法instruct_1(int input, int ergodicNum)注释
System.out.print("经过指令处理之后此处的内态为" + getInternalStatus());
System.out.print(",输入态为" + list.get(ergodicNum));
System.out.println(",R(右移)");
System.out.print("处理后的结果为:");
listPrint();
}
System.out.println();
System.out.println();
}
/**
* 方法public void instruct_3 (int input, int ergodicNum)是当内态为10的时候做指令。
* @param input 输入态
* @param ergodicNum 遍历次数
*/
public void instruct_3 (int input, int ergodicNum) {
//过程打印如方法instruct_1(int input, int ergodicNum)注释
System.out.print("step" + (ergodicNum + 1) + ":");
listPrint();
System.out.print(" ");
if(input != 0) {
//代码保护块
System.out.println("输入态指令错误!");
return ;
}
//当内态为10且输入态为0
if(input == 0) {
//过程打印如方法instruct_1(int input, int ergodicNum)注释
processPrint(input, ergodicNum);
setInternalStatus(11);//内态置为11
list.set(ergodicNum, 1);//输入态置为1
//过程打印如方法instruct_1(int input, int ergodicNum)注释
System.out.print("经过指令处理之后此处的内态为" + getInternalStatus());
System.out.print(",输入态为" + list.get(ergodicNum));
System.out.println(",R(右移)");
System.out.print("处理后的结果为:");
listPrint();
}
System.out.println();
System.out.println();
}
/**
* 方法public void instruct_4 (int input, int ergodicNum)是当内态11的时候做指令。
* @param input 输入态
* @param ergodicNum 遍历次数
*/
public void instruct_4 (int input, int ergodicNum) {
//打印如方法instruct_1(int input, int ergodicNum)注释
System.out.print("step" + (ergodicNum + 1) + ":");
listPrint();
System.out.print(" ");
if(input != 0) {
//代码保护块
System.out.println("输入指令错误");
return ;
}
//当内态为11且输入态为0
if(input == 0) {
//过程打印如方法instruct_1(int input, int ergodicNum)注释
processPrint(input, ergodicNum);
setInternalStatus(0);//内态置为0
list.set(ergodicNum, 1);//输入态置为1
//过程打印如方法instruct_1(int input, int ergodicNum)注释
System.out.print("经过指令处理之后此处的内态为" + getInternalStatus());
System.out.print(",输入态为" + list.get(ergodicNum));
System.out.println(",STOP");
System.out.print("处理后的结果为:");
//打印最终得到的为二进制编码
for(int i = 0; i < list.size(); i++) {
System.out.print(list.get(i));
}
System.out.print(0);
}
System.out.println();
System.out.println();
System.out.println();
}
}
2、Result.java:
import java.util.*;
/**
* Produce:<br>
* 类Result继承类Solution,需要得到其封装的字段和方法。<br>
* <br>
* Detail:<br>
* 方法public void obtainbinaryData ()是获得二进制编码<br>
* 方法public String transformData ()是将十进制数转换成二进制编码<br>
* 方法public void transformNum ()是将二进制编码转换成十进制数<br>
* 方法public void obtainResult ()是进行指令操作获得结果<br>
* 方法public static void main(String[] args)是程序入口
* <br>
* Date:2019年3月17日
*/
public class Result extends Solution {
//输入
Scanner scanner = new Scanner(System.in);
/**
* 方法public void obtainbinaryData ()是获得二进制编码
*/
public void obtainbinaryData () {
super.setBinaryCoding(transformData());//得到二进制编码
//为可变二进制编码list赋值
for(int i = 0; i < super.getBinaryCoding().length(); i++) {
//当得到的该处值是数字即加一层保护
if(super.getBinaryCoding().charAt(i) >= 48 && super.getBinaryCoding().charAt(i) <= 57) {
//就用list.add()为super.list的末尾加一个值
super.list.add(Integer.parseInt(super.getBinaryCoding().charAt(i)+""));
} else {
//保护代码块
System.out.println("输入指令错误!");
}
}
super.list.add(0);
}
/**
* 方法public String transformData ()是将十进制数转换成二进制编码
* @return binaryCode
*/
public String transformData () {
System.out.println("请输入需要执行XN*2的数(十进制):");
int data = 0;//需要执行XN*2的数(十进制)
String binary = "";//需要执行XN*2的数(二进制)
String binaryCode = "0";//二进制编码
data = scanner.nextInt();//输入
binary = Integer.toBinaryString(data);//转换成二进制
binary += ",";//给二进制末尾加","确保结束
System.out.println("得到的二进制数:" + binary);
//二进制转换成二进制编码
for(int i = 0; i < binary.length(); i++) {
//如果该处为0就给编码加一个0,确保得到的数00
if(binary.charAt(i) == '0'){
binaryCode += "0";
} else if(binary.charAt(i) == '1') {
//如果为1就给编码加10,确保得到的是010
binaryCode += "10";
} else {
//不是1也不是0那就是",",就给末尾加110,确保为0110
binaryCode += "110";
}
}
System.out.println("得到的二进制编码:" + binaryCode);
return binaryCode;
}
/**
* 方法public void transformNum ()是将二进制编码转换成十进制数
*/
public void transformNum () {
String tempString = "";
String binaryString = "";
//把最终的二进制编码赋给字符串tempString
for(int i = 0; i < super.list.size(); i++) {
tempString += super.list.get(i);
}
//进行转换
for(int i = 0; i < tempString.length(); i++) {
//该处为0
if(tempString.charAt(i) == '0') {
//判断下一位置
if(tempString.charAt(i + 1) == '1') {
//下一位值是1且下一位置的下一位置也是1,则表明遇见了0110
if(tempString.charAt(i + 2) == '1') {
break;//就break掉完成转换
} else {
//此处代表下一位值是1且下一位置的下一位置是0,则表明遇见了010
binaryString += 1;//就给二进制字符串压进一个1
}
} else {
//此处代表该位置为0且下一位置也为0
binaryString += 0;//就给二进制字符串压进一个0
}
} else {
//保护代码块
if(tempString.charAt(i + 1) == '0') {
continue;
} else {
break;
}
}
}
System.out.println("得到的二进制结果为:" + binaryString);
System.out.println("得到的十进制结果为:" + Integer.parseInt(binaryString, 2));
}
/**
* 方法public void obtainResult ()是进行指令操作获得结果
*/
public void obtainResult () {
obtainbinaryData();//方法嵌套
//进行命令执行,遍历
for(int i = 0; i < super.list.size(); i++) {
//switch当前状态
switch (super.getInternalStatus()) {
//为0，则进入内态为0的方法
case 0:
super.instruct_1(super.list.get(i), i);
break;
//为1，则进入内态为1的方法
case 1:
super.instruct_2(super.list.get(i), i);
break;
//为10，则进入内态为10的方法
case 10:
super.instruct_3(super.list.get(i), i);
break;
//为11，则进入内态为11的方法
case 11:
super.instruct_4(super.list.get(i), i);
break;
default:
break;
}
}
transformNum();//翻译得到的值
}
public static void main(String[] args) {
// TODO 自动生成的方法存根
Result result = new Result();
result.obtainResult();
}
}
四、总结
在实现图灵机模型（XN x 2）这个题目中笔者最先想到的是使用线性表解决，其主要原因在与线性表的增删改查的实现比较容易，所以笔者采用这种方法。哈哈哈，毕竟可以复习数据结构嘛。。。。当然了条条大路通罗马，或许各位同胞会有更加简单的方法或者本文有不足的地方，希望评论指出。