[C++知识库]蓝桥杯_带分数C++(dfs与STL)

问题描述：
??100 可以表示为带分数的形式：100 = 3 + 69258 / 714。还可以表示为：100 = 82 + 3546 / 197。注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。类似这样的带分数，100 有 11 种表示法。
输入：从标准输入读入一个正整数N (N< 1000*1000)
输出：程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。 注意：不要求输出每个表示，只统计有多少表示法！

样式输入：100
样式输出：11

方法一：这里采用algorithm库中的next_permutation，该函数是进行所有数的全排列，可以列出1-9的全排列，从而只需要考虑符号的位置

//用vector比普通数组慢一些
//使用STL——next_permutation(first,end)
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int lenth(int n);
int num(int i,int j,vector<int> v);

int main(){
    int n,i,j,count=0;
    vector<int> v;
    for(i=1;i<=9;i++){
        v.push_back(i);
    }//将1-9数读入vector
    cin>>n;
    do{
        for(i=0;i<=lenth(n);i++){
            for (int j = i; j < 8; j++) {
                    if (j - i < 8 - j) 
                        continue;
                int a=num(0,i,v);
                int b=num(i+1,j,v);
                int c=num(j+1,8,v);
                if((n==a+b/c)&&(b%c==0)){
                    count++;
                }
            }
        }
    }while(next_permutation(v.begin(),v.end()));//排列1-9，同时进行演算
    cout<<count<<endl;
    return 0;
}

int lenth(int n){
    int len=0;
    while(n){
        len++;
        n=n/10;
    }
    return len;
}

int num(int i,int j,vector<int> v){
    int sum=0,m;
    for(m=i;m<=j;m++){
        sum=sum*10+v[m];
    }
    return sum;
}

方法二：dfs

#include <iostream>

using namespace std;

int a[10]={0,1,2,3,4,5,6,7,8,9};
int book[10];
int total=0,N;
void judge(int a[]);
void dfs(int step);

int main(){
    cin>>N;
    dfs(1);
    cout<<total;
    return 0;
}

int num(int x,int y){
    int num=0,i;
    for(i=x;i<=y;i++){
        num=num*10+a[i];
    }
    return num;
}

void judge(int a[]){
    int i,j;
    for(i=1;i<=7;i++){
        int interger=num(1,i);//控制分子
        for(j=(9-i)/2+i;j<=9;j++){
            int fz=num(i+1,j-1);
            int fm=num(j,9);
            if(interger+fz/fm==N&(fz%fm==0))
                total++;
        }
    }
}

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;
        }
    }
}