题目描述
100 可以表示为带分数的形式:100=3+69258714
还可以表示为:100=82+3546197
注意特征:带分数中,数字 1∼9
分别出现且只出现一次(不包含 0
)。
类似这样的带分数,100
有 11
种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9
不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<106
样例
输入样例1:
100
输出样例1:
11
输入样例2:
105
输出样例2:
6
算法1
(暴力枚举)
dfs全排列,n=a+b/c 化成 nc-ac==b,化除法为乘法易表达
C++ 代码
#include <iostream>
using namespace std;
int order[10010];
int isused[10010];
int n;
int cnt;
int cal(int l,int r){
int ret=0;
for(int i=l;i<=r;i++){
ret=ret*10+order[i];
}
return ret;
}
void dfs(int u){
if(u>9){
for(int i=1;i<=9;i++){
for(int j=i+1;j<=9;j++){
int a=cal(1,i);
long long b=cal(i+1,j);//n*c-a*c==b,若bshi int,b会溢出
int c=cal(j+1,9);
if(n*c-a*c==b) cnt++;
}
}
return ;
}
for(int i=1;i<=9;i++){//模板dfs
if(isused[i]==0){
isused[i]=1;
order[u]=i;
dfs(u+1);
isused[i]=0;//回溯,恢复现场
order[u]=0;
}
}
}
int main(int argc, char** argv) {
cin>>n;
dfs(1);
printf("%d",cnt);
return 0;
}
算法2
全排列用库函数next_permutation
C++ 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,cnt;
int cal(int l,int k,int order[]){ //字符串转成整数形式
int res=0;
for(int i=l;i<=k;i++){
res=res*10+order[i];
}
return res;
}
int main(){
cin>>n;
int order[9]={1,2,3,4,5,6,7,8,9};
do{
for(int i=0;i<7;i++){
for(int j=i+1;j<8;j++){
int a=cal(0,i,order);
long long b=cal(i+1,j,order);//n*c-a*c==b,若bshi int,b会溢出
int c=cal(j+1,8,order);
if(n*c-a*c==b) { //n=a+b/c
cnt++;
}
}
}
}while(next_permutation(order,order+9));//全排列库函数
printf("%d",cnt);
return 0;
}