递归与分治思想

例题1：

给中序遍历和后序遍历求前序遍历。

#include
using namespace std;
string zhong,hou;
//https://ac.nowcoder.com/acm/contest/21763/1011
void deal(int l1,int r1,int l2,int r2)
{
	if(l1>r1) return;
	char gen=hou[r2];
	int pos;
	for(int i=l1;i<=r1;i++)//找到中序遍历中的根节点
	{
		if(gen==zhong[i])
		{
			pos=i;
			break;
		}
	}
	printf("%c",gen);//一开始遍历根节点
	deal(l1,pos-1,l2,l2+pos-1-l1);//先遍历左子树
	deal(pos+1,r1,l2+pos-l1,r2-1);//再遍历右子树
} 
int main()
{
	cin>>zhong>>hou;
	int len=zhong.size();
	deal(0,len-1,0,len-1);
}

例题2：FBI树

#include
using namespace std;
//https://ac.nowcoder.com/acm/contest/21763/1013
string s;
void deal(int l,int r)
{
	int mid=(l+r)/2;
	if(l==r) 
	{
		if(s[l]=='1') printf("I");
		else printf("B");
		return;
	}
	deal(l,mid);//先遍历左子树 
	deal(mid+1,r);//再遍历右子树 
	int vis1=0,vis0=0;
	for(int i=l;i<=r;i++)//最后遍历根 
	{	
		if(s[i]=='1') vis1=1;
		if(s[i]=='0') vis0=1;
	}
	if(vis1==1&&vis0==1) printf("F");
	else if(vis1==0&&vis0==1) printf("B");
	else if(vis1==1&&vis0==0) printf("I");
}
int main()
{
	int n;
	cin>>n;
	int len=pow(2,n);
	cin>>s;
	deal(0,len-1);
}

写法2： 

#include
using namespace std;
//https://ac.nowcoder.com/acm/contest/21763/1013
string s;
char deal(int l,int r)
{
	int mid=(l+r)/2;
	if(l==r) 
	{
		if(s[l]=='1') 
		{
			printf("I");
			return 'I';
		}
		else {
			printf("B");
			return 'B';
		}
	}
	char zuo=deal(l,mid);//先遍历左子树 
	char you=deal(mid+1,r);//再遍历右子树 
	int vis1=0,vis0=0;
	//for(int i=l;i<=r;i++)//最后遍历根 
	//{	
	//	if(s[i]=='1') vis1=1;
	//	if(s[i]=='0') vis0=1;
	//}
	if(zuo!=you||zuo=='F'||you=='F') 
	{
		printf("F");
		return 'F';
	}
	else if(zuo==you&&zuo=='B') 
	{
		printf("B");
		return 'B';
	}
	else 
	{
		printf("I");
		return 'I';
	}
}
int main()
{
	int n;
	cin>>n;
	int len=pow(2,n);
	cin>>s;
	deal(0,len-1);
}

例题3：表达式计算

#include
using namespace std;
string s;
int trans(int l,int r)
{
	int num=0;
	for(int i=l;i<=r;i++) num=num*10+s[i]-'0';
	return num;
 } 
int calc(int l,int r)
{
	int cnt=0;//统计括号
	int pos1=-1,pos2=-1,pos3=-1;//记录+- */ ^的位置
	for(int i=l;i<=r;i++)
	{
		if(s[i]=='(') cnt++;
		if(s[i]==')') cnt--;
		if(cnt==0) 
		{
			if(s[i]=='+'||s[i]=='-') pos1=i;
			if(s[i]=='*'||s[i]=='/') pos2=i;
			if(s[i]=='^') pos3=i;
		}	
	}
	if(pos1==-1&&pos2==-1&&pos3==-1)//如果没找到运算符，说明被括号包围了，或者本身就没有运算符
	{
		if(cnt==0&&s[l]=='(')//括号刚好匹配，没有多余的括号
		{
			return calc(l+1,r-1);	
		}
		if(cnt>0)//左边括号多了
		{
			return calc(l+1,r);	
		} 
		if(cnt<0)//右括号多了
		{
			return 	calc(l,r-1);
		} 
		//数字本身 
		return trans(l,r);
	}
	if(pos1!=-1) //先考虑加减	因为优先级最低 
	{
		if(s[pos1]=='+') return calc(l,pos1-1)+calc(pos1+1,r);
		if(s[pos1]=='-') return calc(l,pos1-1)-calc(pos1+1,r);
	} 
	else if(pos2!=-1) //考虑乘除	
	{
		if(s[pos2]=='*') return calc(l,pos2-1)*calc(pos2+1,r);
		if(s[pos2]=='/') return calc(l,pos2-1)/calc(pos2+1,r);
	} 
	//else if(pos3!=-1) // 考虑^ 
	//{
		//if(s[pos3]=='^') 
            return pow(calc(l,pos3-1),calc(pos3+1,r));
	//} 
}
int main()
{
	cin>>s;
	cout< 
通过以上例题可以知道递归函数，优先执行的先写。