迭代加深搜索 埃及数字

埃及分数问题

参考lrj紫书：在古埃及，人们用单位分数的和(即1/a，a是自然数）表示一切有理数。例如2/3=1/2+1/6，但不允许2/3=1/3+1/3，因为在加数中不允许有相同的。
对于一个分数a/b，表示方法多种，其中加数少的比加数多的好，如果加数个数相同，最小的分数越大越好。
输入a，b，(0<a<b<500) 找最佳表达式
样例： 495 499
输出：Case 1: 495/499=1/2+1/5+1/6+1/8+1/3992+1/14970

自然数有无限个，回溯法甚至无法搜索完一层的扩展。解决办法是枚举回溯的深度maxd，这样只要解的深度有限，扩展便可有限的完成。

dfs(d, from, ca, cb)的含义是：在扩展最大深度为d的限制下，寻找：最大分数是1/from，分数之和为ca/cb的解，存于v数组中。

有个地方解释下：
from = max(from, getFirst(ca, cb));
这一行是因为每次扩展的时候都是dfs(d+1,i+1,na/g,nb/g)，这里i+1和getFirst(na/g,nb/g)的相对大小其实是不确定的，取其大作为新一次dfs的from即可。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
const int inf = 0x3f3f3f3f, maxN = 1e2 + 5;
int N, M, T;
ll v[maxN], ans[maxN];
int a, b, maxd;

ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
// 找到满足1/c <= a/b的最大1/c,亦最小c,返回c
int getFirst(ll a, ll b) { return b / a + 1; }
// 当前v数组存的解更短/一样长但是分数更大
bool better(int d) {
    rrep(i, 0, d + 1)
        if (v[i] != ans[i])
            return ans[i] == -1 || v[i] < ans[i];
    return 0;
}

bool dfs(int d, int from, ll ca, ll cb) {
    if (d == maxd) {
        if (cb % ca)
            return 0;
        v[d] = cb / ca;
        if (better(d))
            memcpy(ans, v, sizeof(ll) * (d + 1));
        return 1;
    }
    bool ok = 0;
    from = max(from, getFirst(ca, cb));

    for (int i = from; ; ++i) {
        // 若剩下maxd+1-d个分数全是1/i仍不够ca/cb
        if (cb * (maxd + 1 - d) <= i * ca)
            break;
        v[d] = i;

        // 计算ca/cb-1/i 结果为na/nb
        ll nb = cb * i;
        ll na = ca * i - cb;
        ll g = gcd(na, nb);
        if (dfs(d + 1, i + 1, na / g, nb / g))
            ok = 1;
    }
    return ok;
}

int main() {
    // freopen("data.in", "r", stdin);
    int kase = 0;
    while (cin >> a >> b) {
        int ok = 0;
        for (maxd = 1; maxd <= 100; ++maxd) {
            mst(ans, -1);
            if (dfs(0, getFirst(a, b), a, b)) {
                ok = 1;
                break;
            }
        }
        cout << "Case " << ++kase << ": ";
        if (ok) {
            cout << a << "/" << b << "=";
            rep(i, 0, maxd)
                cout << "1/" << ans[i] << "+";
            cout << "1/" << ans[maxd] << "\n";
        } else {
            cout << "No solution.\n";
        }
    }
    return 0;
}