蓝桥杯2013年第四届真题-带分数 （C++代码）深度优先搜索 DFS的应用！！！ 还有STL版本的！！ 两个啊！！不看很可惜！！

解题思路:1.dfs或者STL的next_permutation构建1~9个数的所有排列
               2.找出整数，分母，分子各自的位数范围

               3.写出由数组位数求出该数的值的算法 （可类比求逆序数的算法）

               4.暴力搜索统计即可！
注意事项:  1.整数位数最大只能为7     2.分子位数必须大于分母位数    3.分母位数不能没有
               4.最后判断 整数+分子/分母==N&&分子%分母==0  缺一不可！！ 

              5.还一个很坑的地方，求分子分母位数时，最好控制分母的位数，因为有上限为9，便于控制

             如果控制分子来弄，会报错50%，因为分母的范围被缩小了！ 体会很深。。。错很多次50%了

参考代码:  这是dfs版本的

#include<iostream>
using namespace std;
int a[10]={0,1,2,3,4,5,6,7,8,9};
bool book[10];
int total=0,N;
   //把获取的数组起终点下标转化成数 
int getNum(int x,int y){
int num=0;
for(int i=x;i<=y;i++){
num=num*10+a[i];
}
return num;
}
     //判断是否符合等式要求
 void judge(int a[]){
 int i,j;
 //整数位的范围是1~7 
for(i=1;i<=7;i++){
//先求整数
int integer=getNum(1,i); 
      //控制分母范围较好，因为控制分子的话，分母的范围会被降低！！ 
   for(j=(9-i)/2+i;j<=9;j++){
   int fz=getNum(i+1,j-1); //分子必须留一位给分母
int fm=getNum(j,9);
if(integer+fz/fm==N&&(fz%fm)==0)
   total++;
   }
}
 } 
 //求9个数的全排列 
void dfs(int step){
if(step==10){
   judge(a);
}
for(int i=1;i<=9;i++){
if(book[i]==0){
a[step]=i;
book[i]=1;
dfs(step+1);
book[i]=0;
}
}
}
int main(){
cin>>N;
dfs(1);
cout<<total;
return 0;}

     下面是STL的next_permutation版本的   后面的要简洁一点！！

#include<iostream>
#include<algorithm> 
using namespace std;
int a[10]={0,1,2,3,4,5,6,7,8,9};
bool book[10];
int total=0,N;
   //把获取的数组起终点下标转化成数 
int getNum(int x,int y){
int num=0;
for(int i=x;i<=y;i++){
num=num*10+a[i];
}
return num;
}
     //判断是否符合等式要求
 void judge(int a[]){
 int i,j;
 //整数位的范围是1~7 
for(i=1;i<=7;i++){
//先求整数
int integer=getNum(1,i); 
      //控制分母范围较好，因为控制分子的话，分母的范围会被降低！！ 
   for(j=(9-i)/2+i;j<=9;j++){
   int fz=getNum(i+1,j-1); //分子必须留一位给分母
int fm=getNum(j,9);
if(integer+fz/fm==N&&(fz%fm)==0)
   total++;
   }}} 
int main(){
cin>>N;
    do{
         judge(a);
    }while(next_permutation(a+1,a+10));
cout<<total;
return 0;}