Re: [問題] 最大公因數
※ 引述《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
推
04/16 09:50, , 1F
04/16 09:50, 1F
討論串 (同標題文章)