PAT B1062 最简分数(C++)

发表于 | 分类于 | |
字数统计: 298 字 | 阅读时长 ≈ 1 分钟
PAT甲级目录 | PAT乙级目录

题目描述

B1062 最简分数

解题思路

分数化简可以利用最大公约数，最大公约数为 1 则已经是最简分数。

易错点

  • 第一个分数有可能大于第二个分数
  • 结果的分数值介于两个分数之间，等号没有取到

也许陌生的知识点

  • int gcd(int a, int b){ return b == 0 ? abs(a) : gcd(b, a % b);}
    • 获取最大公约数
  • swap(n1, n2)
    • 交换两个变量的值
    • 所需头文件： algorithm
  • cmath 中的取整函数
  • y = ceil(x)
    • 向下取整
  • y = floor(x)
    • 向上取整
  • y = round(x)
    • 四舍五入

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int gcd(int a, int b){ return b == 0 ? abs(a) : gcd(b, a % b);}
int main(){
  int n1, m1, n2, m2, K, cnt = 0;
  scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &K);
  if(n1 * m2 > n2 * m1){ // 当第一个分数大于第二个分数
    swap(n1, n2);
    swap(m1, m2);
  }
  for(int i = ceil(1.0 * n1 / m1 * K); 1.0 * i / K < 1.0 * n2 / m2; i++){
    if(gcd(i, K) == 1){// 为最简分数
      if(cnt != 0) printf(" ");
      printf("%d/%d", i, K);
      cnt++;
    }
  }
  return 0;
}