A27372. 将整数换成分数
题目描述
将整数换成分数
题目描述
一个小于 100 万的正整数 n，尝试把 n 变成带分数形式，也就是 n=a+b/c，其中a，b，c 是三个正整数，并且数字 1~9（不含 0）在 a、b、c 中，必须出现，且只能出现一次。例如：100=3 + 69258/714，其中 1 到 9 这 9 个数字全都出现了，并且只出现一次。当然，100 还等于 82 + 3546/197，也就是说将 100 变成带分数形式，会有两种组合方式。事实上 100，可以写成 11 种 1 到 9 组成整数加上分数的形式。
请编写一个程序，根据一个输入 N，程序输出该数字用数码 1~9 不重复不遗漏地组成带分数表示的全部可能性。不要求输出每个表示，只输出有多少种表示法！
输入格式
输入一行，表示要分解的正整数。
输出格式
输出一行，表示有多少分法。
样例输入
100样例输出
11注意事项
请严格按要求输出，不要多余的打印语句，例如：“输入 x=...” 等多余内容。本程序的代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意: main 函数需要返回 0。
注意: 只使用 ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include<xxx>， 不能通过工程设置而省略常用头文件。
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int count = 0;
void check(int n, const vector<int>& digits) {
// 尝试所有可能的分割方式
for (int a_len = 1; a_len <= 7; ++a_len) {
for (int b_len = 1; b_len <= 8 - a_len; ++b_len) {
int c_len = 9 - a_len - b_len;
if (c_len < 1) continue;
// 构造a、b、c
int a = 0;
for (int i = 0; i < a_len; ++i) {
a = a * 10 + digits[i];
}
int b = 0;
for (int i = a_len; i < a_len + b_len; ++i) {
b = b * 10 + digits[i];
}
int c = 0;
for (int i = a_len + b_len; i < 9; ++i) {
c = c * 10 + digits[i];
}
// 检查是否满足n = a + b / c且b % c == 0
if (c != 0 && b % c == 0 && a + b / c == n) {
count++;
}
}
}
}
void permute(int n, vector<int>& digits, int start) {
if (start == digits.size()) {
check(n, digits);
return;
}
for (int i = start; i < digits.size(); ++i) {
swap(digits[start], digits[i]);
permute(n, digits, start + 1);
swap(digits[start], digits[i]);
}
}
int main() {
int n;
cin >> n;
vector<int> digits = {1, 2, 3, 4, 5, 6, 7, 8, 9};
permute(n, digits, 0);
cout << count << endl;
return 0;
}答案解析
#include <iostream>
#include <vector>
using namespace std;
// 检查数字是否包含1到9且不重复
bool isValid(int a, int b, int c) {
vector<bool> used(10, false); // 用于标记1到9的数字是否被使用
int num;
// 检查a
num = a;
while (num > 0) {
if (used[num % 10]) return false; // 如果数字重复，返回false
used[num % 10] = true;
num /= 10; }
// 检查b
num = b;
while (num > 0) {
if (used[num % 10]) return false;
used[num % 10] = true;
num /= 10;
}
// 检查c
num = c;
while (num > 0) {
if (used[num % 10]) return false;
used[num % 10] = true;
num /= 10;
}
// 检查是否包含1到9的所有数字
for (int i = 1; i <= 9; ++i) {
if (!used[i]) return false;
}
return true;}
int main() {
int n; // 输入的整数
cin >> n;
int count = 0; // 符合条件的表示方法数量
// 遍历所有可能的a, b, c组合
for (int a = 1; a < n; ++a) {
for (int b = 1; b < n; ++b) {
for (int c = 1; c < n; ++c) {
if (a * c + b == n && isValid(a, b, c)) { // 检查是否符合条件
count++;
}
}
}
}
// 输出符合条件的表示方法数量
cout << count << endl;
return 0;
}