问题描述
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
使用全排列：
#include<iostream> #include<algorithm> using namespace std; int main() { int g[10] = { 0,1,2,3,4,5,6,7,8,9 }; int res = 0, n; cin >> n; do { for (int i = 1; i <= 7; i++) { for (int j = 1; j + i < 9; j++) { int x1 = 0, x2 = 0, x3 = 0; for (int a = 1; a <= i; a++) { x1 = x1 * 10 + g[a]; } for (int b = i + 1; b <= i + j; b++) { x2 = x2 * 10 + g[b]; } for (int c = i + j + 1; c <= 9; c++) { x3 = x3 * 10 + g[c]; } if (x1 + x2 * 1.0 / x3 == n) res++; } } } while (next_permutation(g+1, g + 10)); cout << res << endl; return 0; }
使用递归代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 20; int n; bool st[N]; //状态 bool backup[N]; //拷贝用 int ans; bool check(int a, int c) { int b = n * c - a * c; if (!a || !b || !c) return false; memcpy(backup, st, sizeof(st)); while (b) { int x = b % 10; b /= 10; if (!x || backup[x]) return false; backup[x] = true; } for (int i = 1; i <= 9; i++) { if (!backup[i]) return false; } return true; } void dfs_c(int u, int a, int c) { if (u == n) return; if (check(a, c)) ans++; for (int i = 1; i <= 9; i++) { if (!st[i]) { st[i] = true; dfs_c(u + 1, a, c * 10 + i); st[i] = false; } } } void dfs_a(int u, int a) //u表示当前已经用了多少个数字 { if (a >= n) return; dfs_c(u, a, 0); for (int i = 1; i <= 9; i++) { if (!st[i]) { st[i] = true; dfs_a(u + 1, a*10+i); st[i] = false; } } } int main() { cin >> n; dfs_a(0, 0); cout << ans << endl; return 0; }
