100 可以表示为带分数的形式:100 = 3 + 69258 / 714。
还可以表示为:100 = 82 + 3546 / 197。
注意特征:带分数中,数字1~9分别出现且只出现一次(不包含0)。
类似这样的带分数,100 有 11 种表示法。
从标准输入读入一个正整数N (N< 1000*1000)
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意:不要求输出每个表示,只统计有多少表示法!
100
11
题目已知,数字1-9只能出现一次,我们可以用全排列来考虑,我们可以枚举出1-9的全排列,来从中挑选符合题目条件的带分数形式。
全排列我们可以用dfs来做,对于每个全排列,我们可以用两个for循环来枚举分割点,把全排列分割成三份,分别代表带分数中的整数部分,和分数部分中的分子与分母,来判断是否符合题意。
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 10; int n; int res=0; bool st[N]; int num[N]; int func(int l,int r)//求出每一部分的数值 { int sum=0; for(int i=l;i<=r;i++) { sum=sum*10+num[i]; } return sum; } void dfs(int u) { if(u==9) { for(int i=0;i<7;i++)//枚举分割点 { for(int j=i+1;j<8;j++) { //求出每个部分的数值 int a=func(0,i); int b=func(i+1,j); int c=func(j+1,8); //判断是否符合题意-(给式子两边同乘以分母) if(a*c +b==n*c) { res++; } } } return ; } for (int i = 1; i >n; dfs(0); cout<<res<<endl; return 0; }
0.0分
2 人评分