题目
100 可以表示为带分数的形式:$100 = 3 + \frac{69258}{714}$
还可以表示为:$100 = 82 + \frac{3546}{197}$
注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。
类似这样的带分数,100 有 11 种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<106
输入样例1:
100
输出样例1:
11
输入样例2:
105
输出样例2:
6
题解
解法一
思路
1、枚举全排列1 - 9 的所有数字
2、将所有的结果进行分解,分成三个数字
3、对这三个数字进行验证是否成功
代码
时间复杂度:因为这题比较暴力,因此需要计算一下时间复杂度
全排列已知是O(n*n!) , 又验证的时候,枚举隔板是8位置个选2个隔板,计算数字忽略。
$
时间复杂度为 : n\times n! \times C_{2}^{8}
又因为 n = 9,有 9 \times 9! \times 8 \times 7 \div 2 = 91445760 \leq 10^8
$
刚好成立
空间复杂度:一般题目给出的都是64MB,使用60MB一下都是可以的
其中 1byte 称为1B , 1bit 称为1b即一位(一个二进制位数) , 有 1byte = 8 bit
#include<iostream>
using namespace std;
const int N = 20;
int shu[N];//存放全排列数字
bool st[N];//数字是否出现
int n;//输入一个数字,验证符合的数字个数
int cnt;//符合条件的数字个数
//验证一个排列是否符合
void yan()
{
int a = 0,b = 0, c = 0;
//分成三段
for(int i = 2; i<9 ; i++)
{
for(int j = i+1 ; j<10 ; j++)
{
a = 0,b = 0,c = 0;//重新验证新数字
for(int x = 1 ; x < i ; x++) a = a * 10 + shu[x] ;
for(int y = i ; y < j ; y++) b = b * 10 + shu[y] ;
for(int z = j ; z < 10; z++) c = c * 10 + shu[z] ;
//等式要符合,并且要是b和c能整除
if(n == a + (b / c) && b % c == 0) cnt++;
}
}
}
void dfs(int u)
{
//处理边界
if(u == 10)
{
//进行验证数字
yan();
return ;
}
//枚举1 - 9 不重复的数字
for(int i = 1 ; i<10 ; i++)
{
if(!st[i])
{
st[i] = true;
shu[u] = i;
dfs(u+1);//递归
st[i] = false;//恢复现场
}
}
}
int main()
{
cin>>n;
dfs(1);//从1开始
cout<<cnt;//输出符合的个数
return 0;
}
解法二
思路
先枚举求出a,然后枚举求出c,利用n , a , c 的关系求出数字b
判断数字b是否符合即可
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 20;
bool st[N];//判断数字有没有用过
int n;//输入一个数字,验证符合的数字个数
int cnt;//符合条件的数字个数
//利用a、 c 求出b,判断b是否符合
bool check(int a,int c)
{
//求出b ,因为 n = a + b/c ,有b = nc - ac
int b = n*c - a*c;
//a 、b、 c有一个是0都返回false
if(!a || !b || !c) return false;
//a、b、c里面1 - 9必须出现,并且只能出现一次
bool ch[N] ;
memcpy(ch , st ,sizeof st);//必须拷贝一份,直接使用st,恢复现场很麻烦
while(b)
{
int j = b % 10;
if(!j || ch[j]) return false;//取到了数字0,或者数字j已经被使用
b /= 10;
ch[j] = true;//标记数字j
}
for(int i = 1 ; i<=9 ; i++)
{
if(!ch[i]) return false;//存在有1 - 9数字没有被使用,返回false
}
return true;
}
//枚举求出c
void dfs_c(int u ,int a ,int c)
{
if(u == 9) return;//这里如果使用了9个,说明b已经没有了
if(c) if(check(a,c)) cnt++;
for(int i = 1 ; i<=9 ; i++)
{
if(!st[i])
{
st[i] = true;
dfs_c(u+1, a , c*10 + i);
st[i] = false;
}
}
}
//枚举求出a
void dfs_a(int u,int a)
{
if(a >= n || u == 8) return ;//当a比n大,显然不行 ,u已经到达第8层,说明用了8个数字
if(a) dfs_c(u+1 , a , 0); //当a不为0的时候,递归找出c
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<<cnt;//输出符合的个数
return 0;
}