带分数 （dfs）c++

题目描述

100  可以表示为带分数的形式：100  =  3  +  69258  /  714。
还可以表示为：100  =  82  +  3546  /  197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100  有  11  种表示法。

输入

从标准输入读入一个正整数N  (N< 1000*1000) 

输出

程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。 
注意：不要求输出每个表示，只统计有多少表示法！ 

样例输入

100  

样例输出

11

解题思路：

题目已知，数字1-9只能出现一次，我们可以用全排列来考虑，我们可以枚举出1-9的全排列，来从中挑选符合题目条件的带分数形式。

全排列我们可以用dfs来做，对于每个全排列，我们可以用两个for循环来枚举分割点，把全排列分割成三份，分别代表带分数中的整数部分，和分数部分中的分子与分母，来判断是否符合题意。

代码示例：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10;
int n;
int res=0;
bool st[N];
int num[N];
int func(int l,int r)//求出每一部分的数值
{
    int sum=0;
    for(int i=l;i<=r;i++)
    {
        sum=sum*10+num[i];
    }
    return sum;
}
void dfs(int u)
{
    if(u==9)
    {
        for(int i=0;i<7;i++)//枚举分割点
        {
            for(int j=i+1;j<8;j++)
            {
            //求出每个部分的数值
                int a=func(0,i);
                int b=func(i+1,j);
                int c=func(j+1,8);
                
            //判断是否符合题意-（给式子两边同乘以分母）
                if(a*c +b==n*c)
                {
                    res++;
                }
            }
        }
        return ;
    }
    
    for (int i = 1; i >n;
    dfs(0);
    cout<<res<<endl;
    
    return 0;
    
}