题目描述
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循环来枚举分割点,把全排列分割成三份,分别代表带分数中的整数部分,和分数部分中的分子与分母,来判断是否符合题意。
代码示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #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; } |
9.9 分
2 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复