如何用Java模擬XN*2圖靈機(jī)
更新時間：2021年04月12日 17:11:59 作者：KitchenSink
這篇文章主要介紹了如何用Java模擬XN*2圖靈機(jī)方法,感興趣的朋友可以參考下
題目描述：
對于XN*2圖靈機(jī)進(jìn)行模擬，任意給定的十進(jìn)制數(shù)，轉(zhuǎn)換為收縮擴(kuò)展二進(jìn)制的編碼，再編程模擬此Turing機(jī)的運行過程，要求輸出從開始運行起的每一步驟的結(jié)果。用C或C++或Java或Python語言實現(xiàn)程序解決問題。
要求：1. 程序風(fēng)格良好（使用自定義注釋模板）；
2. 提供友好的輸入輸出，并進(jìn)行輸入數(shù)據(jù)的正確性驗證。
算法分析：
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ù)，實現(xiàn)乘2運算功能。
概要設(shè)計：
算法流程圖如下：
測試：
|
輸入的十進(jìn)制數(shù) |
正確的二進(jìn)制編碼 |
輸出的二進(jìn)制編碼 |
正確的運算結(jié)果 |
輸出的運算結(jié)果 |
|
0 |
0011000 |
0011000 |
0 |
0 |
|
3 |
0101011000 |
0101011000 |
6 |
6 |
|
18 |
0100010011000 |
0100010011000 |
36 |
36 |
運行結(jié)果：
調(diào)試：
①對調(diào)用指令的方法進(jìn)行調(diào)試，開始時binCodeList的size為0，導(dǎo)致執(zhí)行binCodeList.set(i, “0”)時出現(xiàn)錯誤，進(jìn)過調(diào)試后發(fā)現(xiàn)是因為沒給方法設(shè)置binCodeList的參數(shù)，導(dǎo)致方法中用的是類中空的binCodeList。在方法的參數(shù)中加上List<String> binCodeList就可以解決。
②對將二進(jìn)制編碼轉(zhuǎn)換為十進(jìn)制數(shù)的方法進(jìn)行調(diào)試，開始時運算結(jié)果出現(xiàn)錯誤，調(diào)試后發(fā)現(xiàn)是判斷第i個字符為1，第i+1個字符為0后，沒有將i再加1，導(dǎo)致下次循環(huán)又遍歷到i+1的0，于是有些步驟結(jié)果就會多出0。在if (binCode.charAt(i + 1) == '0'){…}代碼塊中加上i++就可以解決。
源代碼：
import java.util.*;
/**
* @description: 該類模擬XN*2圖靈機(jī)，對任意給定的十進(jìn)制數(shù)，轉(zhuǎn)換為收縮擴(kuò)展二進(jì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時機(jī)器向右移動一格
static int s = 0; // 當(dāng)s為1時機(jī)器停止運行
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ī)的運行過程
* @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)對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時機(jī)器停止，跳出循環(huán)
if (s == 1) {
break;
}
switch (getInternalState()) {
// 內(nèi)態(tài)為0時執(zhí)行指令1
case 0:
instruction_1(binCodeList.get(i), i, binCodeList);
break;
// 內(nèi)態(tài)為1時執(zhí)行指令2
case 1:
instruction_2(binCodeList.get(i), i, binCodeList);
break;
// 內(nèi)態(tài)為10時執(zhí)行指令3
case 10:
instruction_3(binCodeList.get(i), i, binCodeList);
break;
// 內(nèi)態(tài)為11時執(zhí)行指令4
case 11:
instruction_4(binCodeList.get(i), i, binCodeList);
break;
default:
break;
}
}
System.out.println("XN*2圖靈機(jī)計算的最終結(jié)果為：");
f.toDecNum(f.toString(binCodeList)); // 將binCodeList轉(zhuǎn)換為String類型的二進(jìn)制編碼binCode，再轉(zhuǎn)換為int類型的十進(jìn)制數(shù)decNum
}
/**
* @description: 根據(jù)指令對每一步驟結(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的實例tm
System.out.println("請輸入一個十進(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()); // 運行圖靈機(jī)
} catch (InputMismatchException ex) {
System.out.println("輸入有誤！");
}
}
}
/**
* @description: 該類具有圖靈機(jī)TuringMachine運行過程中所需要的一些方法
*/
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)識此二進(jìn)制數(shù)到此已完整，后面的0都忽略不計
System.out.println("這個數(shù)的二進(jìn)制表示為：" + binNum);
// 利用for循環(huán)對二進(jìn)制數(shù)binNum中的字符進(jìn)行遍歷，根據(jù)其中的每個字符得出二進(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("這個數(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)對ArrayList類型的binCode進(jìn)行遍歷，根據(jù)其中的每個元素得出二進(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中的每個字符用空格分隔開，并去掉首尾的空格
// 根據(jù)分隔符空格分隔出binCode中的每個字符存放到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ī)對十進(jìn)制數(shù)進(jìn)行乘2運算，并輸出每一步驟的結(jié)果。
本次測試的關(guān)鍵問題在于圖靈機(jī)運行過程和算法的理解，圖靈機(jī)判斷當(dāng)前內(nèi)態(tài)和輸入后執(zhí)行指令，在這里我才用switch語句根據(jù)內(nèi)態(tài)的值判斷執(zhí)行哪個指令方法，再根據(jù)輸入判斷具體執(zhí)行什么指令，通過for循環(huán)模擬右移操作。到此這篇關(guān)于如何用Java模擬XN*2圖靈機(jī)的文章就介紹到這了,更多相關(guān)Java內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在本篇文章里小編給大家整理的是一篇關(guān)于java類實現(xiàn)日期的時間差的實例講解內(nèi)容，有興趣的朋友們可以學(xué)習(xí)下。2021-01-01
ArrayList源碼探秘之Java動態(tài)數(shù)組的實現(xiàn)
這篇文章將帶大家從ArrayList源碼來探秘一下Java動態(tài)數(shù)組的實現(xiàn)，文中的示例代碼講解詳細(xì)，對我們深入了解JavaScript有一定的幫助，需要的可以參考一下2023-08-08
在獲取update操作的返回值時遇到了一個問題，似乎 Mybatis 進(jìn)行 update 操作得到的 int 返回值并不是影響的行數(shù)，下面通過本文給大家分享Mybatis Update操作返回值問題，需要的朋友參考下吧2017-09-09
這篇文章主要介紹了Java規(guī)則引擎Easy Rules的使用介紹，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06
本篇文章主要介紹了springMVC攔截器和過濾器總結(jié)，可以用來對訪問的url進(jìn)行攔截處理，有興趣的可以了解一下。2017-01-01
Spring Security+Spring Data Jpa如何進(jìn)行安全管理
這篇文章主要介紹了Spring Security+Spring Data Jpa如何進(jìn)行安全管理，幫助大家更好的理解和學(xué)習(xí)Spring Security框架，感興趣的朋友可以了解下2020-09-09
這篇文章主要給大家介紹了關(guān)于java監(jiān)聽器實現(xiàn)和原理的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用java具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
Java實現(xiàn)Excel轉(zhuǎn)PDF的兩種方法詳解
使用具將Excel轉(zhuǎn)為PDF的方法有很多，在這里我給大家介紹兩種常用的方法：使用spire轉(zhuǎn)化PDF、使用jacob實現(xiàn)Excel轉(zhuǎn)PDF，分別應(yīng)對兩種不一樣的使用場景，需要的可以參考一下2022-01-01
這篇文章主要介紹了SpringBoot實體多層嵌套如何判空字段,最近在公司了接了個需求：需要開發(fā)一個中間系統(tǒng),進(jìn)行三方聯(lián)調(diào),文中通過代碼示例介紹的非常詳細(xì),需要的朋友可以參考下2024-09-09
在做項目中，只要涉及敏感信息，或者對安全有一定要求的場景，都需要對數(shù)據(jù)進(jìn)行加密。接下來通過本文給大家分享Java?加密解密和數(shù)字簽名問題，感興趣的朋友跟隨小編一起看看吧2021-12-12