带分数
问题描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
输入格式
从标准输入读入一个正整数N (N<1000*1000)
输出格式
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
样例输入1
100
样例输出1
11
样例输入2
105
样例输出2
6
Algorithm
一开始，常规思路进行枚举，因为等式形如：
那么考虑整除的问题，C最多不超过4位数，A不超过7位数，由等式我们可以算出B。则过程很清晰了：
分别枚举A和C，算出B，判断一下是否满足条件，计数即可。
但是仔细分析了一下时间复杂度，果然没有通过。先放一下代码：
1 /* 2 * N = A + B/C 3 * A最多7位，C最多4位,算出B 4 */ 5 #include<iostream> 6 #include<algorithm> 7 8 using namespace std; 9 10 int c = 0,N = 0;; 11 12 // 获取数字长度 13 int size(int n) 14 { 15 int c = 0; 16 while(n) 17 { 18 n /= 10; 19 c++; 20 } 21 return c; 22 } 23 24 bool sure(int A, int B, int C) 25 { 26 // 排除有0项 27 if((size(A) + size(B) + size(C)) != 9) 28 return false; 29 if(A == C) 30 return false; 31 if(B <= 0) 32 return false; 33 int s[10] = {0}; 34 // int a=A,b=B,c=C; 35 while(A!=0 || B!=0 || C!=0) 36 { 37 s[A%10]++;s[B%10]++;s[C%10]++; 38 A /= 10;B /= 10;C /= 10; 39 } 40 for(int i=1;i<=9;i++){ 41 if(s[i] != 1) 42 return false; 43 } 44 // cout<<a<<":"<<b<<":"<<c<<endl; 45 return true; 46 } 47 48 int solve(int n) 49 { 50 // 设置循环节加速，但效果甚小 51 int len[7] = {0, 9876, 987, 987, 98, 98, 9}; 52 int A = 1, C = 2, B = 0; 53 for(A=1;A<=9876543;A++){ // 需要排除有0的项 54 // 在这里的几个ABC也可以排除0项，但效果也甚微 55 for(C=2;C<=len[size(A)];C++){ 56 B = C*(N - A); 57 if(sure(A, B, C)) 58 c++; 59 } 60 } 61 return c; 62 } 63 /* 64 * 加速了还是发现时间复杂度太高，约O(9876543 * 5000) 65 * 改用全排列试试 约O(7 * 9!) 66 * 速度提升大约 70*30 倍 67 */ 68 int main() 69 { 70 while(cin>>N) 71 { 72 cout<<solve(N)<<endl; 73 c = 0; 74 } 75 return 0; 76 }
View Code
但是思路是没有问题的，接下来想到了以前做过的一道题目：桥本分数式
基本与本题一致，所以改用全排列的做法。枚举9个数的全排列确实要比循环每一个A、C快得多。
全排列可以用C++自带的 #include<algorithm> 头文件的 next_permutation 函数。也可以深度优先遍历。
用一个数组保存1 — 9之后，我们只需要尝试每一个组合的有限个分组即可，满足等式计数+1.
尽管还是有点吃力，但是勉强过了。
AC
1 /* 2 * N = A + B/C 3 * A 最长不超过7位数, 这样我们确定一个 A 4 * 然后我们可以知道 C 的最后一位为 a[8] 5 * 通过计算我们可以确定 B 的 最后一位 b_end = (N - A)*a[8]%10 6 * 如此，我们就知道了 C 为多少 7 * 最后，判断一下是否满足等式 8 */ 9 #include<iostream> 10 #include<algorithm> 11 12 using namespace std; 13 14 int c = 0,N = 0;; 15 int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 16 17 // 这里复习一下整数快速幂，就不调用数学库了 18 // O(log2N) 19 int pow(int x, int n) 20 { 21 int s = 1; 22 while(n) 23 { 24 if(n&1) s *= x; 25 x *= x; 26 n >>= 1; 27 } 28 return s; 29 } 30 31 // A、B、C, b开始, e-1结束的一段数组 32 int PI(int b, int e) 33 { 34 int s = 0, k = e-b-1; 35 while(b!=e) 36 { 37 s += a[b]*pow(10, k);k--;b++; 38 } 39 return s; 40 } 41 42 // 获取 B 最后一位的 local 43 int getB_end(int x) 44 { 45 int loc = 0; 46 for(int i=0;i<9;i++) 47 if(a[i] == x) 48 return i; 49 } 50 51 void solve(int *a, int N) 52 { 53 int A, B, C;A = B = C = 0; 54 // cout<<N<<endl; 55 for(int i=1;i<=7;i++){ 56 A = PI(0, i); 57 int B_end = ((N - A)*a[8])%10; 58 int loc = getB_end(B_end); 59 if(loc < i || loc >= 8) 60 continue; 61 // Ai! 这里注意一下是 loc + 1 62 B = PI(i, loc+1); 63 C = PI(loc+1, 9); 64 // cout<<A<<":"<<B<<":"<<C<<endl; 65 // cout<<A<<":"<<B<<":"<<C<<endl; 66 if(A*C + B == N*C){ 67 // cout<<A<<":"<<B<<":"<<C<<endl; 68 c++; 69 } 70 } 71 } 72 73 int main() 74 { 75 while(cin>>N) 76 { 77 while(next_permutation(a, a+9)) 78 { // 时间复杂度可以看成 O(9!) 79 solve(a, N); 80 // break; 81 } 82 cout<<c<<endl;c = 0; 83 } 84 return 0; 85 }
View Code
2019-01-15
19:09:38