程序设计方法与优化第四次作业

第二章 图灵机
一、题目分析
题目的要求是编程模拟任意给定的一台图灵机的运行过程，图灵机实质上是一连串的设计好的指令，满足某个指令的调用要求，便调用该指令完成相关操作，理解了这一点问题便容易解决。
二、算法构造
在此论证算法设计中的一些必要的设计依据。
图灵机的指令可以运用if-switc-case语句进行实现，if语句用于判断内态，switch-case语句读取磁带上的二进制数，并进行相关操作，每运行一条指令，输出结果。
三、算法实现
package package1;
import java.util.Scanner;
import java.util.*;
public class Example {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int m;//定义一个整形变量保存输入的正整数
System.out.println(“请输入一个正整数:”);
m=sc.nextInt();
System.out.println(“输入的数为:”+m);//输出输入的数
System.out.println(“将该数转换为二进制的结果:”+Integer.toBinaryString(m));//输出该数转换为二进制的结果
String str1=Integer.toBinaryString(m);//定义一个字符串变量保存二进制数
System.out.println(“二进制转换为扩展二进位:”+“00”+str1.replace(“1”,“10”)+“1100”);//输出扩展二进位
String str=“00”+str1.replace(“1”,“10”)+“1100”;//定义一个字符串变量保存扩展二进位
char[] arr=str.toCharArray();//定义字符数组保存扩展二进位
int sign=0;//定义内态
for(int i=0;i<arr.length;i++)
{
if(sign0)//内态为0时
{
switch(arr[i])
{
case ‘0’:break;
case ‘1’:sign=1;break;
default:System.out.println(“data error!”);
}
for(int j=0;j<arr.length;j++)//输出结果
System.out.printf("%c “,arr[j]);
System.out.printf(”\n");
}
else if(sign1)//内态为1时
{
switch(arr[i])
{
case ‘0’:sign=0;break;
case ‘1’:sign=10;break;
default:System.out.println(“data error!”);
}
for(int j=0;j<arr.length;j++)//输出结果
System.out.printf("%c “,arr[j]);
System.out.printf(”\n");
}
else if(sign10)//内态为10时
{
switch(arr[i])
{
case ‘0’:sign=11;i-=2;break;
case ‘1’:break;
default:System.out.println(“data error!”);
}
for(int j=0;j<arr.length;j++)//输出结果
System.out.printf("%c “,arr[j]);
System.out.printf(”\n");
}
else if(sign11)//内态为11时
{
if(arr[i]‘0’)
{
sign=0;
arr[i]=‘1’;
break;
}
else if(arr[i]‘1’)
{
sign=100;
arr[i]=‘0’;
i-=2;
}
for(int j=0;j<arr.length;j++)//输出结果
System.out.printf("%c “,arr[j]);
System.out.printf(”\n");
}
else if(sign100)//内态为100时
{
switch(arr[i])
{
case ‘0’:sign=101;arr[i]=‘1’;i-=2;break;
case ‘1’:i-=2;break;
}
for(int j=0;j<arr.length;j++)//输出结果
System.out.printf("%c “,arr[j]);
System.out.printf(”\n");
}
else if(sign101)//内态为101时
{
switch(arr[i])
{
case ‘0’:sign=110;break;
case ‘1’:sign=10;break;
}
for(int j=0;j<arr.length;j++)//输出结果
System.out.printf("%c “,arr[j]);
System.out.printf(”\n");
}
else if(sign110&&arr[i]‘1’)//内态为110且读取到1时
{
sign=111;
for(int j=0;j<arr.length;j++)//输出结果
System.out.printf("%c “,arr[j]);
System.out.printf(”\n");
}
else if(sign==111)//内态为111时
{
switch(arr[i])
{
case ‘0’:sign=11;arr[i]=‘1’;break;
case ‘1’:arr[i]=‘0’;break;
}
}
}
for(int j=0;j<arr.length;j++)//输出结果
System.out.printf("%c “,arr[j]);
String str2=new String(arr);
if(str2.contains(“110”)==true)//如果扩展二进位中包含110字符串则把110以及后面的字符串全部删除
str2 = str2.replace(str2.substring(str2.lastIndexOf(“110”),str2.length()),”");
System.out.println("\n将扩展二进位转换为普通二进位的结果:"+str2.replace(“10”,“1”));//将扩展二进位转换为普通二进位
String str3=str2.replace(“10”,“1”);
char[] arr2=str3.toCharArray();//定义字符数组保存二进位
int sum=0;//定义sum进行十进制计数
for(int i=0;i<arr2.length;i++){
sum=sum+(int)(Math.pow(2, arr2.length-i-1))*Integer.parseInt(arr2[i]+"");//另外一种方法将二进制转换为十进制
}//计算十进制结果
sum=Integer.parseInt(str3,2);//调用包装类的parseInt方法直接将二进制数转换为十进制数
System.out.println(“将二进制转换为十进制的结果:”+sum);//输出转换后的十进制数结果
sc.close();//关闭输入流
}
}

四、调试、测试及运行结果
运行界面：

一开始输入1发现提示错误：

错误提示为数组指针越界，经检查是将二进位扩展为扩展二进位后没有在字符串前加足够的0来应对有些指令会令读取的位置左移。修改后：
String str=“00”+str1.replace(“1”,“10”)+“1100”;//定义一个字符串变量保存扩展二进位
输入、程序运行以及输出结果：

结果正确!
五、经验归纳
不得不说图灵的思想是如此的超前，经过这次的作业，我加深了对计算机内部工作原理的理解，在求解如何将扩展二进位转换为十进制数并输出的过程中，更是进一步加深了我对java中String类及包装类的理解及运用，同时我还设计了另外一种求解的方法，更可谓拓宽了思维，学习编程和解决数学题很像，会多种不同的解决思路才能应对各种各样的问题。