如何用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時執行指令1case 0: instruction_1(binCodeList.get(i), i, binCodeList); break;// 內態為1時執行指令2case 1: instruction_2(binCodeList.get(i), i, binCodeList); break;// 內態為10時執行指令3case 10: instruction_3(binCodeList.get(i), i, binCodeList); break;// 內態為11時執行指令4case 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的實例tmSystem.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中的字符進行遍歷，根據其中的每個字符得出二進制編碼binCodefor (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進行遍歷，根據其中的每個元素得出二進制編碼binCodefor (int i = 0; i < binCode.length(); i++) { // 0 -> 0 if (binCode.charAt(i) == ’0’) {binNum += '0'; } else if (binCode.charAt(i) == ’1’) {// 10 -> 1if (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內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！