带分数DFS小白讲解

我这里是用了dfs进行全排列解答，
需要注意的一点就是题目描述不能有零 （N = x + dmo/mo //x、dmo、mo 每一位上都不能有零），
从1到N进行遍历然后利用dfs全排列即可，具体细节请看代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <set>
#include <stack>
#include<algorithm>
using namespace std;

typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int ans=0,b[10]={0},a[10],x;  //答案，标记数组，排列数组，遍历变量
int N;  //输入

bool check(){  //检查现在的全排列能否构成带分数
    int s=x,w=0;
    while(s){
        w++;
        s/=10;
    }
    int dmo=0,mo=0; //分母，分子
    int pos=(9-w)/2+w;
    for(int i=pos;i<=8;i++){  //遍历分母分子间隔点
        dmo=mo=0;
        for(int j=w+1;j<=i;j++){
            dmo*=10;
            dmo+=a[j];
        }
        for(int j=i+1;j<=9;j++){
            mo*=10;
            mo+=a[j];
        }
        if(dmo%mo==0){  //需要判断是否整除
            if(x+dmo/mo==N){
                return true;
            }
        }
    }
    return false;
}

void dfs(int step){   //对1~9剩下的数的全排列
    if(step>9){
        if(check())
            ans++;
        return ;
    }
    for(int i=1;i<=9;i++){
        if(b[i]==0){
            b[i]=1;  //标记
            a[step]=i;
            dfs(step+1);
            b[i]=0;
        }
    }
}


int main(){
    cin >> N;
    for(int i=1;i<N;i++){  //遍历
        int flag=1;
        x=i;   //记录当前标记的数，这里用的全局变量
        int w=0,s=i;  //记录当前数的位数和定义中间变量标记数组
        memset(b,0,sizeof b);
        while(s){  //检查当前的数有几位
            w++;
            if(b[s%10]==0)  //标记当前数的每一位
                b[s%10]=1;
            else
                flag=0;
            if(s%10==0)  //题目描述不能有零
                flag=0;
            s/=10;
        }
        if(flag)
            dfs(w+1);  //从现在遍历的数后面一位进行全排列
    }
    cout << N << " " << ans;
}

以上是本小白的讲解，有什么不对还请大佬们指正。