「PAT乙级真题解析」Basic Level 1062 最简分数 (问题分析+完整步骤+伪代码描述+提交通过代码)
题目给定两个有理数分数形式的分子和分母, 以及一个整数K, 要求给出介于两个有理数之间的最简分数, 且分数的分母得是整数. 因为给定了一个整数作为分母, 我们要查找的范围其实是分子为1到K, 分母为K的K个分数.
#算法#数据结构#c语言#pat考试#需求分析
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
PAT乙级BasicLevelPractice 1062 最简分数
问题分析
题目给定两个有理数分数形式的分子和分母, 以及一个整数K, 要求给出介于两个有理数之间的最简分数, 且分数的分母得是整数. 因为给定了一个整数作为分母, 我们要查找的范围其实是分子为1到K, 分母为K的K个分数.
完整描述步骤
- 获取输入给定的两个分数的分子和分母: N1, M1, N2, M2
- 获取输入指定的分母值: K
- 检查给定的两个分数的大小:
- 如果 N1 / M1 > N2 / M2: 则交换两个分数的值, 确保N1 / M1 < N2 / M2
- 对于分子i从1到K:
- 对于分数 i / K, 如果 N1 / M1 < i / K < N2 / M2 且 i和K的最大公因子是1,
- 则输出分数 i / K
- 对于分数 i / K, 如果 N1 / M1 < i / K < N2 / M2 且 i和K的最大公因子是1,
伪代码描述
- get input: N1, M1, N2, M2;
- get input: K;
- if N1 / M1 > N2 / M2:
- change value of N1 / M1 and N2 / M2;
- for i in range(1, K):
- if N1 / M1 < i / K < N2 / M2 and gcd(i, k) == 1:
- print(i / k);
- if N1 / M1 < i / K < N2 / M2 and gcd(i, k) == 1:
注意事项
- 题设没有保证 N1/M1 < N2/M2, 所以需要检查两个分数的大小
- 等于N1/M1 或 N2/M2的数不满足题设的要求, 不能输出, 而浮点数的相等比较不是用"=="而是检查差值是否小于小误差(10^-6)
完整提交代码
/*
# 问题分析
题目给定两个有理数分数形式的分子和分母, 以及一个整数K,
要求给出介于两个有理数之间的最简分数, 且分数的分母得是整数.
因为给定了一个整数作为分母, 我们要查找的范围其实是分子为1到K, 分母为K的K个分数.
# 完整描述步骤
1. 获取输入给定的两个分数的分子和分母: N1, M1, N2, M2
2. 获取输入指定的分母值: K
3. 检查给定的两个分数的大小:
- 如果 N1 / M1 > N2 / M2: 则交换两个分数的值, 确保N1 / M1 < N2 / M2
4. 对于分子i从1到K:
- 对于分数 i / K, 如果 N1 / M1 < i / K < N2 / M2 且 i和K的最大公因子是1,
- 则输出分数 i / K
# 伪代码描述
1. get input: N1, M1, N2, M2;
2. get input: K;
3. if N1 / M1 > N2 / M2:
- change value of N1 / M1 and N2 / M2;
4. for i in range(1, K):
- if N1 / M1 < i / K < N2 / M2 and gcd(i, k) == 1:
- print(i / k);
# 注意事项
1. 题设没有保证 N1/M1 < N2/M2, 所以需要检查两个分数的大小
2. 等于N1/M1 或 N2/M2的数不满足题设的要求, 不能输出, 而浮点数的相等比较不是用"=="而是检查差值是否小于小误差(10^-6)
*/
# include<stdio.h>
# define EPS 1E-6
int gcd(int a, int b){
return a % b == 0 ? b : gcd(b, a % b);
}
int main(){
int N1, M1, N2, M2;
int K;
scanf("%d/%d %d/%d %d", &N1, &M1, &N2, &M2, &K);
double rational_number_1 = (double)N1 / M1;
double rational_number_2 = (double)N2 / M2;
if (rational_number_2 < rational_number_1){
double temp = rational_number_2;
rational_number_2 = rational_number_1;
rational_number_1 = temp;
}
double current_ration_number;
int count = 0;
for (int i = 0; i < K; i++){
current_ration_number = (double)i / K;
if (current_ration_number > rational_number_2 || rational_number_2 - current_ration_number < EPS)
break;
if (current_ration_number > rational_number_1 && gcd(K, i) == 1)
{
if (count == 0){
printf("%d/%d", i, K);
} else {
printf(" %d/%d", i, K);
}
count++;
}
}
printf("\n");
return 0;
}