XDOJ396.图灵机模拟程序

发布时间:2024年01月08日

图灵机模拟程序

描述: 写一个图灵机模拟程序,该程序输入专用图灵机指令集及用户输入,模拟执行 图灵机程序,产生输出。

输入说明: 输入第一行为一个整数 n,表示专用图灵机指令集有 n 条指令。 接下来是 n+1 行

1)前 n 行为 n 条指令,每条指令由 5 个部分构成,每个部分用空格分隔,

如下 所示:

当前状态 输入符号 输出符号 纸带移动方向 新状态

例如:ADD 0 1 L RETURN

其中,

“当前状态”和“新状态”为一个长度不超过 20 个字符的字符串

?“输入符号”和“输出符号”各是一个字符,输入和输出符号有‘*’, ‘0’,‘1’三种,其中‘*’表示分界符,两个‘*’之内的部分是有效 输入/输出。

纸带其余部分填充‘#’表示空白 ?“纸带移动方向”也是一个字符,有三种可能:‘L’表示左移,‘R’表 示右移,‘N’表示不动

2)最后一行为一个长度不超过 100 的字符串,表示图灵机输入 该字符串由若干‘#’,两个‘*’和若干‘0’,‘1’字符构成,‘#’表示纸 带上的空白,‘*’表示输入分界符,‘0’和‘1’表示有效输入,

如下所示:

#####*101*####

注意:

(1)有两种状态是固定字符串:“INIT”表示初始状态,“STOP”表示停机状 态

(2)图灵机一开始处于初始状态(INIT),读写头位于输入右边的星号 (*),如下图所示。 (3)纸带移动方向与读写头移动方向是相对的,纸带移动方向向右表示读写头 移动方向向左 输出说明: 根据输入数据执行图灵机程序,在一行上打印出执行后的输出,只输出有效部 分,不输出‘#’,‘*’。

输入样例:

12

INIT * * N START

START * * R ADD

ADD 0 1 L RETURN

ADD 1 0 R CARRY

ADD * * L STOP

CARRY 0 1 L RETURN

CARRY 1 0 R CARRY

CARRY * 1 R OVERFLOW

OVERFLOW # * L RETURN

RETURN 1 1 L RETURN

RETURN 0 0 L RETURN

RETURN * * N STOP

##########*101*##########

输出样例: 110

样例说明: 该样例为执行二进制加 1 操作 y=x+1 的专用图灵机程序,输入为 101,输出为 110。

#include<ctype.h>
#include<stdio.h>
#include<string.h>

struct Command
{
	char now[20];
	char next[20];
	char in;
	char out;
	char move;
};

char str[200];
int ptr;

int main()
{
	int n = 0;
	Command command[100] = { 0 };
	//输入
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		getchar();
		scanf("%s %c %c %c %s", &command[i].now, &command[i].in, &command[i].out, &command[i].move, &command[i].next);
	}
	getchar();
	scanf("%s", str);
	//找到初始位置
	int flag = 0;
	for (int i = 0; i < strlen(str); i++)
	{
		if (str[i] == '*')
		{
			flag++;
			if (flag == 2)
			{
				ptr = i;
				break;
			}
		}
	}
	//初始化状态并执行对应操作
	char Now[20] = "INIT";
	while (1)
	{
		//找到和当前状态符合的命令执行操作并更新当前状态
		int i = 0;
		for (i = 0; i < n; i++)
		{
			if (strcmp(Now, command[i].now) == 0 && command[i].in == str[ptr])
			{
				break;
			}
		}
		strcpy(Now, command[i].next);
		//输出
		str[ptr] = command[i].out;
		//移动
		char Move = command[i].move;
		if (Move == 'R')
		{
			ptr--;
		}
		else if (Move == 'L')
		{
			ptr++;
		}
		//遇到“STOP”,程序停止执行
		if (strcmp(Now, "STOP") == 0)
		{
			break;
		}
	}
	for (int i = 0; i < 200; i++)
	{
		if (isdigit(str[i]))
		{
			printf("%c", str[i]);
		}
	}
	return 0;
}

文章来源:https://blog.csdn.net/yonpiguxiao/article/details/135459150
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。