带分数(蓝桥杯真题)

题目描述：100 可以表示为带分数的形式：100=3+69258/714

还可以表示为：100=82+3546/197

注意特征：带分数中，数字 1∼9

分别出现且只出现一次（不包含 0）。

类似这样的带分数，100有 11种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 1∼9

不重复不遗漏地组成带分数表示的全部种数。

数据范围

1≤N<106

输入样例1：
 100
输出样例1：
 11
输入样例2：
 105
输出样例2：
 6

这是很典型的一种题型，深搜生成全排列，下面给出三种解法

方法1：利用c++自带的next_permutation()函数，(感兴趣的同学可以百度一下)

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 int arr[] = {1,2,3,4,5,6,7,8,9};
 int n,cnt;
 
 int getSubSum(int start,int tail,int *arr){
     int sum = 0;
     for(int i=start;i<tail;i++){
         sum=sum*10+arr[i];
     }
     return sum;
 }
 
 int getNumLen(int x){
     int len=0;
     while(x){
         x/=10;
         len++;
     }
     return len;
 }
 int main(){
     scanf("%d",&n);
     do{
         for(int i=1;i<=getNumLen(n);i++){
             //整数部分位数不能大于我们输入的n的位数
             for(int j=i+1;j<9;j++){
               //枚举j的截取位置，不能到九，因为至少要给分母留一位
                 if(j-i<9-j){//分子位数必须多于分母。 
                     continue;
                 }
                 int zs = getSubSum(0,i,arr);
                 int fz = getSubSum(i,j,arr);
                 int fm = getSubSum(j,9,arr);
                 if(zs+fz/fm==n&&fz%fm==0){
                     //通过check,cnt就++。
                     cnt++;
                 }
             }
         }
     }while(next_permutation(arr,arr+9));
     cout<<cnt<<endl;
     return 0;
 }

方法2：相较于方法1，可以理解为自行将next_permutation()的功能实现一下,

没有实质区别,下面是代码：

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 int n,cnt;
 int dt[10];//用来记录全排列
 bool vis[10];//判重数组，
 int getNumLen(int x){//求某个整数的位数
     int len=0;
     while(x){
         x/=10;
         len++;
     }
     return len;
 }
 
 int getSubSum(int head,int tail,int *arr){
     int sum=0;
     for(int i=head;i<tail;i++){
         sum=sum*10+arr[i];
     }
     return sum;
 }
 void dfs(int x){
     if(x==10){//边界处理 
         for(int i=1;i<=getNumLen(n);i++){
             for(int j=i+1;j<9;j++){
                 if(j-i<9-j){
                     continue;
                 }
                 int zs = getSubSum(1,i+1,dt);
                 int fz = getSubSum(i+1,j+1,dt);
                 int fm = getSubSum(j+1,10,dt);
                 if(zs+fz/fm==n&&fz%fm==0){
                     cnt++;
                 }
             }
         }
         return;
     }
     //非边界深搜
     for(int i=1;i<=9;i++){
         if(!vis[i]){
             vis[i] = 1;
             dt[x] = i;
             dfs(x+1);
             vis[i] = 0;
             dt[x] = 0;
         }
     } 
 } 
 int main(){
     cin>>n;
     dfs(1);//从第一个位置开始放置，按什么位置放什么数的策略递归 
     cout<<cnt<<endl;
     return 0;
 }

方法3：题意原等式：n = a+b/c 。我们对等式稍加变形->n*c = a*c+b;这样，我们再用两层dfs,分别用来枚举a和c的值，再根据变形后的等式求出b的值，最后做判重和非零判断，若判断通过，则cnt++。下面是代码：

 #include<iostream>
 #include<algorithm>
 #include<cstring>
 #include<cstdio>
 using namespace std;
 //将带分数稍加变形(左右同时乘以c),即得：n*c = c*a + b.其中，a是整数，b是分子，c是分母。 
 //这样，我们就可以通过枚举a和c两个数，b便自然得出，再通过check，cnt就++。 
 int n;
 int cnt;
 bool vis[30];//1~9是否已经被访问的判断数组
 bool backup[30];//用来做判重的数组，其实其中的数据来自vis，
 //只是我们不希望vis数组在递归时受到影响，就把vis数组中的数据拷贝到backup中 
 
 bool check(int a,int c){
     int b = n*c - a*c;
     if(!a||!b||!c)return false;
     
     //判重
     memcpy(backup,vis,sizeof(vis));
     
     //因为递归到这里a和c的用的数字是不会有所重复的，所以只需要对b的位数做判断
     //此时，vis数组中只有部分元素为1，即a和c的数字组成， 
     while(b){
         int one = b%10;
         b/=10;
         if(!one||backup[one]){//！one表示b的每一位不应该为0(题目要求),backup[one]指的是one这个数字在之前没有出现过 
             return false;
         } else {//否则 
             backup[one] = 1;//否则，将此为设为已经使用 
         }
     } 
     
     for(int i=1;i<=9;i++){
         if(!backup[i]) return false;
     }
     return true;
 } 
 void dfs_c(int num,int a,int c){
     if(num>9)return;
     
     if(check(a,c)) cnt++;
     for(int i=1;i<=9;i++){
         if(!vis[i]){
             vis[i] = 1;
             dfs_c(num+1,a,c*10+i);
             vis[i] = 0;
         }
     }
     
 }
 void dfs_a(int num,int a){
     //if(num>9)
     if(a>=n)return;//整数部分不小于我们的输入，就return，不满足
     
     if(a) dfs_c(num,a,0);
     
     for(int i=1;i<=9;i++){
         if(!vis[i]){
             vis[i] = 1;
             dfs_a(num+1,a*10+i);
             vis[i] = 0;
         }
     }
 } 
 
 int main(){
     cin>>n;
     
     dfs_a(0,0);//参数一是1~9用了几个数，参数二是a的数值大小。
     //其中，第一个参数的边界条件是在dfs_c中来判断的，因为dfs_c的递归比dfs_a更深 
     cout<<cnt<<endl; 
     return 0;
 }