模拟图灵机程序

支持 Windows 98 及以上的操作系统编译运行。

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <Windows.h>
#include "TuringMachine.h"

HINSTANCE hInstance;
HWND hWinMain;
LPCSTR szClassName = "VLSMB";
LPCSTR szCaptionMain = "计算理论-图灵机程序 Code By VLSMB";

LPCSTR HELP_DOCUMENT = "计算理论-图灵机程序 Code By VLSMB\r\n\r\n使用说明:\r\n首先点击加载语法,选择一个图灵机文件(*.tm)加载到程序中。然后在输入框中输入你想输入的语句,点击左侧的输入按钮完成输入。之后就可以点击左侧的执行单步或者执行全部来模拟图灵机的运行。\r\n\r\n*.tm文件结构的说明:\r\n第一行,是一个字符串。描述这个tm的作用。(注意中文编码为GBK!!!)\r\n第二行有一个数字k,代表图灵机状态的数量(图灵机的状态从0开始,则状态为0~k - 1,其中k - 1为终止状态,0为开始状态)\r\n第三行有一个数字a,代表输入字符种类的个数。\r\n第四行有a个字符,每个字符使用空格相隔,代表输入字符的集合。(字符为char,这里只给出输入带上的字符,图灵机后来填涂的字符不算)\r\n第五行有一个整数n,代表转移函数的个数。\r\n之后有n行五元组,每一行为一个转移函数,分别为q、a、q'、a'、d,含义见图灵机定义。";


LRESULT CALLBACK _ProcWinMain(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam);
int WINAPI _WinMain();

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nShowCmd)
{
return _WinMain();
}

LRESULT CALLBACK _ProcWinMain(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam)
{
switch (uMsg)
{
case WM_CREATE:
{
InitTMMemory();
HWND hWnBtn = CreateWindowExA(0, "BUTTON", "加载语法", WS_TABSTOP | WS_VISIBLE | WS_CHILD | BS_DEFPUSHBUTTON,
30, 30, 100, 30, hWnd, (HMENU)(BTN_LOAD), hInstance, NULL);
HFONT hFont = CreateFontA(14, 0, 0, 0, FW_NORMAL, FALSE, FALSE, FALSE, DEFAULT_CHARSET, OUT_DEFAULT_PRECIS, CLIP_DEFAULT_PRECIS, DEFAULT_QUALITY, DEFAULT_PITCH, "Arial");
HFONT hFont_Big = CreateFontA(20, 0, 0, 0, FW_NORMAL, FALSE, FALSE, FALSE, DEFAULT_CHARSET, OUT_DEFAULT_PRECIS, CLIP_DEFAULT_PRECIS, DEFAULT_QUALITY, DEFAULT_PITCH, "Arial");
HFONT hFont_Data = CreateFontA(20, 0, 0, 0, FW_NORMAL, FALSE, FALSE, FALSE, DEFAULT_CHARSET, OUT_DEFAULT_PRECIS, CLIP_DEFAULT_PRECIS, DEFAULT_QUALITY, DEFAULT_PITCH, "Courier");
SendMessageA(hWnBtn, WM_SETFONT, (WPARAM)hFont, TRUE);
HWND hWnEdit = CreateWindowExA(0, "STATIC", "未加载图灵机。", WS_CHILD | WS_VISIBLE,
180, 30, 520, 30, hWnd, (HMENU)EDIT_GRINFO, hInstance, NULL);
SendMessageA(hWnEdit, WM_SETFONT, (WPARAM)hFont_Big, TRUE);
hWnEdit = CreateWindowExA(0, "BUTTON", "点击输入", WS_TABSTOP | WS_VISIBLE | WS_CHILD | BS_DEFPUSHBUTTON,
30, 100, 100, 30, hWnd, (HMENU)BTN_INPUT, hInstance, NULL);
SendMessageA(hWnEdit, WM_SETFONT, (WPARAM)hFont, TRUE);
hWnEdit = CreateWindowEx(0, "EDIT", "", WS_CHILD | WS_VISIBLE | WS_BORDER | ES_AUTOHSCROLL,
180, 100, 520, 30, hWnd, (HMENU)EDIT_INPUT, hInstance, NULL);
SendMessageA(hWnEdit, WM_SETFONT, (WPARAM)hFont_Data, TRUE);
hWnEdit = CreateWindowExA(0, "STATIC", "输出:", WS_CHILD | WS_VISIBLE,
30, 150, 100, 30, hWnd, (HMENU)EDIT_GRINFO, hInstance, NULL);
SendMessageA(hWnEdit, WM_SETFONT, (WPARAM)hFont_Big, TRUE);
hWnEdit = CreateWindowEx(0, "EDIT", "", WS_CHILD | WS_VISIBLE | WS_BORDER | ES_MULTILINE | ES_AUTOVSCROLL | ES_READONLY | ES_AUTOHSCROLL,
180, 150, 520, 300, hWnd, (HMENU)EDIT_OUTPUT, hInstance, NULL);
ShowScrollBar(hWnEdit, SB_VERT, TRUE);
SendMessageA(hWnEdit, EM_SETSEL, 0, 0);
SendMessageA(hWnEdit, EM_SETREADONLY, TRUE, 0);
SendMessageA(hWnEdit, WM_SETFONT, (WPARAM)hFont_Data, TRUE);
hWnBtn = CreateWindowExA(0, "BUTTON", "执行单句", WS_TABSTOP | WS_VISIBLE | WS_CHILD | BS_DEFPUSHBUTTON,
30, 200, 100, 30, hWnd, (HMENU)(BTN_RUNSingle), hInstance, NULL);
SendMessageA(hWnBtn, WM_SETFONT, (WPARAM)hFont, TRUE);
hWnBtn = CreateWindowExA(0, "BUTTON", "全部执行", WS_TABSTOP | WS_VISIBLE | WS_CHILD | BS_DEFPUSHBUTTON,
30, 250, 100, 30, hWnd, (HMENU)(BTN_RUNAll), hInstance, NULL);
SendMessageA(hWnBtn, WM_SETFONT, (WPARAM)hFont, TRUE);
hWnBtn = CreateWindowExA(0, "BUTTON", "帮助", WS_TABSTOP | WS_VISIBLE | WS_CHILD | BS_DEFPUSHBUTTON,
30, 350, 100, 30, hWnd, (HMENU)(BTN_HELP), hInstance, NULL);
SendMessageA(hWnBtn, WM_SETFONT, (WPARAM)hFont, TRUE);
hWnBtn = CreateWindowExA(0, "BUTTON", "清空输入", WS_TABSTOP | WS_VISIBLE | WS_CHILD | BS_DEFPUSHBUTTON,
30, 300, 100, 30, hWnd, (HMENU)(BTN_CLEAR), hInstance, NULL);
SendMessageA(hWnBtn, WM_SETFONT, (WPARAM)hFont, TRUE);
}
break;
case WM_CLOSE:
DeleteTMMemory();
DestroyWindow(hWnd);
PostQuitMessage(NULL);
break;
case WM_COMMAND:
{
if (LOWORD(wParam) == BTN_LOAD && HIWORD(wParam) == BN_CLICKED)
{
ReadTuringMachine(hWnd);
}
else if (LOWORD(wParam) == BTN_RUNSingle && HIWORD(wParam) == BN_CLICKED)
{
RunSingleStep(hWnd);
}
else if (LOWORD(wParam) == BTN_RUNAll && HIWORD(wParam) == BN_CLICKED)
{
RunAllStep(hWnd);
}
else if (LOWORD(wParam) == BTN_INPUT && HIWORD(wParam) == BN_CLICKED)
{
GetInput(hWnd);
}
else if (LOWORD(wParam) == BTN_CLEAR && HIWORD(wParam) == BN_CLICKED)
{
ClearInput(hWnd);
}
else if (LOWORD(wParam) == BTN_HELP && HIWORD(wParam) == BN_CLICKED)
{
MessageBoxA(hWnd, HELP_DOCUMENT, TITLE, MB_ICONINFORMATION);
}
}
default:
return DefWindowProcA(hWnd, uMsg, wParam, lParam);
}
return 0;
}
int WINAPI _WinMain()
{
WNDCLASSEXA stWndClass;
MSG stMsg;
hInstance = GetModuleHandleA(NULL);
RtlZeroMemory(&stWndClass, sizeof(stWndClass));

stWndClass.hCursor = LoadCursorA(0, IDC_ARROW);
stWndClass.hInstance = hInstance;
stWndClass.cbSize = sizeof(WNDCLASSEX);
stWndClass.style = CS_HREDRAW | CS_VREDRAW;
stWndClass.lpfnWndProc = _ProcWinMain;
stWndClass.hbrBackground = (HBRUSH)(COLOR_WINDOW + 1);
stWndClass.lpszClassName = szClassName;
RegisterClassExA(&stWndClass);

hWinMain = CreateWindowExA(WS_EX_CLIENTEDGE, szClassName, szCaptionMain, WS_OVERLAPPEDWINDOW, 100, 100, 800, 600, NULL, NULL, hInstance, NULL);

ShowWindow(hWinMain, SW_SHOWNORMAL);
UpdateWindow(hWinMain);

while (1)
{
if (GetMessageA(&stMsg, NULL, 0, 0) == 0)
break;
TranslateMessage(&stMsg);
DispatchMessageA(&stMsg);
}
return (int)stMsg.wParam;
}

TuringMachine.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#ifndef __TURINGMACHINE_H
#define __TURINGMACHINE_H

#include <Windows.h>
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

#define BTN_LOAD 0x1001
#define BTN_RUNSingle 0x1002
#define BTN_RUNAll 0x1003
#define EDIT_GRINFO 0x1004
#define EDIT_INPUT 0x1005
#define EDIT_OUTPUT 0x1006
#define BTN_INPUT 0x1007
#define BTN_HELP 0x1008
#define BTN_CLEAR 0x1009

#define TITLE "图灵机程序"

void InitTMMemory();
void DeleteTMMemory();
void ReadTuringMachine(HWND hWnd);
void RunSingleStep(HWND hWnd);
void RunAllStep(HWND hWnd);
void GetInput(HWND hWnd);
void ClearInput(HWND hWnd);

void _ShowSingleStatus(HWND hWnd);
void _ShowAddStatus(HWND hWnd);
bool _RunSingleStep_Inner(HWND hWnd);



struct node
{
int qc;
char ac;
int qn;
char an;
char mv;
};

#endif

TuringMachine.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
#include "TuringMachine.h"

bool hasLoaded = false; // 判断语法是否加载
bool hasInput = false; // 是否存在输入
const int N = 100005;
//struct node grammar[N]; // 存储语法
struct node* grammar = NULL;
int numOfGrammer = 0; // 语法的数量
//char status[N]; // 当前输入带字符情况
//char pointer[N];
char* status = NULL;
char* pointer = NULL;
int curStatus = -1; // 当前图灵机状态
int pos = 0; // 读头位置
int numOfStatus = 0; // 图灵机状态数量
//char Alphabet[N]; // 字母表
char* Alphabet = NULL;
int numOfAlpha; // 字母的数量

void InitTMMemory()
{
status = new char[N];
RtlZeroMemory(status, sizeof(char)*N);
pointer = new char[N];
RtlZeroMemory(pointer, sizeof(char) * N);
Alphabet = new char[N];
RtlZeroMemory(Alphabet, sizeof(char) * N);
grammar = new struct node[N];
RtlZeroMemory(grammar, sizeof(struct node) * N);
}
void DeleteTMMemory()
{
delete[] status;
delete[] pointer;
delete[] Alphabet;
delete[] grammar;
}

/*

*.tm文件结构的说明:

第一行,是一个字符串。描述这个tm的作用。(注意中文编码为GBK!!!)
第二行有一个数字k,代表图灵机状态的数量(图灵机的状态从0开始,则状态为0~k-1,其中k-1为终止状态,0为开始状态)
第三行有一个数字a,代表输入字符种类的个数。
第四行有a个字符,每个字符使用空格相隔,代表输入字符的集合。(这里只给出输入带上的字符,图灵机后来填涂的字符不算)
第五行有一个整数n,代表转移函数的个数。
之后有n行五元组,每一行为一个转移函数,分别为q、a、q'、a'、d,含义见图灵机定义。

*/

void ReadTuringMachine(HWND hWnd)
{
OPENFILENAME ofn; // 文件选择对话框结构体
char szFile[260] = { 0 }; // 用于保存文件路径

ZeroMemory(&ofn, sizeof(ofn));
ofn.lStructSize = sizeof(ofn);
ofn.hwndOwner = hWnd;
ofn.lpstrFile = szFile;
ofn.lpstrFile[0] = '\0';
ofn.nMaxFile = sizeof(szFile);
ofn.lpstrFilter = "TuringMachine files\0*.TM\0All files\0*.*\0";
ofn.nFilterIndex = 1;
ofn.lpstrFileTitle = NULL;
ofn.nMaxFileTitle = 0;
ofn.lpstrInitialDir = NULL;
ofn.lpstrTitle = "打开图灵机配置文件";
ofn.Flags = OFN_PATHMUSTEXIST | OFN_FILEMUSTEXIST | OFN_ALLOWMULTISELECT;
if (GetOpenFileName(&ofn) != TRUE) return;

char* useful = new char[N];

ifstream file(szFile);
if (!(file >> useful >> numOfStatus >> numOfAlpha))
{
MessageBoxA(hWnd, "文件损坏!", TITLE, MB_ICONERROR);
return;
}
int i = 0, j = 0;
for (i = 0; i < numOfAlpha; i++)
{
if (!(file >> Alphabet[i]))
{
MessageBoxA(hWnd, "文件损坏!", TITLE, MB_ICONERROR);
return;
}
}
if (!(file >> numOfGrammer))
{
MessageBoxA(hWnd, "文件损坏!", TITLE, MB_ICONERROR);
return;
}
for (i = 0; i < numOfGrammer; i++)
{
if (!(file >> grammar[i].qc >> grammar[i].ac >> grammar[i].qn >> grammar[i].an >> grammar[i].mv))
{
MessageBoxA(hWnd, "文件损坏!", TITLE, MB_ICONERROR);
return;
}
}
char tmp;
file >> tmp;
if (!file.eof())
{
MessageBoxA(hWnd, "文件损坏!", TITLE, MB_ICONERROR);
return;
}
MessageBoxA(hWnd, "图灵机加载成功!", TITLE, MB_ICONINFORMATION);
SetWindowTextA(GetDlgItem(hWnd, EDIT_GRINFO), useful);
ClearInput(hWnd);
hasLoaded = true;
delete[] useful;
}

void GetInput(HWND hWnd)
{
if (!hasLoaded)
{
MessageBoxA(hWnd, "未加载图灵机配置文件!", TITLE, MB_ICONWARNING);
return;
}
HWND hEdit = GetDlgItem(hWnd, EDIT_INPUT);
int len = GetWindowTextLengthA(hEdit);
char* buf = new char[len + 10];
GetWindowTextA(hEdit, buf + 1, len + 1);
buf[len + 1] = '\0';
int i = 0, j = 0, fg = 0;
for (i = 1; i <= len; i++)
{
fg = 0;
for (j = 0; j < numOfAlpha && !fg; j++)
{
if (Alphabet[j] == buf[i])
{
fg = 1;
break;
}
}
if (!fg)
{
MessageBoxA(hWnd, "输入字符中存在非字母表的字符!", TITLE, MB_ICONERROR);
return;
}
}
buf[0] = 'B';
buf[len+1] = 'B';
buf[len + 2] = '\0';
hasInput = true;
pos = 1;
curStatus = 0;
strcpy(status, buf);
_ShowSingleStatus(hWnd);
delete[] buf;
MessageBoxA(hWnd, "输入成功!", TITLE, MB_ICONINFORMATION);
}

void ClearInput(HWND hWnd)
{
if (!hasLoaded || !hasInput) return;
hasInput = false;
SetWindowTextA(GetDlgItem(hWnd, EDIT_OUTPUT), "");
}

void _ShowSingleStatus(HWND hWnd)
{
for (int i = 0; i < pos; i++)pointer[i] = ' ';
pointer[pos] = '*';
pointer[pos + 1] = '\0';
char* buf = new char[strlen(status) + strlen(pointer) + 10];
strcpy(buf, status);
buf[strlen(status)] = '\r';
buf[strlen(status) + 1] = '\n';
strcpy(buf + strlen(status) + 2, pointer);
HWND hEdit = GetDlgItem(hWnd, EDIT_OUTPUT);
SetWindowTextA(hEdit, buf);
delete[] buf;
}
void _ShowAddStatus(HWND hWnd)
{
for (int i = 0; i < pos; i++)pointer[i] = ' ';
pointer[pos] = '*';
pointer[pos + 1] = '\0';
char* buf = new char[strlen(status) + strlen(pointer) + 10];
strcpy(buf, status);
buf[strlen(status)] = '\r';
buf[strlen(status) + 1] = '\n';
strcpy(buf + strlen(status) + 2, pointer);
HWND hEdit = GetDlgItem(hWnd, EDIT_OUTPUT);
/*SetWindowTextA(hEdit, buf);*/
int len = GetWindowTextLengthA(hEdit);
char* buf2 = new char[strlen(buf) + len + 10];
GetWindowTextA(hEdit, buf2, len+1);
buf2[len] = '\r';
buf2[len + 1] = '\n';
strcpy(buf2 + len + 2, buf);
SetWindowTextA(hEdit, buf2);
delete[] buf;
delete[] buf2;
}

void RunSingleStep(HWND hWnd)
{
if (!hasLoaded)
{
MessageBoxA(hWnd, "未加载图灵机配置文件!", TITLE, MB_ICONWARNING);
return;
}
if (!hasInput)
{
MessageBoxA(hWnd, "请输入语句!", TITLE, MB_ICONWARNING);
return;
}
if (_RunSingleStep_Inner(hWnd)) _ShowSingleStatus(hWnd);
else
{
if (curStatus == numOfStatus - 1) MessageBoxA(hWnd, "图灵机接受了输入!", TITLE, MB_ICONINFORMATION);
else MessageBoxA(hWnd, "图灵机拒绝了输入!", TITLE, MB_ICONWARNING);
}
}

void RunAllStep(HWND hWnd)
{
if (!hasLoaded)
{
MessageBoxA(hWnd, "未加载图灵机配置文件!", TITLE, MB_ICONWARNING);
return;
}
if (!hasInput)
{
MessageBoxA(hWnd, "请输入语句!", TITLE, MB_ICONWARNING);
return;
}
SetWindowTextA(GetDlgItem(hWnd, EDIT_OUTPUT), "");
while (_RunSingleStep_Inner(hWnd)) _ShowAddStatus(hWnd);
if (curStatus == numOfStatus - 1) MessageBoxA(hWnd, "图灵机接受了输入!", TITLE, MB_ICONINFORMATION);
else MessageBoxA(hWnd, "图灵机拒绝了输入!", TITLE, MB_ICONWARNING);
}

bool _RunSingleStep_Inner(HWND hWnd)
{
if (curStatus == numOfStatus - 1)return false;
int fg = 0;
for (int i = 0; i < numOfGrammer; i++)
{
if (curStatus == grammar[i].qc && status[pos] == grammar[i].ac)
{
fg = 1;
curStatus = grammar[i].qn;
if (status[pos] = 'B' && status[pos + 1] == '\0')
{
status[pos + 1] = 'B';
status[pos + 2] = '\0';
}
status[pos] = grammar[i].an;
if (grammar[i].mv == 'L')pos--;
else if(grammar[i].mv == 'R') pos++;
if (status[pos] == '\0')
{
status[pos] = 'B';
status[pos + 1] = '\0';
}
if (pos < 0)
{
MessageBoxA(hWnd, "图灵机读头越界!可能转移函数存在错误!", TITLE, MB_ICONERROR);
return false;
}
break;
}
}
return fg ? true : false;
}

语法定义文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
判断输入是否为0^n1^n,其中n大于等于1
6
2
0 1
13
0 0 1 X R
0 Y 3 Y R
1 0 1 0 R
1 1 2 Y L
1 Y 1 Y R
2 0 2 0 L
2 X 0 X R
2 Y 2 Y L
3 Y 3 Y R
3 B 4 B L
4 X 4 0 L
4 Y 4 1 L
4 B 5 B S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
判断字符串是不是wcw的结构,其中w为a、b的正闭包。
11
3
a b c
33
0 a 1 X R
1 a 1 a R
1 b 1 b R
1 c 9 c R
9 X 9 X R
9 Y 9 Y R
9 a 3 X L
3 X 3 X L
3 Y 3 Y L
3 c 4 c L
4 a 5 a L
4 b 5 b L
5 a 5 a L
5 b 5 b L
5 X 0 X R
5 Y 0 Y R
0 b 2 Y R
2 a 2 a R
2 b 2 b R
2 c 8 c R
8 X 8 X R
8 Y 8 Y R
8 b 3 Y L
4 X 6 X R
4 Y 6 Y R
6 X 6 X R
6 Y 6 Y R
6 c 6 c R
6 B 7 B L
7 c 7 c L
7 X 7 a L
7 Y 7 b L
7 B 10 B R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
计算自然数n以2为底的对数,用一进制a代表输入,b代表输出
6
1
a
17
0 c 0 c R
0 a 1 c R
1 c 1 c R
1 b 1 b R
1 a 2 a R
2 a 1 c R
2 c 2 c R
2 b 2 b R
2 B 3 b L
3 b 3 b L
3 c 3 c L
3 a 3 a L
3 B 0 B R
1 B 3 b L
0 b 4 B L
4 c 4 B L
4 B 5 B R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
计算m-n的值,输入为0^m10^n的形式,输出为0的序列。
7
2
0 1
16
0 0 1 B R
0 1 5 B R
1 0 1 0 R
1 1 2 1 R
2 1 2 1 R
2 0 4 1 L
2 B 3 B L
3 0 3 0 L
3 1 3 B L
3 B 6 0 S
4 0 4 0 L
4 1 4 1 L
4 B 0 B R
5 0 5 B R
5 1 5 B R
5 B 6 B S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
将一进制转换为二进制。输入带为n个a,输出为n的二进制01序列。
9
1
a
30
0 c 0 c R
0 0 6 0 L
0 1 6 1 L
0 a 1 c R
1 c 1 c R
1 a 2 a R
1 0 4 0 S
1 1 4 1 S
1 B 4 B S
2 c 2 c R
2 a 1 c R
2 0 3 0 S
2 1 3 1 S
2 B 3 B S
3 0 3 0 R
3 1 4 0 R
3 B 5 0 L
4 1 4 1 R
4 0 3 1 R
4 B 5 1 L
5 a 5 a L
5 c 5 c L
5 0 5 0 L
5 1 5 1 L
5 B 0 B R
6 c 6 c L
6 B 7 B R
7 c 7 B R
7 0 8 0 S
7 1 8 1 S