题目描述
100 可以表示为带分数的形式:100=3+69258714
还可以表示为:100=82+3546197
注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。
类似这样的带分数,100 有 11 种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<106
解题思路:
暴力枚举出99个数的全排列,然后用一个长度为99的数组保存全排列的结果
从全排列的结果中用两重循环暴力分解出三段,形如下图,通过 i,ji,j 将一个排列分割,每段代表一个数
验证枚举出来的三个数是否满足题干条件,若满足则计数
样例
输入样例1:
100
输出样例1:
11
输入样例2:
105
输出样例2:
6
算法1
//暴力枚举出所有的全排列
//利用双重循环将全排列分为3段
#include <iostream>
using namespace std;
const int N=10;
int target;//目标数
int num[N];//用来存储全排列
bool used[N];//判断某个数是否被用过
int cnt;//计数,最后输出的结果
//计算num数组中一段的数是多少
int calc(int l,int r)
{
int res=0;
for(int i=l;i<=r;i++)
res=res*10+num[i];
return res;
}
//dfs用来生成全排列
//当全排列后生成三段
void dfs(int u)
{
//用两层循环分成三段
if(u==9)
{
for(int i=0;i<7;i++)
{
for(int j=i+1;j<8;j++)
{
int a=calc(0,i);
int b=calc(i+1,j);
int c=calc(j+1,8);
//注意判断条件,C++是整除,所以转化成加减乘运算
if(a*c+b==c*target)
{
cnt++;
}
}
}
return;
}
//搜索模板
for(int i=1;i<=9;i++)
{
if(!used[i])
{
used[i]=true;//标记使用
num[u]=i;
dfs(u+1);
used[i]=false;//还原现场
}
}
}
int main()
{
cin>>target;
dfs(0);
cout<<cnt<<endl;
return 0;
}