1062 最简分数（20 分)

可爱见见

发布于 2019-10-25 01:52:12

4200

发布于 2019-10-25 01:52:12

文章被收录于专栏：卡尼慕

1062 最简分数 (20 分)

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

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

输入格式：

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

输出格式：

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

输入样例：

7/18 13/20 12

输出样例：

5/12 7/12

【我的代码】

 1#include <iostream>
 2#include <vector>
 3using namespace std;
 4bool judge(int N, int M){
 5    for(int i = 2 ; i < M; i++){
 6        if(((M % i) == 0) && ((N % i) == 0)){
 7            return false;
 8        }
 9    }
10    return true;
11}
12int main(){
13    int N1,M1,N2,M2;
14    int K;
15    scanf("%d/%d %d/%d %d",&N1,&M1,&N2,&M2,&K);
16    float ans1,ans2;
17    ans1 = (float)N1 / (float)M1;
18    ans2 = (float)N2 / (float)M2;
19    if(ans1 > ans2){
20        float tmp = ans1;
21        ans1 = ans2;
22        ans2 = tmp;
23    }
24    int K1 = 1;
25    float ans3;
26    vector<int> res;
27    for(; K1 <= K; K1++){
28        ans3 = (float) K1 / (float) K;
29        if(ans3 > ans1 && ans3 < ans2 && judge(K1,K))
30            res.push_back(K1);
31        if(ans3 == 1)
32            break;
33    }
34    int len = res.size();
35    for(int i = 0; i < len; i++){
36        printf("%d/%d",res[i],K);
37        if(i != len - 1)
38            cout<<" ";
39    }
40    return 0;
41}

【我的思路】

其实算是蒙对的，为什么这么说呢，因为我假设了答案是恒小于0的，本来就只是想骗一点分，没想到尽然给通过了。

但是后面自己测试的时候就发现：

没有结果！毕竟是偷分的方法。

【参考代码】

 1#include <iostream>
 2using namespace std;
 3int gcd(int a, int b){
 4    return b == 0 ? a : gcd(b, a % b);
 5}
 6int main() {
 7    int n1, m1, n2, m2, k;
 8    scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k);
 9    if(n1 * m2 > n2 * m1) {
10        swap(n1, n2);
11        swap(m1, m2);
12    }
13    int num = 1;
14    bool flag = false;
15    while(n1 * k >= m1 * num) num++;
16    while(n1 * k < m1 * num && m2 * num < n2 * k) {
17        if(gcd(num, k) == 1) {
18            printf("%s%d/%d", flag == true ? " " : "", num, k);
19            flag = true;
20        }
21        num++;
22    }
23    return 0;
24}

很显然，使用这个方法就不会出现上面的情况。

所以我错就是在范围上面我取了他的子集。这里第15行保证了分子的起始位置，然后在16行开始进行循环，使用乘法而非除法。另外，这里判断是否存在公因数使用的方法是辗转相除法。

【更改】

于是我更改了代码，ummm没问题了。

 1#include <iostream>
 2#include <vector>
 3using namespace std;
 4bool judge(int N, int M){
 5    for(int i = 2 ; i < 1000; i++){
 6        if(((M % i) == 0) && ((N % i) == 0)){
 7            return false;
 8        }
 9    }
10    return true;
11}
12int main(){
13    int N1,M1,N2,M2;
14    int K;
15    scanf("%d/%d %d/%d %d",&N1,&M1,&N2,&M2,&K);
16    if(N1 * M2 > N2 * M1){
17        swap(N1,N2);
18        swap(M1,M2);
19    } 
20    int K1 = 1;
21    vector<int> res;
22    for(; K1 <= 1000; K1++){
23        if(K1 * M1 > K * N1 && K1 * M2 < K * N2 && judge(K1,K))
24            res.push_back(K1);
25    }
26    int len = res.size();
27    for(int i = 0; i < len; i++){
28        printf("%d/%d",res[i],K);
29        if(i != len - 1)
30            cout<<" ";
31    }
32    return 0;
33}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-10-24，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自卡尼慕微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度