PAT乙级1062 || 最简分数（详解，C/C++示例，测试点分析）

Posted on In

最简分数

题目描述

一个分数一般写成两个整数相除的形式：N/M，其中 M 不为0。最简分数是指分子和分母没有公约数的分数表示形式。

现给定两个不相等的正分数 N1/M1 和 N2/M2，要求你按从小到大的顺序列出它们之间分母为 K 的最简分数。

输入格式

输入在一行中按 N/M 的格式给出两个正分数，随后是一个正整数分母 K，其间以空格分隔。题目保证给出的所有整数都不超过 1000。

输出格式

在一行中按 N/M 的格式列出两个给定分数之间分母为 K 的所有最简分数，按从小到大的顺序，其间以 1 个空格分隔。行首尾不得有多余空格。题目保证至少有 1 个输出。

输入样例

1
7/18 13/20 12

输出样例

1
5/12 7/12

问题解决

解题思想

分数定义为结构体类型，写一个求a,b,c的最小公倍数的函数lcm()，我们都知道用辗转相除法求最大公约数的方法gcd()，求得a与b的最大公约数d后，它们的最小公倍数即为a * b / d。求三个数的最小公倍数可在此基础上拓展。

设m为两个分数的分母与k三者的最小公倍数，将两个分数按分母为m进行通分，通分后设较大分子为high，较小分子为low，从low + 1出发一直遍历到high - 1，对每种分子的取值情况进行相应的判断（见下方代码2），然后按格式输出即可。

下面的代码1是我一开始写的代码，虽然测试系统的测试点都能通过，但是测试点4竟耗时100ms有余（代码2只用6ms），从代码1也可看出，对每种情况都要进行化简，是很耗费时间的，效率不高。

坑点提醒

坑点1

给出的两个分数的大小顺序是不确定的，需要你判断一下谁大谁小。

坑点2

题目要求列出两个分数之间的分母为k的最简分数，不包括这两个分数。

代码示例（C/C++）

代码1（较耗时）

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
#include <iostream>
#include <cstdio>
using namespace std;
int gcd(int a, int b);
int lcm(int a, int b, int c);
void Simplify(int &a, int &b);
struct fraction //分数
{
    int a,b;    //分子和分母
};
int main()
{
    fraction f1, f2;
    int k;
    scanf("%d/%d%d/%d%d",&f1.a,&f1.b,&f2.a,&f2.b,&k);
    int m = lcm(f1.b, f2.b, k);
    int low = m / f1.b * f1.a, high = m / f2.b * f2.a;
    if(low > high) {
        swap(low, high);
    }
    int flag = 1;
    for(int i = low + 1; i < high; i++) {
        int tmp1 = i, tmp2 = m;
        Simplify(tmp1, tmp2);
        if(tmp2 == k) {
            if(flag) {
                printf("%d/%d", tmp1, tmp2);
                flag = 0;
            }
            else {
                printf(" %d/%d", tmp1, tmp2);
            }
        }
    }
    return 0;
}
//求a与b的最大公约数
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b,a % b);
}
//求a,b,c的最小公倍数
int lcm(int a, int b, int c)
{
    int m1 = a / gcd(a, b) * b;
    int m2 = b / gcd(b, c) * c;
    return m1 / gcd(m1, m2) * m2;
}
//化简分数
void Simplify(int &a, int &b)
{
    int d = gcd(a, b);
    a /= d;
    b /= d;
}

代码2

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
#include <iostream>
#include <cstdio>
using namespace std;
int gcd(int a, int b);
int lcm(int a, int b, int c);
struct fraction //分数
{
    int a,b;    //分子和分母
};
int main()
{
    fraction f1, f2;
    int k;
    scanf("%d/%d%d/%d%d",&f1.a,&f1.b,&f2.a,&f2.b,&k);
    int m = lcm(f1.b, f2.b, k); //两个分数的分母与k三者的最小公倍数
    int low = m / f1.b * f1.a, high = m / f2.b * f2.a;  //两分数通分使分母为m
    if(low > high) {
        swap(low, high);    //此函数需要加上头文件 <iostream>
    }
    int flag = 1, s = m / k;
    for(int i = low + 1; i < high; i++) {
        if(i % s){  //分子不能整除s
            continue;
        }
        int tmp = i / s;
        if(gcd(tmp, k) != 1){   //分子分母（分母为12）还可以化简
            continue;
        }
        if(flag) {
            printf("%d/%d", tmp, k);
            flag = 0;
        }
        else {
            printf(" %d/%d", tmp, k);
        }
    }
    return 0;
}
//求a与b的最大公约数
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b,a % b);
}
//求a,b,c的最小公倍数
int lcm(int a, int b, int c)
{
    int m1 = a / gcd(a, b) * b;
    int m2 = b / gcd(b, c) * c;
    return m1 / gcd(m1, m2) * m2;
}

题目来源：PAT乙级1062
作者：CHEN, Yue
单位：浙江大学

稀罕作者