带分数[蓝桥杯]

题目描述

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;
}