2009/04/02
0 Comments
Follow My Logic 题目重述
对于一个逻辑电路和给定的输入值，计算该电路的输出值。该逻辑电路有一个或多个输入端， 零个或多个逻辑门电路，和一个输出端。本题中用标准ASCll字符来表示逻辑电路：横竖导线分别用‘-’和‘|’表示，转折点用‘+’表示，输入端用大写字母‘A’-’Z’表示，输出端用问号‘?’表示，小写字母‘o’表示取反。与门、或门及电路各部分示例如下：
:/ :/ -:/ -o:/ A-o:/
: ) : > : )- : )o- : )o-?
:/ :/ -:/ --:/ B-- :/
与门 或门 带输入输出 输入输出 完整电路
的门电路 取反的门电路
输入：
输入数据包含多个输入数据块。每个输入数据块包含以下部分：
一个电路图，以上述形式表示，用只含‘*’的单独一行结束。
多行01字符串，每行对应一组数据，包含26个0或1，分别对应A-Z的值。用只含‘*’的单独一行结束
输出：
对每组输入数据，输出对应的电路输出值。
每个结果占一行。
不同输入数据块的输出结果之间用空行隔开。
这是一道模拟类的题目
第一种思路：
模拟人读逻辑电路的做法，按照逻辑电路的走向确定在门电路的各个输入端的值，计算门电路输出端的值。如此反复，最终求得电路的输出值。
第二种思路：
自上至下，自左至右，顺序求解。
关键：
确定电路在交叉点的走向；
从门电路的一段输入电路转到另一段电路。
根据算法要求需要存储的数据有
1.int row, column 用来表示电路图的行数和最大宽度；
2.int ish, dir 用来表示电路走向（水平或竖直、正向或负向）；
2.char logic[100][100] 用来存储逻辑电路图；
3.int state[100][100] 用来存储电路上每一个点的值；
4.int value[26] 用来存储A-Z的值。
确定电路在交叉点的走向
根据题意，没有两个交叉点相邻，一个交叉点周围只有‘－’和‘｜’。分两种情况讨论。
if(ish) //原先为水平方向
{
if(x dir=1;
else //转向上
dir=-1;
ish=0;
x+=dir;
}
else //原先为垂直方向
{
if(y dir=1; //转向右
else
dir=-1; //转向左
ish=1;
y+=dir;
}
电路分析流程：
通过两个函数hdsearch()和process()的嵌套调用实现。
process() 用于从某一位置根据电路走向计算下一位置的值，直至获得输出结果，或到达某一门电路无法继续。
hdsearch() 用于从某一位置寻找这段电路的开头（字母输入值）。
程序从process()开始，直至某一门电路因另一输入端没有计算而无法继续。调用hdsearch()寻找到另一输入端所在电路的开头，然后调用process()继续计算。如此递归调用，直至获得最终输出结果。
#include
#include
int state[100][100],value[26],row,column,done;
char logic[100][100];
void hdsearch(int x,int y)
{
int dir,ish;
void process(int x,int y);
if(done)return;
dir=-1;ish=1;
while(!done)
{
if(logic[x][y]>='A'&&logic[x][y]<='Z')
process(x,y);
else switch(logic[x][y])
{
case '-':
case 'o':
case ':':
case '//':
case '/':
y=y+dir;
break;
case '|':
x+=dir;
break;
case ')':
case '>':
if(state[x-1][y-1]==-1)
{x--;y--;}
else if(state[x+1][y-1]==-1)
{x++;y--;}
else
{
if(logic[x][y]==')')
state[x][y]=state[x-1][y]&state[x+1][y];
else
state[x][y]=state[x-1][y]|state[x+1][y];
process(x,y);
}
break;
case '+':
if(ish)
{
if(x dir=1;
else
dir=-1;
ish=0;
x+=dir;
}
else
{
if(y dir=1;
else
dir=-1;
ish=1;
y+=dir;
}
break;
}
}
return;
}
void process(int x,int y)
{
int dir,ish;
void hdsearch(int x,int y);
if(done)return;
if(logic[x][y]>='A'&&logic[x][y]<='Z')
{
state[x][y]=value[logic[x][y]-'A'];
if(y {
ish=1;
dir=1;
y++;
state[x][y]=state[x][y-1];
}
else if(y>0&&logic[x][y-1]=='-')
{
ish=1;
dir=-1;
y--;
state[x][y]=state[x][y+1];
}
else if(x {
ish=0;
dir=1;
x++;
state[x][y]=state[x-1][y];
}
else if(x>0&&logic[x-1][y]=='|')
{
ish=0;
dir=-1;
x--;
state[x][y]=state[x+1][y];
}
}
else
{
ish=1;
dir=1;
}
while(!done)
{
switch(logic[x][y])
{
case '-':
case ':':
case ')':
case '>':
y+=dir;
state[x][y]=state[x][y-dir];
break;
case 'o':
y+=dir;
state[x][y]=state[x][y-dir]^1;
break;
case '|':
x+=dir;
state[x][y]=state[x-dir][y];
break;
case '//':
if(state[x+2][y]==-1)
hdsearch(x+2,y);
else
{
x++;
y++;
if(logic[x][y]==')')
state[x][y]=state[x-1][y-1]&state[x+1][y-1];
else
state[x][y]=state[x-1][y-1]|state[x+1][y-1];
}
break;
case '/':
if(state[x-2][y]==-1)
hdsearch(x-2,y);
else
{
x--;
y++;
if(logic[x][y]==')')
state[x][y]=state[x-1][y-1]&state[x+1][y-1];
else
state[x][y]=state[x-1][y-1]|state[x+1][y-1];
}
break;
case '+':
if(ish)
{
if(x dir=1;
else
dir=-1;
ish=0;
x+=dir;
state[x][y]=state[x-dir][y];
}
else
{
if(y dir=1;
else
dir=-1;
ish=1;
y+=dir;
state[x][y]=state[x][y-dir];
}
break;
case '?':
printf("%d/n",state[x][y]);
done=1;
break;
}
}
return;
}
int main()
{
int i,j,flag;
char c;
while(scanf("%c",&c)==1)
{
column=0;
for(i=0;(i>0?(c=getchar()):1)&&c!='*';i++)
{
if(c=='/n'){i--;continue;}
logic[i][0]=c;
for(j=1;(c=getchar())!='/n';j++)
{
logic[i][j]=c;
}
if(j>column)
column=j;
for(;j<100;j++)
logic[i][j]=' ';
}
c=getchar();
while(c=='/n')c=getchar();
row=i;
while(c!='*')
{
if(c=='/n')continue;
value[0]=c-'0';
for(i=1;i<26;i++)
{
value[i]=getchar();
value[i]-='0';
}
c=getchar();
for(i=0;i for(j=0;j state[i][j]=-1;
flag=0;
for(j=0;j for(i=0;i if(logic[i][j]>='A'&&logic[i][j]<='Z')
{flag=1;break;}
done=0;
process(i,j-1);
c=getchar();
}
printf("/n");
c=getchar();
}
return 0;
}
所有递归调用都在计算出最终结果后才返回，可用简单循环代替。Hdsearch()可作为process()的一个分支的一部分。
总结：
模拟类的程序，可以完全模拟人的思维方式进行，也可以充分利用题目中的简化条件，制定适合计算机的搜索策略。
模拟类的程序，关键要分析处理过程，找出其中的难点进行重点突破。
