题目描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。输入格式
从标准输入读入一个正整数N (N<1000*1000)
输出格式
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
输入样例
100输出样例 复制
11即n=a+b/c
方法1(最暴力的做法)：
全排列9个数字（即1~9）
使用两个for循环将9个数字分割成三个数
判断三个数是否符合题目要求的等式
注：除法没有特殊说明是整除，所以默认不是整除，此时需要避免除法，即将除法变成加减乘
时间复杂度：
全排列的时间复杂度是：n!*n；
从9个数里面放两个隔板,即在八个空挡里面选两个位置放隔板，即将9个数分成三份，是C(8,2)
所以总的时间复杂度为：n!*n*C(8,2)，即：9！*9*8*7/2=91445760
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
bool vis[10];
int n,an[10],ans;
int xten(int l,int r) {
int temp=0;
for(int i=l; i<=r; i++) {
temp=temp*10+an[i]+1;
}
return temp;
}
void dfs(int q) {
if(q==9) {
for(int i=0; i<=6; i++) {
for(int j=i+1; j<=7; j++) {
int a=xten(0,i);
int b=xten(i+1,j);
int c=xten(j+1,8);
if(c*(n-a)==b) ans++;
}
}
return ;
}
for(int i=0; i<9; i++) {
if(!vis[i]) {
vis[i]=true;
an[q]=i;
dfs(q+1);
vis[i]=false;
}
}
}
int main() {
scanf("%d",&n);
dfs(0);
printf("%d\n",ans);
return 0;
}方法二(利用n减少时间复杂度)：
先枚举a和c，通过n与a、b、c的关系推出b；即b=n*c-n*a;
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=20;
int n;
bool st[N],backup[N];
int ans=0;
bool check(int a,int c) {
int b=n*c-a*c;
if(!a||!b||!c)return false;
memcpy(backup,st,sizeof(st));
while(b) {
int x=b%10;
if(!x||backup[x])return false;
backup[x]=true;
b/=10;
}
for(int i=1; i<=9; i++) {
if(!backup[i])
return false;
}
return true;
}
void dfs_c(int u,int a,int c) {
if(u==9)return;
if(check(a,c)) {
ans++;
}
for(int i=1; i<=9; i++) {
if(!st[i]) {
st[i]=true;
dfs_c(u+1,a,c*10+i);
st[i]=false;
}
}
}
void dfs_a(int u,int a) {
if(a>=n) return ;
if(a) dfs_c(u,a,0);
for(int i=1; i<=9; i++) {
if(!st[i]) {
st[i]=true;
dfs_a(u+1,a*10+i);
st[i]=false;
}
}
}
int main() {
cin>>n;
dfs_a(0,0);
cout<<ans<<endl;
return 0;
}文章来源地址https://www.toymoban.com/news/detail-404229.html
文章来源：https://www.toymoban.com/news/detail-404229.html
到了这里，关于带分数[蓝桥杯]的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![HTTP状态 404 - 未找到 类型 状态报告 消息 请求的资源[]不可用 描述 源服务器未能找到目标资源的表示或者是不愿公开一个已经存在的资源表示。 Apache Tomcat/8.5.70](https://imgs.yssmx.com/Uploads/2024/02/511446-1.png)
