1062 最简分数 (20 分)
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
解题思路：
Mara: 这些分数的题目做来做去就是一堆整数加减乘除，有劲吗？
Jack: 有劲啊，我最喜欢整数了，可以用指头感受的才是真实的。
Mara: 少废话了，这题怎么做啊 ？难道从 1 / K 到 (K - 1) / K 一个一个的变成小数去比大小，这靠谱吗？
Jack: 题目里面有两个条件啊， 一是要大小位于两个分数之间，二是要求是最简分数。最简分数什么意思，分子和分母不能再约分，不能约分什么意思，没有TM的公约数了，没有公约数了什么意思，TM的最大公约数是1 啊。怎么求两个数的最大公约数啊，TM的欧几里得辗转相除啊。还有你想和小数TM的比大小，那能比的准吗？分数是什么，分数乘以分母就都是整数，通分呐，通分完了之后用整数比大小不就的了吗。把问题转化成你熟悉的模式，对，基本就是这样。
Mara: 你TM的敢吼我，我问你，两个分数之间到底是开区间还是闭区间。
Jack: 我怎么知道，题目里面又TM没说，写个程序试呗。
Mara: 我就知道！
Jack: 你知道什么，试出来了，是开区间。
Mara: ╭(╯^╰)╮ ╭(╯^╰)╮ ╭(╯^╰)╮ ╭(╯^╰)╮
Jack: (ﾉ"◑ ◑)ﾉ"(｡•́︿•̀｡)(ﾉ"◑ ◑)ﾉ"(｡•́︿•̀｡)(ﾉ"◑ ◑)ﾉ"(｡•́︿•̀｡)(ﾉ"◑ ◑)ﾉ"(｡•́︿•̀｡)
代码：
def main():
temp = [x for x in input().split()]
# 以字符串列表的形式接收输入的两个分数和一个整数，形如['7/18', '13/20', '12']
N1, M1 = (int(x) for x in temp[0].split('/'))
N2, M2 = (int(x) for x in temp[1].split('/'))
# 分别获取两个分数的分子和分母
K = int(temp[2])
# 分母 K
# 将N1/M1, N2/M2, X/K通分，通分后仍满足 X/K 位于两个分数之间。此时分母相
# 同，只需要确定分子的上下界就可以找到所有在这个范围内的分数。
minn = min(N1 * M2 * K, N2 * M1 * K)
maxx = max(N1 * M2 * K, N2 * M1 * K)
# 由于题目中没有给出N1/M1 N2/M2之间的大小关系，所以我们需要自己确定最小值和最大值
answer = []
#print(minn, maxx)
for x in range(1, K):
# 可能的答案有1/K ...... K-1 / k, 来，让我们遍历这个序列
if between(minn, maxx, x * M1 * M2) and gcd(K, x) == 1:
# 如果这个分数在给定的范围内，而且分子和分母的最大公约数是1，即是满
# 足条件的最简分数。
# x * M1 * M2 是通分之后的结果。注意我们这里先判断了这个分数是否在
# 给定的范围内，如果是的话，由于 and 的短路原则就不必再计算 最大公约
# 数，这样就能减少一些计算。
answer.append('{}/{}'.format(x, K))
else:
#print("gcd {} {}".format(K, x), gcd(K, x), )
pass
print(" ".join(answer))
# 使用join方法将字符串拼接起来并输出答案
def gcd(a, b):
# 辗转相除法求两个非负整数的最大公约数
if b == 0:
return a
else:
return gcd(b, a % b)
def between(minn, maxx, x):
# 判断 x 是否在(minn, maxx)这个区间内
if x > minn and x < maxx:
return True
else:
return False
if __name__ == '__main__':
main()
易错点：
- 经测试得，题目中两个分数之间是指开区间而非闭区间。
- 如果用浮点数去存储分数，要考虑浮点误差带来的影响。
总结：
- 二进制喜欢整数，我也是。有时候我们解决的问题并不是问题直接呈现的样子，题目描述往往只是表面的展示，解题的每种方式都是看待这个问题的一种角度。同样的，平凡的每一天都可以用不同的角度去打量。人们往往没有他们所想的那样幸福或者不幸，我们只是用夸张来掩盖平凡庸俗的事实罢了。所以，请放肆一点，嚣张一点，勇敢一点，毕竟我们只活一次。