IDA* 求解埃及分数问题

【题意】中文题目

【解题方法】

迭代加深搜索，实质上是限定下界的深度优先搜索。即首先允许深度优先搜索K层，若没有发现可行解，再将K+1后

重复以上步骤搜索，直到搜索到可行解。


在迭代加深搜索的算法中，连续的深度优先搜索被引入，每一个深度约束逐次加1，直到搜索到目标为止。这样可以

看出重复搜索了好多。但是它的好处在于：


1.空间开销小   每个深度下实际上是一个深度优先搜索，不过深度有限制，而DFS的空间消耗小是众所周知的。

2.利于深度剪枝

3.时间效率不低 虽然重复搜索，但是大家不难理解，前一次搜索跟后一次相不是微不足到的。


我们可以看出，迭代加深搜索算法就是仿广度优先搜索的深度优先搜索。既能满足深度优先搜索的线性存储要求，又能保证发现一个最小深度的目标结点。


从实际应用来看，迭代加深搜索的效果比较好，并不比广度优先搜索慢很多，但是空间复杂度却与深度优先搜索相同，比广度优先搜索小很多。


使用搜索算法的时候，选择正确的搜索方式很重要。当有一类问题需要做广度优先搜索，但却没有足够的空间，而时间却很充裕，碰到这类问题，我们可以选择迭代加深搜索算法。

解法在紫书P 206 - 208 有非常详细的介绍，有兴趣可以去看看。

【AC代码】

//
//Created by BLUEBUFF 2016/1/8
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
const int maxn = 20000;
const int maxm = 2e5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
//int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
LL maxd; //深度上限
LL v[maxn], ans[maxn]; //v是暂时存放的满足题意的分母的数组，ans是记录满足题意的最优分母值的数组
LL getmax(LL a, LL b){
    return a > b ? a : b;
}
LL gcd(LL a, LL b){
    return b == 0 ? a : gcd(b, a % b);
}
LL get_first(LL a, LL b){//取比a/b小的最大分数，分子必须为1
    LL i;
    for(i = 2;;i++){
        if(b < a * i) break;
    }
    return i;
}
bool better(int d){//如果当前解v比目前最优解ans更优，更新ans
    for(int i = d; i >= 0; i--){
        if(v[i] != ans[i]){
            return ans[i] == -1 || v[i] < ans[i];
        }
    }
    return false;
}
bool dfs(LL d, LL from, LL aa, LL bb) //当前深度为d, 分母不能小于 from, 分数之和恰好为 aa / bb
{
    if(d == maxd){
        if(bb % aa) return false; //aa / bb 必须是埃及分数，即是有理数
        v[d] = bb / aa;
        if(better(d)) memcpy(ans, v, sizeof(LL) * (d + 1)); //更新最优解
        return true; //返回最优解为真
    }
    bool ok = false;
    from = getmax(from, get_first(aa, bb)); //枚举的起点
    for(int i = from;; i++){
        //剪枝，如果剩下的maxd - d + 1个分数全部都是1 / i, 加起来仍然不超过 aa / bb， 则无解
        if((maxd - d + 1) * bb <= i * aa) break;
        v[d] = i;
        //计算 aa / bb - 1 / i， 设结果为 a2 / b2
        LL a2 = aa * i - bb;
        LL b2 = bb * i;
        LL g = gcd(a2, b2);
        if(dfs(d + 1, i + 1, a2 / g, b2 / g)) ok = true;
    }
    return ok;
}
int main()
{
    LL a, b;
    while(scanf("%lld%lld", &a, &b) != EOF)
    {
        if(a == 0){
            cout << a << "/" << b << "=0" << endl;
            continue;
        }
        memset(ans, -1, sizeof(ans));
        LL g = gcd(a, b);
        LL aa = a / g;
        LL bb = b / g;
        if(aa == 1){
            printf("%d/%d=%d/%d\n", a, b, aa, bb);
        }
        else{
            for(maxd = 1;; maxd++){
                if(dfs(0, get_first(a, b), a, b)){
                    break;
                }
            }
            printf("%d/%d=", aa, bb);
            for(int i = 0; i <= maxd - 1; i++){
                printf("1/%d+", ans[i]);
            }
            printf("1/%d\n", ans[maxd]);
        }
    }
    return 0;
}