题目描述

主要是先递归出所有可能的9位排序。然后把前几位作为整数，中间几位作为分子，末尾几位作为分母进行计算的，拆分数字没有用到递归，不知道有没有更合理的方法。

样例

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
int n;
int coun;
bool state[10];
int nums[10];
int interger;
int ret[3];//分子，分母

bool dfs2(int cur)//找分子分母
{
    for(int i=cur;i<9;i++)
    {
        for(int a=cur;a<=i;a++)
        {
            ret[1]*=10;
            ret[1]+=nums[a];
        }
        for(int b=i+1;b<=9;b++)
        {
            ret[2]*=10;
            ret[2]+=nums[b];
        }
        if(interger+((float)ret[1]/ret[2])==n)
        {
            return true;
        }
        ret[1]=ret[2]=0;
    }
    return false;
}
bool dfs1()//找整数
{
    int cur=2;
    interger = nums[1];
    while(interger<n)
    {
        if(dfs2(cur))
        {
            return true;
        }
        interger*=10;
        interger+=nums[cur++];
    }
    return false;
}

void fun()
{
    if(dfs1())
    {
        /*
        for(int i=1;i<=9;i++)
        {
            printf("%d ",nums[i]);
        }
        printf("\n");
        */
        coun++;
    }
    interger=0;
}
void dfs(int u)//枚举所有可能
{
    if(u>9)
    {
        fun();
        return;
    }
    for(int i=1;i<=9;i++)
    {
        if(!state[i])
        {
            state[i]=true;
            nums[u]=i;
            dfs(u+1);

            //还原现场
            state[i]=false;
            nums[u]=0;
        }
    }
}

int main()
{
    cin>>n;
    dfs(1);
    cout<<coun;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla