首页 > 代码库 > careercup-递归和动态规划 9.11
careercup-递归和动态规划 9.11
9.11 给定一个布尔表达式，由0、1、&、|和^等符号组成，以及一个想要的布尔结果result，实现一个函数，算出有几种括号的放法可使该表达式得出result值。
解法：
跟其他递归问题一样，此题的关键在于找出问题与子问题之间的关系。
假设函数int f(expression,result)会返回所有值为return的有效表达式的数量。我们想要算出f(1^0|0|1,true)（也即，给表达式1^0|0|1加括号使其求值为true的所有方式）。每个加括号的表达式最外层肯定有一对括号。因此，我们可以这么做：
也就是说，我们可以迭代整个表达式，将每个运算符当作第一个要加括号的运算符。
现在，又该如何计算这些内层的表达式呢，比如f((1^0)|(0|1),true)?很简单，要让这个表达式的值为true，左半部分和右半部分必有一位true。因此，这个表达式分解如下：
f((1^0) | (0|1),true)= f(1^0,true)* f(0|1,true) +
f(1^0,false)* f(0|1,true)+
f(1^0,true) * f(0|1,false)
对每个布尔表达式，都可以进行类似的分解：
对false结果，我们也可以执行非常类似的操作：
至此，要解决这个问题，只需反复套用这些递归关系即可。
C++实现代码：
#include<iostream>#include<string>using namespace std;int f(string exp,bool result,int s,int e){ if(s==e) { if(exp[s]==‘1‘&&result) return 1; else if(exp[s]==‘0‘&&!result) return 1; else return 0; } int c=0; int i; if(result) { for(i=s+1; i<=e; i+=2) { if(exp[i-1]==‘&‘) { c+=f(exp,true,s,i-1)*f(exp,true,i+1,e); } else if(exp[i]==‘|‘) { c+=f(exp,true,s,i-1)*f(exp,false,i+1,e); c+=f(exp,false,s,i-1)*f(exp,true,i+1,e); c+=f(exp,true,s,i-1)*f(exp,true,i+1,e); } else if(exp[i]==‘^‘) { c+=f(exp,true,s,i-1)*f(exp,false,i+1,e); c+=f(exp,false,s,i-1)*f(exp,true,i+1,e); } } } else { for(i=s+1;i<=e;i+=2) { if(exp[i-1]==‘&‘) { c+=f(exp,true,s,i-1)*f(exp,false,i+1,e); c+=f(exp,false,s,i-1)*f(exp,true,i+1,e); c+=f(exp,false,s,i-1)*f(exp,false,i+1,e); } else if(exp[i]==‘|‘) { c+=f(exp,false,s,i-1)*f(exp,false,i+1,e); } else if(exp[i]==‘^‘) { c+=f(exp,true,s,i-1)*f(exp,true,i+1,e); c+=f(exp,false,s,i-1)*f(exp,false,i+1,e); } } } return c;}int main(){ string str="1^0|0&1&0|1^1^0|1|1&0&1^0|0&1&0|1^1^0|1|1&0^1^0|0&1&0|1^1^0|1|1&0^1^0|0&1&0|1^1^0|1|1&0|1|0|0"; cout<<f(str,true,0,4)<<endl;}
虽然这么做可行，但不是很有效，对于同一个exp的值，他会重复算f(exp)很多次。
要解决这个问题，我们可以运用动态规划，缓存不同表达式的结果。注意，我们需要根据expression和result进行缓存。
dp C++实现代码：
#include<iostream>#include<string>#include<map>using namespace std;int f(string exp,bool result,int s,int e,map<string,int> &mp){ string key=""+result+s+e; if(mp.find(key)!=mp.end()) return mp[key]; if(s==e) { if(exp[s]==‘1‘&&result) return 1; else if(exp[s]==‘0‘&&!result) return 1; else return 0; } int c=0; int i; if(result) { for(i=s+1; i<=e; i+=2) { if(exp[i-1]==‘&‘) { c+=f(exp,true,s,i-1,mp)*f(exp,true,i+1,e,mp); } else if(exp[i]==‘|‘) { c+=f(exp,true,s,i-1,mp)*f(exp,false,i+1,e,mp); c+=f(exp,false,s,i-1,mp)*f(exp,true,i+1,e,mp); c+=f(exp,true,s,i-1,mp)*f(exp,true,i+1,e,mp); } else if(exp[i]==‘^‘) { c+=f(exp,true,s,i-1,mp)*f(exp,false,i+1,e,mp); c+=f(exp,false,s,i-1,mp)*f(exp,true,i+1,e,mp); } } } else { for(i=s+1;i<=e;i+=2) { if(exp[i-1]==‘&‘) { c+=f(exp,true,s,i-1,mp)*f(exp,false,i+1,e,mp); c+=f(exp,false,s,i-1,mp)*f(exp,true,i+1,e,mp); c+=f(exp,false,s,i-1,mp)*f(exp,false,i+1,e,mp); } else if(exp[i]==‘|‘) { c+=f(exp,false,s,i-1,mp)*f(exp,false,i+1,e,mp); } else if(exp[i]==‘^‘) { c+=f(exp,true,s,i-1,mp)*f(exp,true,i+1,e,mp); c+=f(exp,false,s,i-1,mp)*f(exp,false,i+1,e,mp); } } } mp[key]=c; return c;}int fDP(string exp,bool result,int s,int e){ map<string,int> dp; return f(exp,result,s,e,dp);}int main(){ string str="1^0|0&1&0|1^1^0|1|1&0&1^0|0&1&0|1^1^0|1|1&0^1^0|0&1&0|1^1^0|1|1&0^1^0|0&1&0|1^1^0|1|1&0|1|0|0"; cout<<fDP(str,true,0,4)<<endl;}
careercup-递归和动态规划 9.11
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。