poj3295 构造法

一个循环是32次，列举pqrst所有的值的情况，如果32种情况得到的值相同则为正确的。

和计算器比较像，类似算式表达式的前缀式，用递归解

 

列举32种情况

for(i=0; i<32; ++i)
  {

  switch( str[pos] )
  {
  case 'p':return i&1;
  case 'q':return i>>1&1;
  case 'r':return i>>2&1;
  case 's':return i>>3&1;
  case 't':return i>>4&1;

  }

}

开始时脑门夹到了，用

  {
  case 'p':return i&1;
  case 'q':return i&2;
  case 'r' :return i&4;
  case 's':return i&8;
  case 't':return i&16;

  }

结果返回了1 2 4 8 16，不是1

 

#include <stdio.h>
#include <string.h>
char str[130];
int pos;
int judge(char * str,int i)
{
 ++pos;
  switch( str[pos] )
  {
  case 'p':return i&1;
  case 'q':return i>>1&1;
  case 'r':return i>>2&1;
  case 's':return i>>3&1;
  case 't':return i>>4&1;
  case 'K':return judge(str,i)&judge(str,i);
  case 'A':return judge(str,i)|judge(str,i);
  case 'N':return !judge(str,i);
  case 'C':return !judge(str,i)|judge(str,i);
  case 'E':return !(judge(str,i)^judge(str,i));
  }
}

int main()
{
 int i,len,flag;
// freopen("test","r",stdin);
 while(scanf("%s",str),str[0]!='0')
 {
  flag = 1;
  for(i=0; i<32; ++i)
  {
   pos = -1;
   if( !judge(str,i) )
   {
    flag = 0;
    break;
   }
  }
  if(flag)printf("tautology\n");
  else printf("not\n");
 }
 return 0; 
}