Any fool can do it!(Poj2475Zoj2800)(递归备忘录)

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2800

             http://poj.org/problem?id=2475

 

题意:题目给出了此题Set的递归定义,要求根据这个定义确定一个串是不是Set;

解题:就是根据定义一条条的写出递归函数,然后需要注意的是有很多递归的调用存在大量的重复运算,要加备忘录记录结果.

 

8500699dooder_daodao2475Accepted208K32MSC++1165B2011-04-17 00:47:45

 

#include<stdio.h> #include<string.h> #define M 256 char map[M][M]; char s[M]; char Set(int ,int ); char Elem(int ,int ); char List(int ,int ); char ElemList(int ,int ); char Atom(int ,int ); char ElemList(int p,int q) { if(map[p][q]>=0) return map[p][q]; if(p==q+1) return map[p][q]=1; return map[p][q]=List(p,q); } char Elem(int p,int q) { if(map[p][q]>=0) return map[p][q]; return map[p][q]=Atom(p,q)||Set(p,q); } char List(int p,int q) { int i; if(map[p][q]>=0) return map[p][q]; if(Elem(p,q)) return map[p][q]=1; for(i=p;i<=q;i++){ if(s[i]==','){ if(Elem(p,i-1)&&List(i+1,q)) return map[p][q]=1; } } return map[p][q]=0; } char Atom(int p,int q) { return p==q; } char Set(int p,int q) { if(q-p<1) return map[p][q]=0; if(map[p][q]>=0) return map[p][q]; if(s[p]=='{'&&s[q]=='}') return map[p][q]=ElemList(p+1,q-1); return map[p][q]=0; } int main() { int t,k,p,q; char set; scanf("%d",&t); for(k=1;k<=t;k++){ memset(map,-1,sizeof(map)); scanf("%s",s); printf("Word #%d: ",k); p=0;q=strlen(s)-1; set=Set(p,q); puts(set?"Set":"No Set"); } return 0; }