首页 > 代码库 > poj 3295 Tautology 伪递归
poj 3295 Tautology 伪递归
题目链接：
http://poj.org/problem?id=3295
题目描述：
给一个字符串，字符串所表示的表达式中p, q, r, s, t表示变量，取值可以为1或0。K, A, N, C, E 分别表示且，或，非，真蕴含，等值。问表达式是不是永真的，如果是输出“tautology”，否则输出“not”。
解题思路：
这里借用到了递归的本质，也就是对栈的模拟，用递归进行压栈，求表达式的值，再加上对变量状态压缩进行枚举。
1 #include <cstdio>//本代码用G++交就ac，c++交就wa，因为G++是从前向后求值的，c++是从后向前求值的， 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 #define maxn 105 8 char str[maxn]; 9 int index;10 11 bool dfs (int num);//对表达式求值12 bool judge ();//对变量的取值进行枚举13 int main ()14 {15 while (scanf ("%s", str), strcmp(str, "0"))16 {17 if (judge ())18 printf ("tautology\n");19 else20 printf ("not\n");21 }22 return 0;23 }24 bool dfs (int num)25 {26 index ++;27 if (str[index] == ‘p‘)28 return num & 1;29 else if (str[index] == ‘q‘)30 return (num >> 1) & 1;31 else if (str[index] == ‘r‘)32 return (num >> 2) & 1;33 else if (str[index] == ‘s‘)34 return (num >> 3) & 1;35 else if (str[index] == ‘t‘)36 return (num >> 4) & 1;37 else if (str[index] == ‘K‘)38 return dfs (num) & dfs (num);//这里的& | 不能用&& ||，因为后者使用时前面的为假就会停止运算，不能达到预计的效果39 else if (str[index] == ‘A‘)40 return dfs (num) | dfs (num);41 else if (str[index] == ‘N‘)42 return !dfs (num);43 else if (str[index] == ‘C‘)44 return !dfs(num) | dfs(num);45 else if (str[index] == ‘E‘)46 return dfs (num) == dfs(num);47 48 }49 bool judge ()50 {51 int i;52 for (i=0; i<32; i++)53 {54 index = -1;55 if (!dfs (i))56 return 0;57 }58 return 1;59 }
poj 3295 Tautology 伪递归
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。