左嘉

用户名：zuojia

访问量：82651

签　名：

等　　级
排　　名	4
经　　验	33592
参赛次数	226
文章发表	72
年　　龄	40
在职情况	在职
学　　校	北京理工大学
专　　业

　　自我简介：

TA的其他文章

Dinner-题解（C++代码）
浏览：456

信息学奥赛一本通T1444-埃及分数-题解（C语言代码）
浏览：483

用Python爬取本站离线题库
浏览：700

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

信息学奥赛一本通T1444-埃及分数-题解（C语言代码）

　　作者: 左嘉　　　　发表时间：2020-09-13 23:50:13 浏览：483　|　评论：1　

原题链接：信息学奥赛一本通T1444-埃及分数

#### 解题思路：
##### 头部：
```c
#include <stdio.h>
#include <string.h>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define LL long long
#define N 205
LL deepest;
LL now[N];
LL last[N];
```
##### 求最大公约数：
```c
LL GCD(LL a, LL b)
{
    LL c;
    while (b)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
```
##### 判断最小分数的更好分母：
```c
int better(LL step)
{
    if (last[step] == -1 || now[step] < last[step])
        return 1;
    else return 0;
}
```
##### 找到合适的分母：
```c
LL firstFit(LL x, LL y)
{
    for (LL i = 2;; i++)
        if (y < x * i)
            return i; //找到分母i使1/i小于x/y
}
```
#### 注意事项：
[深度优先搜索并剪枝](https://blog.csdn.net/u011815404/article/details/97647923 "深度优先搜索并剪枝")
```c
int dfs(LL step, LL minn, LL x, LL y)
{
    if (step == deepest)
    {
        if (y % x)
            return 0;
        else
        {
            now[step] = y / x;
            if (better(step))
                memcpy(last, now, sizeof(now)); //更优解
            return 1;
        }
    }
    minn = max(minn, firstFit(x, y)); //更小分数的更大分母
    int flag = 0;
    for (LL i = minn;; i++)
    {
        if ((deepest - step + 1) * y <= x * i)
            break; //若(deepest-step+1)*(1/i)<=x/y可剪枝
        now[step] = i;
        LL ny = y * i;
        LL nx = x * i - y;
        LL gcd = GCD(nx, ny);
        if (dfs(step + 1, minn + 1, nx / gcd, ny / gcd))
            flag = 1;
    }
    return flag;
}
```
#### 参考代码：
```c
int main()
{
    LL n, m;
    scanf("%lld%lld", &n, &m);
    for (deepest = 1;; deepest++)
    {
        LL limit = firstFit(n, m);
        memset(now, 0, sizeof(now));
        memset(last, -1, sizeof(last));
        if (dfs(0, limit, n, m))
            break;
    }
    for (LL i = 0; i <= deepest; i++)
        printf("%lld ", last[i]);
    return 0;
}
```

0.0分

4 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

sum666

Very Good!

2020-09-16 21:28:30

左嘉

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C++代码）

C语言考试练习题_一元二次方程（C语言代码）

Lucky Word （C++代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

信息学奥赛一本通T1444-埃及分数-题解（C语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

字符串的输入输出处理（C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

1009题解

P1000 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

左嘉

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C++代码）

C语言考试练习题_一元二次方程 （C语言代码）

Lucky Word （C++代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

信息学奥赛一本通T1444-埃及分数-题解（C语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

字符串的输入输出处理 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

1009题解

P1000 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

字符串的输入输出处理（C语言代码）