埃及分数 -- 迭代加深

首先给不了解迭代加深的同学简单介绍一下：

迭代深入搜索（IDS），其本质上就是深度优先搜索，IDS结合了DFS的空间优势与BFS的时间优势。
搜索的过程对深度进行了限制，使得在搜索到限制深度后必须开始新的搜索路径。
以至于看上去像是广搜，但实现形式是深搜。（总是完成第n的所有节点搜索，再开始第n+1的节点的搜索）。
放在这里的话，n指的就是当前的限制深度。

PS.如果你是第一次学习迭代加深，推荐先完成 Addition Chains熟悉迭代加深的模板。

动手之前，必须要理清的一件事：应该按照什么规则进行拆分？

拆分规则

1.这个分数不能大于输入的分数

~~（废话）~~

2.对分母的限制

在分解成 n 个分数的情况下。

分母最小为 2，不可能是 1 ，题目要求 a<b 即分子小于分母。

分母最大为，假设平均分 n 份，那么最大的分数是，倒数即是最大分母。

此外，题目还要求分母 ≤

3.选取最优答案

同一个分数的拆分方法有多组，那么对于每一组拆分，我们都希望每个分数尽量大，即分母尽量小。

随后，我们对于每次得到的答案都要进行比较取最优。

4.处理约分

进行到每一步都尽量约分，以便处理特殊情况。

tyepdef long long ll; //将long long定义为ll
ll gcd (ll a, ll b) { //取最大公约数
	return b==0?a:gcd(b, a%b);
}

确定了以上规则，我们还需要分析对于搜索的限制。

分析搜索

1.搜索的层数

分解式的分数个数，既是对应搜索的层数，本题目要求分解量尽量小，通过迭代深入搜索控制分解数量。

创建全局变量dep,用于控制分解层数，并创建其他题目所需的变量。

ll a, b, dep, t[110], ans[110];  // a, b输入  dep第几个式子   t[]存放分解出来的分母

int main() {                     // 主函数
    //控制分解的代码
    for (dep = 1; true; dep++) { // 开始分解，利用dep控制层数
        dfs(ll(a / g), ll(b / g), 0);
    }

2.参数

newa -- 本次待分解的分子
newb -- 本次待分解的分母
step -- 当前分解到第几个位置

此时，dep-step即是我们分析时的n。对应当前阶段下，需要被分解成n个式子。

3.处理边界

当本阶段，约分后的式子分子为 1 ，那么这个分母就是候选答案，和之前的答案进行对比记录最优。

void dfs(ll newa, ll newb, ll step) {  // newa分子 newb分母 step当前分解到第几个位置
    if (step + 1 == dep) {             //到达边界
        if (newa == 1) {               //分子为1  该分母newb可能为答案
            t[step + 1] = newb;        //记录分母
            flag = 1;                  //修改标记
            if (t[step + 1] < ans[step + 1] ||
                ans[step + 1] == 0) {  //当本次得到的分母比答案更小 or 第一次找到答案时
                memcpy(ans, t, sizeof(t));  //记录答案
                //或者使用循环
                //for(int i=0; i<sizeof(t); i++) ans[i]=t[i];
            }
        }
        return;
    }
}

4.选取本次的分母

上文已经提到，每个分数的分母要尽量小。

所以要找到小于的最大分数，即分母是大于的最小整数。

在分子无法化为1的情况下，就有每次选取的分数即是 +1。

//未到边界
//可以约分 -- b/a --> 9/3 --> 3
//不能约分 -- b/a+1 --> 9/4+1 --> 3 
ll now = (newb%newa==0 ? newb/newa : newb/newa+1);
for(ll i=max(now, t[step]+1); i<=ceil(newb/newa)*(dep-step); i++) { //dep-step就是刚才说的n
	t[step+1]=i;
        //通分出新的结果传给下次计算
	ll nexta = newa*i-newb;
	ll nextb = newb*i;
	ll g=gcd(nexta, nextb);
	dfs(ll(nexta/g), ll(nextb/g), step+1);
}

最后完成输入，输出，处理搜索结束即可。

核心代码

完整搜索函数代码

void dfs(ll newa, ll newb, ll step) { //newa分子 newb分母 step当前分解到第几个位置 
        if(step+1==dep) { //到达边界 
                if (newa==1) { //分子为1  该分母newb可能为答案 
                        t[step+1]=newb; //记录分母 
                        flag=1; //修改标记 
                        if(t[step+1]<ans[step+1] || ans[step+1]==0) { //当本次得到的分母比答案更小 or 第一次找到答案时 
                                memcpy(ans, t, sizeof(t)); //记录答案
                                //或者使用循环 
//                              for(int i=0; i<sizeof(t); i++) ans[i]=t[i]; 
                        } 
                } 
                return ;
        }
        //未到边界
        //可以约分 -- b/a --> 9/3 --> 3
        //不能约分 -- b/a+1 --> 9/4+1 --> 3 
        ll now = (newb%newa==0 ? newb/newa : newb/newa+1);
        for(ll i=max(now, t[step]+1); i<=ceil(newb/newa)*(dep-step); i++) { //dep-step就是刚才说的n
                t[step+1]=i;
                ll nexta = newa*i-newb;
                ll nextb = newb*i;
                ll g=gcd(nexta, nextb);
                dfs(ll(nexta/g), ll(nextb/g), step+1);
        }         
}

完整主函数

int main(){
        cin >> a >> b;            
        ll g = gcd(a, b);                 //约分
        t[0] = 1;                     
        for (dep=1; true; dep++) {        //开始分解 
                dfs(ll(a/g), ll(b/g), 0);
                if(flag) {
                        break;
                }
        }
        for (int i=1; i<=dep; i++){       //输出
                cout << ans[i] << " ";
        }
}