作者keeperkai (keeperkai)
看板java
标题Re: [问题] 最大公因数
时间Thu Apr 15 22:22:02 2010
※ 引述《sie (︿╴︿")》之铭言：
: 小弟的原程式码有点长
: 以下是部分节录:
: (numerator>=denominator)
: ---------------------------------------------
: p = numerator;
: q = denominator;
: m = 1;
: for(i=1;m>0;i++)
: {
: r = p/q;
: m = p%q;
: if(m==0)
: HCF = q;
: else
: p = q;
: q = r;
: }
: numerator = numerator/HCF;
: denominator = denominator/HCF;
: String fraction = numerator+"/"+denominator;
: System.out.println(fraction);
第一点: q=r...如果我记得没错的话搌转相除是gcd(p,q)=gcd(q,p%q)而非跟
商数再做gcd，所以应该是q=m
依照你演算法的写法，各个时段变数的值如下:
initial:p=14 q=5
i=1: p=5 q=r=14/5=2
i=2: p=2 q=r=5/2=2
i=3: 触动if(2%2=0) ==> HCF=2 离开回圈
numerator=14/2=7
denominator=5/2=2
结果当然是"7/2"...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 203.222.23.95
1F：推 sie:感恩 04/16 09:50