144 lines
4.9 KiB
C++
144 lines
4.9 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
typedef long long ll; // 使用 long long 以处理较大的分母，避免溢出
|
||
|
||
// 计算最大公约数（GCD），用于约分分数
|
||
ll gcd(ll a, ll b) {
|
||
return b == 0 ? a : gcd(b, a % b); // 辗转相除法
|
||
}
|
||
|
||
// 将分数 n/d 约分为最简形式
|
||
pair<ll, ll> reduce(ll n, ll d) {
|
||
ll g = gcd(abs(n), d); // 计算 n 和 d 的 GCD，abs(n) 防止负数问题
|
||
return {n / g, d / g}; // 返回约分后的分子和分母
|
||
}
|
||
|
||
// 表示埃及分数搜索状态的结构体
|
||
struct State {
|
||
ll num, den; // 当前剩余分数 num/den
|
||
vector<ll> dens; // 已选择的单位分数的分母列表
|
||
|
||
// 计算当前状态的最大分母
|
||
ll max_den() const {
|
||
if (dens.empty()) return 0; // 如果没有分母，返回 0
|
||
return *max_element(dens.begin(), dens.end()); // 返回分母列表中的最大值
|
||
}
|
||
};
|
||
|
||
// 哈希函数，用于在 unordered_set 中存储状态（本实现未使用，但保留以备扩展）
|
||
struct StateHash {
|
||
size_t operator()(const State& s) const {
|
||
string str;
|
||
for (ll x : s.dens) str += to_string(x) + ",";
|
||
str += to_string(s.num) + "/" + to_string(s.den);
|
||
return hash<string>()(str);
|
||
}
|
||
};
|
||
|
||
// 获取当前状态的所有后继状态
|
||
vector<State> get_successors(const State& state, int limit, int depth) {
|
||
vector<State> res; // 存储所有可能的后继状态
|
||
ll r = state.num, s = state.den; // 当前剩余分数 r/s
|
||
if (r == 0) return res; // 如果分子为 0，无需继续扩展
|
||
|
||
// 确定最小分母：必须大于上一个分母（保证分母递增，避免重复），且满足 r/s >= 1/d
|
||
ll last_d = state.dens.empty() ? 0 : state.dens.back();
|
||
ll min_d = max(last_d + 1, (s + r - 1) / r); // min_d = ceil(s/r)
|
||
|
||
// 设置分母的上限，防止过大的分母导致计算溢出
|
||
const ll MAX_D = 10000000LL; // 合理的安全上限
|
||
|
||
// 枚举可能的单位分母 d
|
||
for (ll d = min_d; d <= MAX_D; ++d) {
|
||
// 优化：检查剩余步数是否足够表示剩余分数
|
||
int rem_steps = limit - depth - 1; // 剩余可用步数
|
||
double max_sum_after = 0.0; // 剩余步数能表示的最大分数和
|
||
for (int i = 1; i <= rem_steps; ++i) {
|
||
max_sum_after += 1.0 / (d + i); // 假设后续分母递增
|
||
}
|
||
double this_contrib = 1.0 / d; // 当前单位分数的贡献
|
||
double target = (double)r / s; // 目标剩余分数
|
||
// 如果当前贡献加上后续最大可能贡献仍小于目标，剪枝
|
||
if (this_contrib + max_sum_after < target - 1e-10) break;
|
||
|
||
// 计算新分数：r/s - 1/d = (r*d - s) / (s*d)
|
||
ll new_num = r * d - s;
|
||
if (new_num < 0) continue; // 新分子为负，非法状态
|
||
ll new_den = s * d;
|
||
auto p = reduce(new_num, new_den); // 约分新分数
|
||
State ns = {p.first, p.second, state.dens}; // 创建新状态
|
||
ns.dens.push_back(d); // 添加当前单位分母
|
||
res.push_back(ns); // 将新状态加入后继列表
|
||
}
|
||
return res;
|
||
}
|
||
|
||
// 深度优先搜索（DFS），在当前深度限制下搜索解
|
||
void dfs(const State& state, int depth, int limit, vector<State>& solutions) {
|
||
if (depth > limit) return; // 超过深度限制，回溯
|
||
if (state.num == 0 && !state.dens.empty()) { // 找到一个解：分子为 0 且有至少一个分母
|
||
solutions.push_back(state); // 记录解
|
||
return; // 不再扩展此路径
|
||
}
|
||
// 遍历所有后继状态
|
||
for (const auto& next : get_successors(state, limit, depth)) {
|
||
dfs(next, depth + 1, limit, solutions); // 递归搜索
|
||
}
|
||
}
|
||
|
||
// 迭代加深搜索（IDS），寻找最短长度且最大分母最小的埃及分数
|
||
State find_best_egyptian(ll a, ll b) {
|
||
auto p = reduce(a, b); // 约分输入分数
|
||
State start = {p.first, p.second, {}}; // 初始状态
|
||
State best; // 记录最佳解
|
||
ll best_max = LLONG_MAX; // 最佳解的最大分母
|
||
int limit = 0; // 当前深度限制
|
||
|
||
while (true) {
|
||
++limit; // 增加深度限制
|
||
vector<State> solutions; // 存储当前深度下的所有解
|
||
dfs(start, 0, limit, solutions); // 执行 DFS
|
||
if (!solutions.empty()) { // 如果找到解
|
||
for (const auto& s : solutions) { // 遍历所有解
|
||
ll cur_max = s.max_den(); // 当前解的最大分母
|
||
if (cur_max < best_max) { // 如果最大分母更小，更新最佳解
|
||
best = s;
|
||
best_max = cur_max;
|
||
}
|
||
}
|
||
return best; // 返回最佳解
|
||
}
|
||
if (limit > 100) { // 安全限制，防止无限循环
|
||
cout << "No solution found within limit." << endl;
|
||
exit(1);
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
ll a, b;
|
||
// 输入分子和分母，要求 0 < a < b 且互质
|
||
cout << "Enter numerator and denominator (a b, with 0 < a < b, gcd=1): ";
|
||
cin >> a >> b;
|
||
if (a >= b || a <= 0 || gcd(a, b) != 1) { // 简单输入验证
|
||
cout << "Invalid input: require 0 < a < b and gcd(a,b)=1" << endl;
|
||
return 1;
|
||
}
|
||
|
||
State result = find_best_egyptian(a, b); // 寻找最佳埃及分数
|
||
|
||
// 输出结果
|
||
cout << a << "/" << b << " = ";
|
||
for (size_t i = 0; i < result.dens.size(); ++i) {
|
||
if (i > 0) cout << " + ";
|
||
cout << "1/" << result.dens[i]; // 打印单位分数
|
||
}
|
||
cout << endl;
|
||
cout << "Length: " << result.dens.size() << endl; // 打印分解长度
|
||
cout << "Max denominator: " << result.max_den() << endl; // 打印最大分母
|
||
|
||
return 0;
|
||
}
|