蓝桥杯 历届试题 带分数 DFS最容易理解版，内有解析

#include <stdio.h>
#include <string.h>
bool visited[15] ;
int ans = 0 , n , num[5] , k = 0 ;
char str[] ="123456789+/";
char res[15] ;

//剪枝函数 
bool judge()
{
	if(num[0]>=n||num[1]<num[2])	//当第一个数>=输入的数时，肯定不符合条件，当第三个数大于第二个数时，因为不能整除，所以也不行。 
	{
		return false;
	}
	if(num[0]&&num[1]&&num[2])
	{
		if(num[0]+num[1]/num[2]<n)	//当第一个数和第二个数都已得到，此时第三个数正在增大，num[0]+num[1]只会越来越小 
		{
			return false ;
		}
	}
	if(num[0]&&num[1]&&num[2])
	{
		if(num[0]+num[1]<=n)	//若num[0]+num[1]都小于n,则 num[0]+num[1]/num[2]<n必成立 
		{
			return false ;
		}
	}
	return true ;
}
void DFS(int index)
{
	if(11==index && num[0]&&num[1]&&num[2])
	{
		if((num[1]*1.0/num[2]-num[1]/num[2]<0.000001))
		{
			if(num[0]+num[1]/num[2] == n)
			{
				++ans;
			}
		}
		return ;
	}
	else if(!judge())
	{
		return ;
	}
	else
	{
		for(int i = 0 ; i < 11 ; ++i)
		{
			if(!visited[i])
			{
				if(str[i] == '/')	//除号必须在加号之前进行 
				{
					if(!visited[9])
					{
						continue ;
					}
				}
				visited[i] = true ;
				
				if(str[i]>'0'&&str[i]<='9')
				{
					num[k] = num[k]*10+str[i]-'0'  ;
				}
				else 
				{
					++k; 
				}
				res[index] = str[i] ;
				DFS(index+1) ;
				res[index] = '\0' ;
				if(str[i]>'0'&&str[i]<='9')
				{
					num[k] = (num[k]-str[i]+'0')/10  ;
				}
				else
				{
					--k ;
				}
				visited[i] = false;
			}
		}
	}
}

int main()
{
	ans = 0 ;
	scanf("%d",&n);
	DFS(0);
	printf("%d",ans) ;
	return 0 ;
}