埃及分数-迭代加深搜索

发表于 | 分类于 | | 阅读次数:

迭代加深搜索实际上是人为规定搜索深度的DFS。从小到大枚举深度上限maxd，每次执行只考虑深度不超过maxd的结点。这样，只要解的深度有限，就一定可以在有限时间内枚举到。

对于可以用回溯法求解但解答树深度没有明显上限的题目，可以考虑使用迭代加深搜索。

埃及分数问题

在古埃及，人们使用单位分数的和（即1/a，a是自然数）表示一切有理数。例如，2/3 = 1/2 + 1/6，但不允许2/3 = 1/3 + 1/3，因为在加数中不允许有相同的。
对于一个分数a/b，表示方法有很多种，其中加数少的比加数多的好，如果加数个数相同，则最小的分数越大越好。例如，19/45 = 1/5 + 1/6 + 1/18是最优方案。
输入整数a，b（0< a < b < 500），计算最佳表达式。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
 *
 * Author : Aincrad
 *
 * Date : Thu  3 Jan 07:11:15 CST 2019
 *
 */
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3;
long long a, b;
long long ans[maxn];
long long maxd;
long long v[maxn];
bool ok;

long long get_first(long long a, long long b){
    if(b % a == 0) return b / a;
    else return b / a + 1;
}

long long gcd(long long a, long long b){
    if(b == 0) return a;
    gcd(b, a % b);
}

void dfs(int dep, long long from, long long a, long long b){
    if(dep == maxd){
        if(a * b == 0){
            for(int i = dep - 1; i >= 0; i--){
                if(ans[i] == -1 || v[i] < ans[i]){
                    memcpy(ans, v, sizeof(ans));
                    break;
                }
            }
            ok = 1;
        }
        //cout << "return" << endl;
        return;
    }
    from = max(from, get_first(a, b));
    for(long long i = from; ; i++){
        //cout << "true: " << maxd << " " << dep << " " << i << " " << a << " " << b << endl;
        if(b * (maxd - dep) < i * a){
            //cout << "cut" << endl;
            break;
        }
        long long b2 = b * i;
        long long a2 = a * i - b;
        long long g = gcd(a2, b2);
        v[dep] = i;
        //cout << "next: " << maxd << " " << dep + 1 << " " << i + 1 << " " << a2 / g << " " << b2 / g << endl;
        dfs(dep + 1, i + 1, a2 / g, b2 / g);
    }
}

int  main(){
    while(cin >> a >> b){
        for(maxd = 1; ; maxd++){
            memset(ans, -1, sizeof(ans));
            ok = 0;
            dfs(0, get_first(a, b), a, b);
            if(ok) break;
        }
        if(ok){
            cout << a << "/" << b << " = ";
            for(int i = 0; i < maxd; i++){
                cout << 1 << "/" << ans[i];
                if(i != maxd - 1) cout << " + ";
            }
            cout << endl;
        }
    }
    return 0;
}