C++分数转换步数程序纠错:a/b到c/d的计数实现问题
定位到的具体错误
三个硬伤直接导致测试用例跑不出正确结果:
- 约分逻辑写反了顺序
原代码在分子分母各加1之后,先拿当时的a、b算gcd把a除了,a已经被修改成约分后的值,后面再算b的约分数时,用的是改完的a和原来的b重新算gcd,结果完全不对。
举个实际例子:加1后a=5、b=10,正确gcd是5,约分结果应该是1/2。按原代码的执行流:- 先算gcd(5,10)=5,把a改成5/5=1
- 再算b的除数是gcd(现在的a=1, 原来的b=10)=1,最后b还是10
算出来的结果是1/10,和正确值差了十万八千里。
- 循环条件完全不匹配业务逻辑
原代码写的循环触发条件是while (b<d),但每步操作后要对分数约分,分母是可以变小的(比如10/5=2)。拿测试用例来说,初始b=6,目标d=3,6<3本身就不成立,循环直接被跳过,一行代码都不执行,程序跑完根本没有输出。 - 缺失全流程的相等判断
既没在程序开头判断“初始分数就等于目标”的情况,也没在每步操作完检查是否到达目标,哪怕逻辑跑通了,到了目标点也不知道要输出结果。
修复方法
- 修正约分顺序:拿到加1后的a、b,先一次性算出两个数的最大公约数,再同步给a、b做除法,全程不改动计算gcd用的原始值。
- 换正确的循环判断依据:因为每步操作后得到的分数值是严格递增的,当当前分数比目标大的时候,不管怎么操作都不可能再回到目标值,直接返回0;只要当前值比目标小,就继续执行操作,完全不需要用分母的大小当判断条件。
- 把相等判断补在初始状态、每步操作完成后的节点上,一旦匹配目标就立刻输出当前步数。
修复后代码
#include <iostream> using namespace std; int gcd(int x, int y) { while(y) { int r = x % y; x = y; y = r; } return x; } int main() { int a, b, c, d; cin >> a >> b >> c >> d; int step = 0; // 初始状态直接匹配的情况 if (a * d == b * c) { cout << step; return 0; } // 只要当前分数值小于目标,就继续操作 while (a * d < b * c) { a++; b++; // 先算统一的公约数,再同步约分 int common_div = gcd(a, b); a /= common_div; b /= common_div; step++; // 操作完立刻检查是否到达目标 if (a * d == b * c) { cout << step; return 0; } } // 跳出循环说明当前分数已经大于目标,永远无法到达 cout << 0; return 0; }
测试用例核对
输入1 6 2 3时的执行流程:
- 初始1/6 < 2/3,开始操作
- 第1步:2/7,值仍小于目标,步数1
- 第2步:3/8,值仍小于目标,步数2
- 第3步:4/9,值仍小于目标,步数3
- 第4步:5/10,gcd为5,约分后1/2,值仍小于目标,步数4
- 第5步:2/3,和目标匹配,输出5,和预期完全一致。
内容的提问来源于stack exchange,提问作者user14258654
相关产品推荐
相关产品推荐

