如何用Java模拟XN*2图灵机

题目描述:

对于XN*2图灵机进行模拟,任意给定的十进制数,转换为收缩扩展二进制的编码,再编程模拟此Turing机的运行过程,要求输出从开始运行起的每一步骤的结果。用C或C++或Java或Python语言实现程序解决问题。

要求:1. 程序风格良好(使用自定义注释模板);

2. 提供友好的输入输出,并进行输入数据的正确性验证。

算法分析:

1. 将十进制数转换为二进制数;

2. 将二进制数转换为收缩扩展二进制的编码;

3. 根据当前的内态和输入执行XN*2图灵机的指令;

4. 将结果的二进制编码转换为二进制数;

5. 将二进制数转换为十进制数,实现乘2运算功能。

概要设计:

算法流程图如下:

测试:


输入的十进制数


正确的二进制编码


输出的二进制编码


正确的运算结果


输出的运算结果


0


0011000


0011000


0


0


3


0101011000


0101011000


6


6


18


0100010011000


0100010011000


36


36

运行结果:

调试:

①对调用指令的方法进行调试,开始时binCodeList的size为0,导致执行binCodeList.set(i, “0”)时出现错误,进过调试后发现是因为没给方法设置binCodeList的参数,导致方法中用的是类中空的binCodeList。在方法的参数中加上List<String> binCodeList就可以解决。

②对将二进制编码转换为十进制数的方法进行调试,开始时运算结果出现错误,调试后发现是判断第i个字符为1,第i+1个字符为0后,没有将i再加1,导致下次循环又遍历到i+1的0,于是有些步骤结果就会多出0。在if (binCode.charAt(i + 1) == '0'){…}代码块中加上i++就可以解决。

源代码:

import java.util.*;
/**
 * @description: 该类模拟XN*2图灵机,对任意给定的十进制数,转换为收缩扩展二进制的编码,并可输出运行中每一步骤的结果
 */
public class TuringMachine {

    private int internalState; // 图灵机的内态
    private String binCode; // 二进制编码
    Function f = new Function(); // 需要用到的方法
    List<String> binCodeList = new ArrayList<>(); // 用来存放二进制编码

    static int r = 0; // 当r为1时机器向右移动一格
    static int s = 0; // 当s为1时机器停止运行

    TuringMachine() {
        internalState = 0;
        binCode = "0";
    }

    public int getInternalState() {
        return internalState;
    }

    public void setInternalState(int internalState) {
        this.internalState = internalState;
    }

    public String getBinCode() {
        return binCode;
    }

    public void setBinCode(String binCode) {
        this.binCode = binCode;
    }

    /**
     * @description: 模拟图灵机的运行过程
     * @param: [binCode 二进制编码]
     * @return: void
     */
    public void runProcess(String binCode) {
        binCodeList = f.toArrayList(binCode); // 将二进制码binCode转换为ArrayList类型存放在binCodeList中
        // for循环对binCodeList进行遍历,根据当前内态的值判断该执行哪条指令
        for (int i = 0; i < binCodeList.size(); i++) {
            r = 1;
            // 当s==1时机器停止,跳出循环
            if (s == 1) {
                break;
            }
            switch (getInternalState()) {
                // 内态为0时执行指令1
                case 0:
                    instruction_1(binCodeList.get(i), i, binCodeList);
                    break;
                // 内态为1时执行指令2
                case 1:
                    instruction_2(binCodeList.get(i), i, binCodeList);
                    break;
                // 内态为10时执行指令3
                case 10:
                    instruction_3(binCodeList.get(i), i, binCodeList);
                    break;
                // 内态为11时执行指令4
                case 11:
                    instruction_4(binCodeList.get(i), i, binCodeList);
                    break;
                default:
                    break;
            }
        }
        System.out.println("XN*2图灵机计算的最终结果为:");
        f.toDecNum(f.toString(binCodeList)); // 将binCodeList转换为String类型的二进制编码binCode,再转换为int类型的十进制数decNum
    }
    /**
     * @description: 根据指令对每一步骤结果进行打印
     * 指令1: 0 0 -> 0 0 R
     * 0 1 -> 1 0 R
     * 指令2: 1 0 -> 0 1 R
     * 1 1 -> 10 0 R
     * 指令3: 10 0 -> 11 1 R
     * 指令4: 11 0 -> 0 1 STOP
     * @param: [input 输入, i 循环的次数从0开始, binCodeList 存放二进制编码binCode]
     * @return: void
     */
    private void instruction_1(String input, int i, List<String> binCodeList) {
        System.out.println("当前的内态为:" + getInternalState() + ",输入为:" + input);
        if (input.equals("0")) {
            System.out.println("执行此条指令后的内态为:" + getInternalState() + ",输入为:" + binCodeList.get(i) + ",右移");
            System.out.println("此步骤的结果为:");
            System.out.println(f.toString(binCodeList));
        }
        if (input.equals("1")) {
            setInternalState(1);
            binCodeList.set(i, "0");
            System.out.println("执行此条指令后的内态为:" + getInternalState() + ",输入为:" + binCodeList.get(i) + ",右移");
            System.out.println("此步骤的结果为:");
            System.out.println(f.toString(binCodeList));
        }
        System.out.println();
    }

    private void instruction_2(String input, int i, List<String> binCodeList) {
        System.out.println("当前的内态为:" + getInternalState() + ",输入为:" + input);
        if (input.equals("0")) {
            setInternalState(0);
            binCodeList.set(i, "1");
            System.out.println("执行此条指令后的内态为:" + getInternalState() + ",输入为:" + binCodeList.get(i) + ",右移");
            System.out.println("此步骤的结果为:");
            System.out.println(f.toString(binCodeList));
        }
        if (input.equals("1")) {
            setInternalState(10);
            binCodeList.set(i, "0");
            System.out.println("执行此条指令后的内态为:" + getInternalState() + ",输入为:" + binCodeList.get(i) + ",右移");
            System.out.println("此步骤的结果为:");
            System.out.println(f.toString(binCodeList));
        }
        System.out.println();
    }

    private void instruction_3(String input, int i, List<String> binCodeList) {
        System.out.println("当前的内态为:" + getInternalState() + ",输入为:" + input);
        if (input.equals("0")) {
            setInternalState(11);
            binCodeList.set(i, "1");
            System.out.println("执行此条指令后的内态为:" + getInternalState() + ",输入为:" + binCodeList.get(i) + ",右移");
            System.out.println("此步骤的结果为:");
            System.out.println(f.toString(binCodeList));
        }
        System.out.println();
    }

    private void instruction_4(String input, int i, List<String> binCodeList) {
        System.out.println("当前的内态为:" + getInternalState() + ",输入为:" + input);
        if (input.equals("0")) {
            setInternalState(0);
            binCodeList.set(i, "1");
            System.out.println("执行此条指令后的内态为:" + getInternalState() + ",输入为:" + binCodeList.get(i) + ",STOP");
            System.out.println("此步骤的结果为:");
            System.out.println(f.toString(binCodeList));
        }
        s = 1;
        System.out.println();
    }

    public static void main(String[] args) {
        TuringMachine tm = new TuringMachine(); // 创建TuringMachine的实例tm
        System.out.println("请输入一个十进制数:");
        Scanner scanner = new Scanner(System.in);
        try {
            int decNum = scanner.nextInt();
            tm.setBinCode(tm.f.toBinCode(decNum)); // 将十进制数转换为二进制编码并赋值给binCode
            System.out.println();
            tm.runProcess(tm.getBinCode()); // 运行图灵机
        } catch (InputMismatchException ex) {
            System.out.println("输入有误!");
        }
    }
}

/**
 * @description: 该类具有图灵机TuringMachine运行过程中所需要的一些方法
 */
class Function {

    /**
     * @description: 将十进制数转换为二进制编码
     * @param: [decNum 十进制数]
     * @return: java.lang.String
     */
    public String toBinCode(int decNum) {
        String binCode = "";
        String binNum = Integer.toBinaryString(decNum); // 十进制数转换为二进制数
        binNum += ","; // 用,标识此二进制数到此已完整,后面的0都忽略不计
        System.out.println("这个数的二进制表示为:" + binNum);
        // 利用for循环对二进制数binNum中的字符进行遍历,根据其中的每个字符得出二进制编码binCode
        for (int i = 0; i < binNum.length(); i++) {
            // 0 -> 0
            if (binNum.charAt(i) == '0') {
                binCode += "0";
                // 1 -> 10
            } else if (binNum.charAt(i) == '1') {
                binCode += "10";
                // , -> 110
            } else if (binNum.charAt(i) == ',') {
                binCode += "110";
            }
        }
        binCode = "0" + binCode + "00";
        System.out.println("这个数的二进制编码为:" + binCode);
        return binCode;
    }

    /**
     * @description: 将二进制编码转换为十进制数
     * @param: [binCode 二进制编码]
     * @return: int
     */
    public int toDecNum(String binCode) {
        int decNum = 0;
        String binNum = "";
        // 先利用for循环对ArrayList类型的binCode进行遍历,根据其中的每个元素得出二进制编码binCode
        for (int i = 0; i < binCode.length(); i++) {
            // 0 -> 0
            if (binCode.charAt(i) == '0') {
                binNum += "0";
            } else if (binCode.charAt(i) == '1') {
                // 10 -> 1
                if (binCode.charAt(i + 1) == '0') {
                    binNum += "1";
                    i++;
                    // 110 -> ,
                } else if (binCode.charAt(i + 1) == '1') {
                    binNum += ",";
                    break;
                }
            }
        }
        System.out.println("二进制表示:" + binNum);
        decNum = Integer.parseInt(binNum.substring(0, binNum.length() - 1), 2); // 将二进制编码binCode转化为十进制数
        System.out.println("十进制表示:" + decNum);
        return decNum;
    }

    /**
     * @description: 将二进制编码binCode存放到binCodeList中
     * @param: [binCode 二进制编码]
     * @return: java.util.List<java.lang.String>
     */
    public List<String> toArrayList(String binCode) {
        binCode = binCode.replaceAll("", " ").trim(); // 将binCode中的每个字符用空格分隔开,并去掉首尾的空格
        // 根据分隔符空格分隔出binCode中的每个字符存放到binCodeList中
        List<String> binCodeList = new ArrayList<>(Arrays.asList(binCode.split(" ")));
        return binCodeList;
    }

    /**
     * @description: 将binCodeList转换为二进制编码binCode
     * @param: [binCodeList 存放binCode的容器]
     * @return: java.lang.String
     */
    public String toString(List<String> binCodeList) {
        String binCode = String.join("", binCodeList);
        return binCode;
    }
}

总结

本次测试是模拟图灵机对十进制数进行乘2运算,并输出每一步骤的结果。

本次测试的关键问题在于图灵机运行过程和算法的理解,图灵机判断当前内态和输入后执行指令,在这里我才用switch语句根据内态的值判断执行哪个指令方法,再根据输入判断具体执行什么指令,通过for循环模拟右移操作。到此这篇关于如何用Java模拟XN*2图灵机的文章就介绍到这了,更多相关Java内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java 实现模拟用户登录的示例代码

    创建一个用户类类型的集合,手动输入用户库 主要是判定输入的用户名和密码是否与库中的匹配 做好区别是用户名输入错误还是密码输入错误的提示. 定义用户类 public class User{ String username; String keyword; public User(String username, String keyword) { this.username = username; this.keyword = keyword; } } 主程序 import java.util.A

  • Java多线程之简单模拟售票功能

    一.创建 二.完整代码 package com.ql; import lombok.SneakyThrows; import okhttp3.Call; import okhttp3.OkHttpClient; import okhttp3.Request; import okhttp3.Response; import java.io.IOException; public class Mythread extends Thread { public Mythread(String name)

  • 使用Java程序模拟实现新冠病毒传染效果

    简单介绍 2020年注定是不平凡的一年,新冠肺炎肆虐全球,传染性特别强,目前全球感人人数还在逐渐攀升,作为中华儿女特别感谢政府作出的努力,非常感谢并致敬医护人员,是他们的努力为我们创造安全的环境,向你们致敬! 模拟方案 以下是程序粗略的模拟病毒传染过程,具体方案如下: 首先需要构造一个200 * 200的格子界面有四种不同的颜色状态标记着程序执行的过程程序执行10次,初始化格子也就是0的时候,需要在整个格子最中心的100个格子标记为红色,剩余数据随机抽取四千(且不能重复)标记为黑色,其余没有标记

  • Java多线程模拟售票程序和线程安全问题

    Java中线程部分知识中,售票程序非常经典.程序中也有一些问题存在! 需求:模拟3个窗口同时在售100张票. 问题1:为什么100张票被卖出了300张票? 原因:因为tickets是非静态的,非静态的成员变量数据是在每个对象中都会维护一份数据的,三个线程对象就会有三份. 解决方案:把tickets票数共享出来给三个线程对象使用.使用static修饰. 问题2: 出现了线程安全问题 ? 线程安全问题的解决方案:sun提供了线程同步机制让我们解决这类问题的. java线程同步机制的方式: 方式一:同

  • JAVA模拟新增顺序表及单链表

    最近在回顾大学学的数据结构,这里给大家用java模拟顺序表和单链表的新增 1顺序表新增 /** * 顺序表 * * @author cjd * */ public class ArrayList { private Object[] elementData; // 底层是一个数组,目前还没有确定长度 private int size; // 不是数组分配了几个空间,而是元素的个数 public ArrayList() { this(4); } public ArrayList(int initi

  • java多线程之火车售票系统模拟实例

    1.前言 为了学习多线程共享与通信,我们模拟一个火车售票系统,假设有10张火车票,三个窗口(也就是三个线程)同时进行售票. 2.非同步代码 package com.tl.skyLine.thread; /** * Created by tl on 17/3/6. */ public class SellTicket { public static void main(String[] args) { TicketWindow tw = new TicketWindow(); Thread t1

  • Java多线程模拟电影售票过程

    用多线程模拟电影售票过程(Java实训) 实训目的: 多线程的实现.线程同步 实训要求: 总票数和售票窗口数由键盘输入,用每个线程处理一个窗口的售票. Test.java package program5; import java.util.Scanner; public class Test { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(S

  • 使用java一维数组模拟压栈弹栈

    思路 先进后出,优先解决压栈的问题,之后解决弹栈和main方法 功能 随时模拟压栈 随时模拟弹栈 防止异常和各种错误 随时可以遍历"栈"中存在的变量的方法,压栈弹栈栈帧清晰可见! 使用演示: 压栈: 栈满检测: 遍历栈内存和栈帧: 只要栈中有变量就会输出栈帧: 弹栈: 栈空检测:(没有变量,栈帧不输出!) 源码: import java.util.Scanner; public class MoveTest01 { //局部变量供栈方法的遍历数组使用 static int i; //创

  • 如何用Java模拟XN*2图灵机

    题目描述: 对于XN*2图灵机进行模拟,任意给定的十进制数,转换为收缩扩展二进制的编码,再编程模拟此Turing机的运行过程,要求输出从开始运行起的每一步骤的结果.用C或C++或Java或Python语言实现程序解决问题. 要求:1. 程序风格良好(使用自定义注释模板): 2. 提供友好的输入输出,并进行输入数据的正确性验证. 算法分析: 1. 将十进制数转换为二进制数: 2. 将二进制数转换为收缩扩展二进制的编码: 3. 根据当前的内态和输入执行XN*2图灵机的指令: 4. 将结果的二进制编码

  • Java模拟登录正方教务抓取成绩、课表、空教室

    本文实例为大家分享了Java模拟登录正方教务抓取成绩.课表.空教室等信息,供大家参考,具体内容如下 1.Jwgl.java package com.ican.yueban.jwgl; import java.io.IOException; import java.io.InputStream; import java.util.ArrayList; import java.util.List; import java.util.Scanner; import org.apache.http.Ht

  • 如何用Java 几分钟处理完 30 亿个数据(项目难题)

    目录 1. 场景说明 2. 模拟数据 3. 场景分析 4. 读取数据 5. 处理数据 5.1 思路一 完整代码 测试结果 5.2 思路二:分治法 初始化阻塞队列 生产者 消费者 1) 队列线程私有化 2) 多子线程分割字符串 3) 分割字符串算法 完整代码 测试结果 6. 遇到的问题 解决方法 1. 场景说明 现有一个 10G 文件的数据,里面包含了 18-70 之间的整数,分别表示 18-70 岁的人群数量统计.假设年龄范围分布均匀,分别表示系统中所有用户的年龄数,找出重复次数最多的那个数,现

  • Java模拟QQ桌面截图功能实现方法

    本文实例讲述了Java模拟QQ桌面截图功能实现方法.分享给大家供大家参考.具体如下: QQ的桌面截图功能非常方便,去年曾用Java模拟过一个,现整理出来. 本方法首先需要抓到屏幕的整个图象,将图象显示在一个JFrame中,再将JFrame全屏显示,这样就模拟出了一个桌面,Java也就可以获得鼠标的作用区域从而实现桌面中的小范围截屏. import javax.swing.*; import java.awt.*; import java.awt.event.ActionEvent; import

  • java模拟post请求发送json的例子

    java模拟post请求发送json,用两种方式实现,第一种是HttpURLConnection发送post请求,第二种是使用httpclient模拟post请求, 方法一: package main.utils; import java.io.*; import java.net.HttpURLConnection; import java.net.URL; public class HttpUtilTest { Log log = new Log(this.getClass());//初始化

  • Java 模拟银行自助终端系统

    一. 本系统模拟银行用户使用ATM机开户.查询.存款.取款功能,要求使用java语言编程实现. 说明: 1. 对于数据输入异常,可使用java异常处理机制进行处理. 2. 评分将以功能实现与代码规范性相结合的方式进行考核. 3. 如果对项目需求有疑问,可以随时以QQ留言方式联系我进行咨询. 4. 国庆放假期间,每天都有老师在公司值班,10月4日是我在公司值班,10月7日正常上班,欢迎大家到公司来做项目. 二. 项目功能要求: 项目开始运行显示主菜单为: 银行自助终端系统 ************

  • java模拟http的Get/Post请求,并设置ip与port代理的方法

    本文涉及3个基本点: 1.因为很多公司的内网都设有代理,浏览器通过ip与port上网,而java代码模拟http get方式同样需要外网代理: 2.Java实现http的Get/Post请求代码: 3.主要是设置HttpURLConnection请求头里面的属性 比如Cookie.User-Agent(浏览器类型)等等. 比如:http请求中添加Header conn.setRequestProperty("Authorization", authorization); 注:我就在网上

  • Java模拟HTTP Get Post请求 轻松实现校园BBS自动回帖

    本文实例为大家分享了Java模拟HTTP Get Post请求,校园BBS自动回帖功能,供大家参考,具体内容如下 设计思路 找到帖子链接的集合,最后面数字变化, 就可以得到不同的帖子 防止帖子发表会又被删了的情况, 进行判断帖子是否存在 遍历这个集合, 对每个链接做回帖的POST请求 重难点 Note: 回帖需要用户登录信息 一种是利用Cookie 另一种是进行模拟登录 本文采用前者 代码 代码比较简单,注意事项是找到自己的Cookie,赋给String yourCookeie就可以直接运行 主

  • java模拟cookie登陆操作

    在使用java访问URL时,如果该URL需要身份验证,那么就不能够直接访问,因为没有登陆.那么,如何解决这个问题呢? 方法是使用java模拟登陆,登陆后记录下cookie信息,在下次发起请求时时将cookie发送过去用以表明身份,这样就能够访问带有权限的URL了. 下面首先介绍使用java模拟登陆. // 连接地址(通过阅读html源代码获得,即为登陆表单提交的URL) String surl = "http://login.goodjobs.cn/index.php/action/UserLo

  • Java模拟新浪和腾讯自动登录并发送微博

    Java模拟新浪和腾讯自动登录并发送微博功能分享给大家,供大家参考,具体内容如下 1.准备工作 只是登录无需申请新浪和腾迅的开发者账号,如果需要发送微博功能,需要申请一个新浪和腾迅的开发者账号,并添加一个测试应用. 过程请参考官方帮助文档,申请地址:新浪:http://open.weibo.com    腾迅:http://dev.t.qq.com/ 我们需要的是App Key和App Secre及redirect_URI,源代码中已经包含了我申请的测试key,但由于限制直接用我的key你们的账

随机推荐