埃及分数问题 迭代加深搜索/IDA*

输入整数a,b (0<a<b<500) ,输出最佳表达式 使得加数个数尽量小，如果加数个数相同，则最小的分数越大越好 ，输出表达式

考虑从小到大枚举深度上限maxd，每次执行只考虑深度不超过maxd的结点。当前的结点n的深度为g(n)，乐观估价函数为h(n),则当

g(n)+h(n)>maxd时应该剪枝，这就是IDA*算法。

#include<iostream>

#include<string>

#include<cmath>

#include<cstring>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

#include<queue>

#include<stack>

#include<sstream>

#include<cstdio>

#define INF 0x3f3f3f3f

//const int maxn = 1e6 + 5;

const double PI = acos(-1.0);

typedef long long ll;

using namespace std;

int a, b, maxd;

ll gcd(ll a, ll b) {

    return b ==  ? a : gcd(b, a % b);

}

inline int get_first(ll a, ll b) {

    return b / a + ;

}

const int maxn =  + ;

ll v[maxn], ans[maxn];

bool better(int d) {

    for (int i = d; i >= ; i--) if (v[i] != ans[i]) {

        return ans[i] == - || v[i] < ans[i];

    }

    return false;

}

bool dfs(int d, int from, ll aa, ll bb) {

    if (d == maxd) {

        if (bb % aa) return false;

        v[d] = bb / aa;

        if (better(d)) memcpy(ans, v, sizeof(ll) * (d + ));

        return true;

    }

    bool ok = false;

    from = max(from, get_first(aa, bb));

    for (int i = from;; i++) {

        if (bb * (maxd +  - d) <= i * aa)  break;

        v[d] = i;

        ll b2 = bb * i;

        ll a2 = aa * i - bb;

        ll g = gcd(a2, b2);

        if (dfs(d + , i + , a2 / g, b2 / g)) ok = true;

    }

    return ok;

}

int main() {

    int kase = ;

    while (scanf("%d%d", &a, &b) != EOF) {

        int ok = ;

        for (maxd = ; maxd <= ; maxd++) {

            memset(ans, -, sizeof ans);

            if (dfs(, get_first(a, b), a, b)) {

                ok = ;

                break;

            }

        }

        printf("Case %d: ", ++kase);

        if (ok) {

            printf("%d/%d=",a,b);

            for (int i = ; i < maxd; i++) printf("1/%lld+", ans[i]);

            printf("1/%lld\n", ans[maxd]);

        }

        else printf("No solution\n");

    }

    return ;

}