带分数
\(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\)
思路
- 注意提示(不重复不遗漏地)
- 递归实现组合型枚举
- 整数部分,分子部分,分母部分可以看作a,b,c,即全排列进行隔板法后的三种情况
Code
点击查看代码
#include<iostream>
using namespace std;
int ways[10];
bool st[10];
int n,cnt;
int ans;
int get(int l,int r){ //将数组中一段数组变为一个整数
int res = 0;
for(int i = l; i <= r; i++){
res += ways[i];
if(i < r)res *= 10;
}
return res;
}
void dfs(int x){ //全排列得出1-9的9!种排列
if(x > 9){ //其中一种
for(int i = 1; i <= cnt; i ++){ //i <= cnt (剪枝)
int a = get(1,i);
for(int j = i + (9 - i) / 2; j < 9;j ++){ //j = i + (9 - i) / 2(剪枝)
int b = get(i + 1,j),c = get(j + 1, 9); //相当于隔板法
if(b % c != 0)continue;
if(a + b / c != n)continue;
ans ++;
}
}
return;
}
for(int i = 1; i <= 9; i ++){
if(!st[i]){
st[i] = 1;
ways[x] = i;
dfs(x + 1);
ways[x] = 0;
st[i] = 0;
}
}
}
int main(){
cin >> n;
int nt = n;
while(nt){ //得到n的长度用于剪枝
nt /= 10;
cnt ++;
}
dfs(1);
cout << ans;
}