本文共 3314 字，大约阅读时间需要 11 分钟。
我的 PAT-Basic 代码仓：
原题链接：
题目描述：
知识点：欧几里得最大公约数算法
思路一：通分后比较分子
最简分数的定义：分子分母的最大公约数为1，这涉及到欧几里得最大公约数算法。关于欧几里得最大公约数算法的伪码，可以参考中的分析。
将分数的分母都变成M1M2K。
题目规定了给出的所有整数不超过1000，但如果用这个思路，M1M2K最大值为10^9，再加上题给的分数可能是假分数，分子不一定比分母要小，分子可能会超出int型的范围，我们需要用long型变量存储。否则无法通过测试点2。
本题有一个坑点：
N1/M1不一定比N2/M2要小，可能需要我们换一个顺序。如果不考虑到这一点，无法通过测试点1。
时间复杂度和空间复杂度的分析对于本题来说意义不大。
C++代码：
#include
int calculateIndexSlide(string s);long calculateNumerator(string s);long calculateDenominator(string s);long gcd(long num1, long num2);
int main() {string input1;string input2;cin >> input1 >> input2;
long N1 = calculateNumerator(input1);long M1 = calculateDenominator(input1);long N2 = calculateNumerator(input2);long M2 = calculateDenominator(input2);long K;cin >> K;long minNumerator = K * M2 * N1;long maxNumerator = K * M1 * N2;if(minNumerator > maxNumerator) { long temp = minNumerator; minNumerator = maxNumerator; maxNumerator = temp;}vector numerators;for(long i = 1;; i++) { if(M1 * M2 * i >= maxNumerator) { break; } if(gcd(K, i) == 1 && M1 * M2 * i > minNumerator) { numerators.push_back(i); }}for(int i = 0; i < numerators.size(); i++) { cout << numerators[i] << "/" << K; if(i != numerators.size() - 1) { cout << " "; }}return 0; }
int calculateIndexSlide(string s) {for(int i = 0; i < s.length(); i++) {if(s[i] == '/') {return i;}}return -1;}
long calculateNumerator(string s) {int indexSlide = calculateIndexSlide(s);long N = 0;for(int i = 0; i < indexSlide; i++) {N = N * 10 + (s[i] - '0');}return N;}
long calculateDenominator(string s) {int indexSlide = calculateIndexSlide(s);long M = 0;for(int i = indexSlide + 1; i < s.length(); i++) {M = M * 10 + (s[i] - '0');}return M;}
long gcd(long num1, long num2) {if(num2 == 0) {return num1;}return gcd(num2, num1 % num2);}
C++解题报告：
思路二：直接用浮点数进行比较
思路一这么麻烦，还需要通分，何不直接用浮点数进行比较呢？这样也就避免了int型数据越界的问题。
C++代码：
#include
int calculateIndexSlide(string s);int calculateNumerator(string s);int calculateDenominator(string s);int gcd(int num1, int num2);
int main() {string input1;string input2;cin >> input1 >> input2;
int N1 = calculateNumerator(input1);int M1 = calculateDenominator(input1);int N2 = calculateNumerator(input2);int M2 = calculateDenominator(input2);int K;cin >> K;double min = 1.0 * N1 / M1;double max = 1.0 * N2 / M2;if(min > max) { double temp = min; min = max; max = temp;}vector numerators;for(int i = 1;; i++) { if(1.0 * i / K >= max) { break; } if(gcd(K, i) == 1 && 1.0 * i / K > min) { numerators.push_back(i); }}for(int i = 0; i < numerators.size(); i++) { cout << numerators[i] << "/" << K; if(i != numerators.size() - 1) { cout << " "; }}return 0; }
int calculateIndexSlide(string s) {for(int i = 0; i < s.length(); i++) {if(s[i] == '/') {return i;}}return -1;}
int calculateNumerator(string s) {int indexSlide = calculateIndexSlide(s);int N = 0;for(int i = 0; i < indexSlide; i++) {N = N * 10 + (s[i] - '0');}return N;}
int calculateDenominator(string s) {int indexSlide = calculateIndexSlide(s);int M = 0;for(int i = indexSlide + 1; i < s.length(); i++) {M = M * 10 + (s[i] - '0');}return M;}
int gcd(int num1, int num2) {if(num2 == 0) {return num1;}return gcd(num2, num1 % num2);}
转载地址：http://ihli.baihongyu.com/