蓝桥杯历届试题-带分数 （C++代码）(深搜)

解题思路:

深搜

注意事项:

区分三个数



参考代码:#include<iostream>
#include<cstring>
using namespace std;
int n,result;
int book[10],a[10];
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[])
{
    for(int i=1;i<=7;i++)//整数部分最少一位,做多7位
    {
        int x=getnum(1,i);
        for(int j=(9-i)/2+i;j<=9;j++)//分母最多为(9-i)/2位(奇数时直接是最小位数) 故j直接表示分母的位数
        {
            int y=getnum(i+1,j-1);//y表示分子
            int z=getnum(j,9);//z表示分母
            if((y%z)==0&&(x+y/z)==n)
                result++;
        }
    }
}
void dfs(int step)
{
    if(step==10)
    {
        judge(a);
        return;
    }
    for(int i=1;i<=9;i++)
    {
        if(book[i]==0)
        {
            book[i]=1;
            a[step]=i;
            dfs(step+1);
            book[i]=0;
        }
    }
    return;
}
int main()
{
    cin>>n;
    dfs(1);
    cout<<result<<endl;
}