JAVA实现图灵机XN*2

一. 内容

​ 对于XN*2图灵机进行模拟，任意给定的十进制数a，转换为收缩扩展二进制的编码，再编程模拟此Turing机的运行过程，要求输出从开始运行起的每一步骤的结果。

二. 步骤

1. 算法分析

JAVA实现模拟图灵机实现自然数乘2的过程。

编码转换规则：

0→0；1→10；, →110;

处理方法：

内态为0，输入为0→内态为0，输出为0，右移；

内态为0，输入为1→内态为1，输出为0，右移；

内态为1，输入为0→内态为0，输出为1，右移；

内态为1，输入为1→内态为10，输出为0，右移；

内态为10，输入为0→内态为11，输出为1，右移；

内态为11，输入为0→内态为0，输出为1，STOP；

2. 概要设计

3. 测试

测试代码：

static void test(){
  Random r = new Random();
   *//**随机生成**5**个数用来测试
\*   for(int i=0;i<3;i++){
     *//**随机生成范围**[0,999)
\*     int t=r.nextInt(999);
     System.*out*.println("输入的数为： " + t);
     StringBuffer sb = *toBinary*(t);
     System.*out*.println("编码后为：" + sb);
     *calculate*(sb);
     System.*out*.println("计算结果为：" + sb);
     *//**将末尾的逗号去掉
\*     sb.delete(sb.length()-2, sb.length());
     *//**把扩展二进制编码的**10**替换成为**1
\*     String s = sb.toString().replace("10", "1");
     System.*out*.println("计算结果转换为二进制为：" + s);
     *//Integer.parseInt(String s ,int radix)**方法，以十进制输出**radix**进制数**s
\*   System.*out*.println("计算结果转换为十进制为："+Integer.*parseInt*(s,2));
   }
 }

实现结果：

4. 调试

5. 代码实现

package Turing;

import java.util.Random;
import java.util.Scanner;
public class Turing {
    //将整型十进制正数编码为所需要的二进制原码
    static StringBuffer toBinary(int a1){
        String s;
        s = Integer.toBinaryString(a1);         //返回int变量的二进制表示的字符串。
        //转化成扩展二进制编码
        StringBuffer sb = new StringBuffer(s.replace("1","10"));
        sb.append("11000");             //往转化的扩展二进制编码后添加“，”和补0的扩展二进制编码
        return sb;
    }
    //将编码进行乘2计算
    static void calculate(StringBuffer sb){
        int inState = 0;        //内态变量
        //通过扩展二进制编码字符长度进行循环计算
        for(int i=0; i<sb.length(); i++){
            /*charAt()方法返回指定索引i处字符
               setcharAt()设置当前索引处字符内容*/

            //内态为0，输入为0 -> 内态为0，输出为0,右移计算下一位
            if(inState==0 & sb.charAt(i)=='0'){
                inState = 0;
                sb.setCharAt(i,'0');
                System.out.println("内态为0，输入为0，操作后改变为： " + sb +  " 内态为：" + inState + " 输出为：" + sb.charAt(i));
                continue;
            }
            //内态为0，输入为1 -> 内态为1，输出为0,右移计算下一位
            if(inState==0 & sb.charAt(i)=='1'){
                inState = 1;
                sb.setCharAt(i,'0');
                System.out.println("内态为0，输入为1，操作后改变为： "+sb+" 内态为："+inState+" 输出为："+sb.charAt(i));
                continue;
            }
            //内态为1，输入为0 -> 内态为0，输出为1,右移计算下一位
            if(inState==1 & sb.charAt(i)=='0'){
                inState = 0;
                sb.setCharAt(i,'1');
                System.out.println("内态为1，输入为0，操作后改变为： "+sb+" 内态为："+inState+" 输出为："+sb.charAt(i));
                continue;
            }
            //内态为1，输入为1 -> 内态为10，输出为0,右移计算下一位
            if(inState==1 & sb.charAt(i)=='1'){
                inState = 10;
                sb.setCharAt(i,'0');
                System.out.println("内态为1，输入为1，操作后改变为： "+sb+" 内态为："+inState+" 输出为："+sb.charAt(i));
                continue;
            }
            //内态为10，输入为0 -> 内态为11，输出为1 ,右移计算下一位
            if(inState==10 & sb.charAt(i)=='0'){
                inState = 11;
                sb.setCharAt(i,'1');
                System.out.println("内态为10，输入为0，操作后改变为："+sb+" 内态为："+inState+" 输出为："+sb.charAt(i));
                continue;
            }
            //内态为11，输入为0 -> 内态为0，输出为1 ,停止计算
            if(inState==11 & sb.charAt(i)=='0'){
                inState = 0;
                sb.setCharAt(i,'1');
                System.out.println("内态为11，输入为0，操作后改变为："+sb+" 内态为："+inState+" 输出为："+sb.charAt(i));
                break;
            }
        }
    }
    static void test(){
        Random r = new Random();
        //随机生成5个数用来测试
        for(int i=0;i<3;i++){
            //随机生成范围[0,999)
            int t=r.nextInt(999);
            System.out.println("输入的数为： " + t);
            StringBuffer sb = toBinary(t);
            System.out.println("编码后为：" + sb);
            calculate(sb);
            System.out.println("计算结果为：" + sb);
            //将末尾的逗号去掉
            sb.delete(sb.length()-2, sb.length());
            //把扩展二进制编码的10替换成为1
            String s = sb.toString().replace("10", "1");
            System.out.println("计算结果转换为二进制为：" + s);
            //Integer.parseInt(String s ,int radix)方法，以十进制输出radix进制数s
            System.out.println("计算结果转换为十进制为："+Integer.parseInt(s, 2));
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        sc.close();
        StringBuffer sb = toBinary(num);
        System.out.println("编码后为：" + sb);
        calculate(sb);
        System.out.println("计算结果为：" + sb);
        //将末尾的逗号去掉
        sb.delete(sb.length()-3, sb.length());
        //把扩展二进制编码的10替换成为1
        String s = sb.toString().replace("10", "1");
        System.out.println("计算结果转换为二进制为：" + s);
        //Integer.parseInt(String s ,int radix)方法，以十进制输出radix进制数s
        System.out.println("计算结果转换为十进制为："+Integer.parseInt(s, 2));
//        //测试
//        test();
    }
}

三. 心得体会

​在程序设计过程中，我使用java进行编写，遇到的最主要的问题就是对于StringBuffer类的不熟悉，还有对Integer类的方法也很陌生，所以在转化扩展二进制编码和将字符串转换为整数的时候停了下来，最后通过查阅资料，我知道了相关方法的用法，解决了这个问题。

​在这次完成作业的过程中，突出了我知识匮乏的缺点，对于一些常用的类型方法知之甚少，今后我会增强这方面的练习。