一.題目分析
題目要求：根據的圖靈機的工作原理求出任意一個數的二倍數
題目分析：先将該數字由十進制轉換成對應的二進制碼，然後進行擴充。然後根據圖靈機的工作原理對擴充二進制碼進行計算，然後進行收縮，最後将普通二進制碼轉換成十進制碼
二.算法構造
1.先将輸入的十進制轉換成對應的二進制碼
2.根據圖靈機的擴充規則将普通二進制代碼進行擴充
規則：0->0
1->10
,(逗号)->110
然後在倆段加上無限個0（為了友善計算，将存放擴充二進制代碼的第一個數組元素設定成0）
3.根據圖靈機的計算規則，将擴充後的二進制代碼進行計算
規則：内态 輸入 改變後的内态 輸出
0 0 -> 0 0 右移
0 1 -> 1 0 右移
1 0 -> 0 1 右移
1 1 -> 10 1 右移
10 0 -> 11 1 右移
11 0 -> 0 1 停機
4.将擴充後的二進制碼進行收縮，從數組的第一位開始比較，如果第一位數組元素的值與相鄰的數組元素值相等，那麼隻可能是00的情況了，将收縮的數組元素指派為0，i++，下個元素與相鄰的元素再進行比較。如果不相等就是10或01的情況，将收縮後的數組元素指派為1，i=i+2，然後第i個數組元素再與相鄰的元素進行比較。
5.将收縮後的二進制代碼轉換成十進制，輸出
三.算法實作
程式源代碼:
package turing1;
import java.util.Scanner;//導包
public class Turing1 {
public static void main(String[] args)
{
int[] farray= new int[15];//用來存放擴充前的二進制碼
int[] sarray= new int[30];//用來存放擴充後的二進制碼
int[] tarray= new int[15];//用來存放收縮後的二進制碼
Scanner sc=new Scanner(System.in);//建立鍵盤錄入對象
System.out.println(“請輸入要計算的數字”);
int input=sc.nextInt();
//将十進制的數先轉換成二進制數，然後轉換成擴充後的二進制碼
int flength=CreatBinary(input,farray,sarray);
//根據圖靈機的轉換規則，将擴充後的二進制碼進行計算
int tlength=Stransform(flength,sarray);
//将擴充後的二進制碼轉換成普通的二進制碼，然後轉換成十進制碼
Shrink(tlength,sarray,tarray);
}
//将十進制的數先轉換成二進制數，然後轉換成擴充後的二進制碼
public static int CreatBinary(int input,int farray[],int sarray[])
{
int i=0;//用來存放二進制碼的長度
//将十進制數轉換成二進制數
while(input!=0)
{
farray[i]=input%2;//通過取餘和整除的方法求出二進制碼
input/=2;
i++;
}
for(int j=0;j<i/2;j++)//将二進制碼逆序排列
{
int temp=farray[j];
farray[j]=farray[i-j-1];
farray[i-j-1]=temp;
}
//将二進制碼進行擴充
int k=1;//從下标為1的數組開始計算，下标為0數組的設定為0
for(int j=0;j<i;j++)
{
//擴充規則：0->0,1->10,逗号->110
if(farray[j]==1)
{
sarray[k]=1;
sarray[k+1]=0;
k+=2;
}
else
{
k++;
}
}
sarray[k]=1;
sarray[k+1]=1;
sarray[k+2]=0;
k+=3;
System.out.print("這個數字的擴充二進碼是:");
for(int j=0;j<k;j++)
System.out.print(sarray[j]);
System.out.println(" ");
return k;
}
//根據圖靈機的轉換規則，将擴充後的二進制碼進行計算
public static int Stransform(int k,int sarray[])
{int flag=0;//表示圖靈機的内态
for(int j=0;j<=k;j++)//圖靈機的轉換規則
{
if(flag==0&&sarray[j]==0)//0 0 -> 0 0 R
{
sarray[j]=0;
System.out.println("内态由 0 變成 0，輸入為 0 ，輸出為 0 ，右移");
}
else if(flag==0&&sarray[j]==1)//0 1-> 1 0 R
{
sarray[j]=0;
flag=1;
System.out.println("内态由 0 變成 1，輸入為 1，輸出為 0，右移");
}
else if(flag==1&&sarray[j]==0)// 1 0 -> 0 1 R
{
sarray[j]=1;
flag=0;
System.out.println("内态由 1 變成 0，輸入為 0 ，輸出為 1，右移");
}
else if(flag==1&&sarray[j]==1)// 1 1-> 10 0 R
{
flag=10;
sarray[j]=0;
System.out.println("内态由 1 變成 10，輸入為 1 ，輸出為 0 ，右移");
}
else if(flag==10&&sarray[j]==0)// 10 0 -> 11 1 R
{
flag=11;
sarray[j]=1;
System.out.println("内态由 10 變成11，輸入為 0 ，輸出為 1 ，右移");
}
else// 11 0 -> 0 1 STOP
{
flag=0;
sarray[j]=1;
System.out.println("内态由 11 變成 0，輸入為 0 ，輸出為 1 ，停機");
break;
}
}
System.out.print("計算以後的擴充二進碼為:");
k+=2;
for(int j=0;j<k;j++)
System.out.print(sarray[j]);
return k;
}
//将擴充後的二進制碼轉換成普通的二進制碼，然後轉換成十進制
public static void Shrink(int k,int sarray[],int tarray[])
{
int m=0,n=0;
while(m<k-4)//由于最後三位是110，表示逗号，是以不考慮
{
if(sarray[m]==sarray[m+1])//如果相鄰的倆個數相等，一定是00的情況
{
tarray[n]=0;//對應普通的二進制碼就是0
n++;
m++;
}
else//如果相鄰的倆個數不想等，一定時10或01的情況
{
tarray[n]=1;//對應的普通二進制碼就是1
n++;
m=m+2;
}
}
System.out.println(" ");
System.out.print("收縮以後的二進制碼為:");
for(int j=0;j<n;j++)
System.out.print(tarray[j]);
int output=0;//輸出結果
int leap=1;//二進制的位數
for(int j=n-1;j>-1;j--)
{
if(tarray[j]==1)
{
output+=leap;
leap*=2;
}
else
leap*=2;
}
System.out.println(" ");
System.out.println("計算結果為:"+output);
}
}
四.調試、測試及運作結果
調試：
一開始在對擴充二進制碼進行計算的時候為了友善，直接采用6個ify語句進行計算，結果發生了錯誤
結果顯示：
發現錯誤後将6個if語句寫成了if語句的嵌套，最後擴充正确
測試：
1.測試輸入一個任意十進制的數字将其裝換成二進制碼，然後根據圖靈機的擴充規則得到相應的擴充二進制碼
調試結果：
2.測試将擴充後的二進制代碼通過圖靈機計算的規則進行計算
測試結果：
3.測試将計算計算後的二進制碼收縮成普通二進制碼，最後轉換成十進制數
測試結果：
運算結果：
1.輸入5
結果為：
2.輸入11
結果為：
3.輸入34
結果為：
五.經驗歸納
1.在解決一個問題的是時候，先不要忙的程式設計式。首先在計算本上先舉一些具體的例子來驗證自己的想法是否正确。如果有錯誤，應該認真的改正
2.在編寫程式的過程中，如果遇到一些思路上難以了解的東西，多于其他同學進行讨論，說不定在讨論的過程中，就會明白問題的本質
3.在編寫程式的時候，千萬不能投機取巧進而省略一些步驟。例如在計算擴充二進制碼的時候，為了簡單，直接用若幹個if。最後還是改成了if的嵌套，浪費了大把的時間。
4.更加體會到了在編寫程式的過程中，寫注釋的一些好處