题目描述

blablabla

样例

b//先用一个数组保存1-9的全排列
//再用一个二重循环将一个数分成三段，枚举出所有可能的情况
//将这三段进行组合，满足带分数则进行计数

#include<iostream>
//#include<cmath>   注意：如果用头文件math里面的函数pow来求平方，相当于在循环里多了一个函数，所以会超时。
using namespace std;

int num;
int sta[10];
int used[10];
int count=0;

void dfs(int pos){
    if(pos>9) {

        for(int i=1;i<=7;i++){
            for(int j=1;j<=7;j++){
            int k=9-i-j;
            if(j>=k && k>=1){
                int res=0;int b=0;int c=0;
                for(int x=1;x<=i;x++)
                    res=res*10+sta[x];
                for(int y=i+1;y<=i+j;y++)
                    b=b*10+sta[y];
                for(int z=i+j+1;z<=9;z++)
                    c=c*10+sta[z];

                //if(res+b/c==num)  count++; //注意判断条件，因为C++中除法是整除，所以要转化为加减乘来计算
                //如果不改成乘法来计算的话会有很多的数满足条件，因为好多分数做 / 都会得到同一个整数。
                if(res*c+b==num*c) count++;
            }
            }
        }
        return;
}

    for(int i=1;i<=9;i++){
        if(!used[i]){
            sta[pos]=i;
            used[i]=true;
            dfs(pos+1);
            used[i]=false;
            sta[pos]=0;
        }
    }
    return;
}


int main(){
    scanf("%d",&num);
    dfs(1);
    printf("%d",count);
    return 0;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla