前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >1062 最简分数 (20 分)

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 个输出。

输入样例:

代码语言:javascript
复制
7/18 13/20 12

输出样例:

代码语言:javascript
复制
5/12 7/12

【我的代码】

代码语言:javascript
复制
 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的,本来就只是想骗一点分,没想到尽然给通过了。

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

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

【参考代码】

代码语言:javascript
复制
 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没问题了。

代码语言:javascript
复制
 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 条评论
热度
最新
推荐阅读
目录
  • 输入格式:
  • 输出格式:
  • 输入样例:
  • 输出样例:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档