App下載

使用Java模擬XN*2圖靈機(jī) 附實(shí)例代碼詳解

猿友 2021-08-04 11:28:37 瀏覽數(shù) (2366)
反饋

本篇文章主要介紹了如何使用 Java 來模擬 XN*2 圖靈機(jī),下面是具體的實(shí)現(xiàn)過程,供大家參考,希望對(duì)大家的學(xué)習(xí)和工作能夠有所幫助!

題目描述:

對(duì)于XN*2圖靈機(jī)進(jìn)行模擬,任意給定的十進(jìn)制數(shù),轉(zhuǎn)換為收縮擴(kuò)展二進(jìn)制的編碼,再編程模擬此Turing機(jī)的運(yùn)行過程,要求輸出從開始運(yùn)行起的每一步驟的結(jié)果。用C或C++或Java或Python語言實(shí)現(xiàn)程序解決問題。

要求:1. 程序風(fēng)格良好(使用自定義注釋模板);

2. 提供友好的輸入輸出,并進(jìn)行輸入數(shù)據(jù)的正確性驗(yàn)證。

算法分析:

1. 將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù);

2. 將二進(jìn)制數(shù)轉(zhuǎn)換為收縮擴(kuò)展二進(jìn)制的編碼;

3. 根據(jù)當(dāng)前的內(nèi)態(tài)和輸入執(zhí)行XN*2圖靈機(jī)的指令;

4. 將結(jié)果的二進(jìn)制編碼轉(zhuǎn)換為二進(jìn)制數(shù);

5. 將二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù),實(shí)現(xiàn)乘2運(yùn)算功能。

概要設(shè)計(jì):

算法流程圖如下:

202104121443057

測試:

輸入的十進(jìn)制數(shù)

正確的二進(jìn)制編碼

輸出的二進(jìn)制編碼

正確的運(yùn)算結(jié)果

輸出的運(yùn)算結(jié)果

0

0011000

0011000

0

0

3

0101011000

0101011000

6

6

18

0100010011000

0100010011000

36

36

運(yùn)行結(jié)果:

202104121443058

202104121443059

2021041214430510

調(diào)試:

①對(duì)調(diào)用指令的方法進(jìn)行調(diào)試,開始時(shí)binCodeList的size為0,導(dǎo)致執(zhí)行binCodeList.set(i, “0”)時(shí)出現(xiàn)錯(cuò)誤,進(jìn)過調(diào)試后發(fā)現(xiàn)是因?yàn)闆]給方法設(shè)置binCodeList的參數(shù),導(dǎo)致方法中用的是類中空的binCodeList。在方法的參數(shù)中加上List<String> binCodeList就可以解決。

2021041214430511

②對(duì)將二進(jìn)制編碼轉(zhuǎn)換為十進(jìn)制數(shù)的方法進(jìn)行調(diào)試,開始時(shí)運(yùn)算結(jié)果出現(xiàn)錯(cuò)誤,調(diào)試后發(fā)現(xiàn)是判斷第i個(gè)字符為1,第i+1個(gè)字符為0后,沒有將i再加1,導(dǎo)致下次循環(huán)又遍歷到i+1的0,于是有些步驟結(jié)果就會(huì)多出0。在if (binCode.charAt(i + 1) == '0'){…}代碼塊中加上i++就可以解決。

2021041214430512

源代碼:

import java.util.*; 
/**
 * @description: 該類模擬XN*2圖靈機(jī),對(duì)任意給定的十進(jìn)制數(shù),轉(zhuǎn)換為收縮擴(kuò)展二進(jìn)制的編碼,并可輸出運(yùn)行中每一步驟的結(jié)果
 */
public class TuringMachine {
 
    private int internalState; // 圖靈機(jī)的內(nèi)態(tài)
    private String binCode; // 二進(jìn)制編碼
    Function f = new Function(); // 需要用到的方法
    List<String> binCodeList = new ArrayList<>(); // 用來存放二進(jìn)制編碼
 
    static int r = 0; // 當(dāng)r為1時(shí)機(jī)器向右移動(dòng)一格
    static int s = 0; // 當(dāng)s為1時(shí)機(jī)器停止運(yùn)行
 
    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: 模擬圖靈機(jī)的運(yùn)行過程
     * @param: [binCode 二進(jìn)制編碼]
     * @return: void
     */
    public void runProcess(String binCode) {
        binCodeList = f.toArrayList(binCode); // 將二進(jìn)制碼binCode轉(zhuǎn)換為ArrayList類型存放在binCodeList中
        // for循環(huán)對(duì)binCodeList進(jìn)行遍歷,根據(jù)當(dāng)前內(nèi)態(tài)的值判斷該執(zhí)行哪條指令
        for (int i = 0; i < binCodeList.size(); i++) {
            r = 1;
            // 當(dāng)s==1時(shí)機(jī)器停止,跳出循環(huán)
            if (s == 1) {
                break;
            }
            switch (getInternalState()) {
                // 內(nèi)態(tài)為0時(shí)執(zhí)行指令1
                case 0:
                    instruction_1(binCodeList.get(i), i, binCodeList);
                    break;
                // 內(nèi)態(tài)為1時(shí)執(zhí)行指令2
                case 1:
                    instruction_2(binCodeList.get(i), i, binCodeList);
                    break;
                // 內(nèi)態(tài)為10時(shí)執(zhí)行指令3
                case 10:
                    instruction_3(binCodeList.get(i), i, binCodeList);
                    break;
                // 內(nèi)態(tài)為11時(shí)執(zhí)行指令4
                case 11:
                    instruction_4(binCodeList.get(i), i, binCodeList);
                    break;
                default:
                    break;
            }
        }
        System.out.println("XN*2圖靈機(jī)計(jì)算的最終結(jié)果為:");
        f.toDecNum(f.toString(binCodeList)); // 將binCodeList轉(zhuǎn)換為String類型的二進(jìn)制編碼binCode,再轉(zhuǎn)換為int類型的十進(jìn)制數(shù)decNum
    } 
    /**
     * @description: 根據(jù)指令對(duì)每一步驟結(jié)果進(jìn)行打印
     * 指令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 循環(huán)的次數(shù)從0開始, binCodeList 存放二進(jìn)制編碼binCode]
     * @return: void
     */
    private void instruction_1(String input, int i, List<String> binCodeList) {
        System.out.println("當(dāng)前的內(nèi)態(tài)為:" + getInternalState() + ",輸入為:" + input);
        if (input.equals("0")) {
            System.out.println("執(zhí)行此條指令后的內(nèi)態(tài)為:" + getInternalState() + ",輸入為:" + binCodeList.get(i) + ",右移");
            System.out.println("此步驟的結(jié)果為:");
            System.out.println(f.toString(binCodeList));
        }
        if (input.equals("1")) {
            setInternalState(1);
            binCodeList.set(i, "0");
            System.out.println("執(zhí)行此條指令后的內(nèi)態(tài)為:" + getInternalState() + ",輸入為:" + binCodeList.get(i) + ",右移");
            System.out.println("此步驟的結(jié)果為:");
            System.out.println(f.toString(binCodeList));
        }
        System.out.println();
    }
 
    private void instruction_2(String input, int i, List<String> binCodeList) {
        System.out.println("當(dāng)前的內(nèi)態(tài)為:" + getInternalState() + ",輸入為:" + input);
        if (input.equals("0")) {
            setInternalState(0);
            binCodeList.set(i, "1");
            System.out.println("執(zhí)行此條指令后的內(nèi)態(tài)為:" + getInternalState() + ",輸入為:" + binCodeList.get(i) + ",右移");
            System.out.println("此步驟的結(jié)果為:");
            System.out.println(f.toString(binCodeList));
        }
        if (input.equals("1")) {
            setInternalState(10);
            binCodeList.set(i, "0");
            System.out.println("執(zhí)行此條指令后的內(nèi)態(tài)為:" + getInternalState() + ",輸入為:" + binCodeList.get(i) + ",右移");
            System.out.println("此步驟的結(jié)果為:");
            System.out.println(f.toString(binCodeList));
        }
        System.out.println();
    }
 
    private void instruction_3(String input, int i, List<String> binCodeList) {
        System.out.println("當(dāng)前的內(nèi)態(tài)為:" + getInternalState() + ",輸入為:" + input);
        if (input.equals("0")) {
            setInternalState(11);
            binCodeList.set(i, "1");
            System.out.println("執(zhí)行此條指令后的內(nèi)態(tài)為:" + getInternalState() + ",輸入為:" + binCodeList.get(i) + ",右移");
            System.out.println("此步驟的結(jié)果為:");
            System.out.println(f.toString(binCodeList));
        }
        System.out.println();
    }
 
    private void instruction_4(String input, int i, List<String> binCodeList) {
        System.out.println("當(dāng)前的內(nèi)態(tài)為:" + getInternalState() + ",輸入為:" + input);
        if (input.equals("0")) {
            setInternalState(0);
            binCodeList.set(i, "1");
            System.out.println("執(zhí)行此條指令后的內(nèi)態(tài)為:" + getInternalState() + ",輸入為:" + binCodeList.get(i) + ",STOP");
            System.out.println("此步驟的結(jié)果為:");
            System.out.println(f.toString(binCodeList));
        }
        s = 1;
        System.out.println();
    }
 
    public static void main(String[] args) {
        TuringMachine tm = new TuringMachine(); // 創(chuàng)建TuringMachine的實(shí)例tm
        System.out.println("請(qǐng)輸入一個(gè)十進(jìn)制數(shù):");
        Scanner scanner = new Scanner(System.in);
        try {
            int decNum = scanner.nextInt();
            tm.setBinCode(tm.f.toBinCode(decNum)); // 將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制編碼并賦值給binCode
            System.out.println();
            tm.runProcess(tm.getBinCode()); // 運(yùn)行圖靈機(jī)
        } catch (InputMismatchException ex) {
            System.out.println("輸入有誤!");
        }
    } 
}
 
/**
 * @description: 該類具有圖靈機(jī)TuringMachine運(yùn)行過程中所需要的一些方法
 */
class Function {
 
    /**
     * @description: 將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制編碼
     * @param: [decNum 十進(jìn)制數(shù)]
     * @return: java.lang.String
     */
    public String toBinCode(int decNum) {
        String binCode = "";
        String binNum = Integer.toBinaryString(decNum); // 十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)
        binNum += ","; // 用,標(biāo)識(shí)此二進(jìn)制數(shù)到此已完整,后面的0都忽略不計(jì)
        System.out.println("這個(gè)數(shù)的二進(jìn)制表示為:" + binNum);
        // 利用for循環(huán)對(duì)二進(jìn)制數(shù)binNum中的字符進(jìn)行遍歷,根據(jù)其中的每個(gè)字符得出二進(jìn)制編碼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("這個(gè)數(shù)的二進(jìn)制編碼為:" + binCode);
        return binCode;
    }
 
    /**
     * @description: 將二進(jìn)制編碼轉(zhuǎn)換為十進(jìn)制數(shù)
     * @param: [binCode 二進(jìn)制編碼]
     * @return: int
     */
    public int toDecNum(String binCode) {
        int decNum = 0;
        String binNum = "";
        // 先利用for循環(huán)對(duì)ArrayList類型的binCode進(jìn)行遍歷,根據(jù)其中的每個(gè)元素得出二進(jìn)制編碼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("二進(jìn)制表示:" + binNum);
        decNum = Integer.parseInt(binNum.substring(0, binNum.length() - 1), 2); // 將二進(jìn)制編碼binCode轉(zhuǎn)化為十進(jìn)制數(shù)
        System.out.println("十進(jìn)制表示:" + decNum);
        return decNum;
    }
 
    /**
     * @description: 將二進(jìn)制編碼binCode存放到binCodeList中
     * @param: [binCode 二進(jìn)制編碼]
     * @return: java.util.List<java.lang.String>
     */
    public List<String> toArrayList(String binCode) {
        binCode = binCode.replaceAll("", " ").trim(); // 將binCode中的每個(gè)字符用空格分隔開,并去掉首尾的空格
        // 根據(jù)分隔符空格分隔出binCode中的每個(gè)字符存放到binCodeList中
        List<String> binCodeList = new ArrayList<>(Arrays.asList(binCode.split(" ")));
        return binCodeList;
    }
 
    /**
     * @description: 將binCodeList轉(zhuǎn)換為二進(jìn)制編碼binCode
     * @param: [binCodeList 存放binCode的容器]
     * @return: java.lang.String
     */
    public String toString(List<String> binCodeList) {
        String binCode = String.join("", binCodeList);
        return binCode;
    } 
}

總結(jié)

本次測試是模擬圖靈機(jī)對(duì)十進(jìn)制數(shù)進(jìn)行乘2運(yùn)算,并輸出每一步驟的結(jié)果。

本次測試的關(guān)鍵問題在于圖靈機(jī)運(yùn)行過程和算法的理解,圖靈機(jī)判斷當(dāng)前內(nèi)態(tài)和輸入后執(zhí)行指令,在這里我才用switch語句根據(jù)內(nèi)態(tài)的值判斷執(zhí)行哪個(gè)指令方法,再根據(jù)輸入判斷具體執(zhí)行什么指令,通過for循環(huán)模擬右移操作。

到此這篇關(guān)于如何用Java模擬XN*2圖靈機(jī)的文章就介紹到這了,想要了解更多相關(guān)Java內(nèi)容,請(qǐng)搜索W3Cschool以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持!?


0 人點(diǎn)贊