一.輾轉相除法
1.求最大公因子的方法(a,b) = (b,c)稱為輾轉相除法
??Ⅰ.其中a = qb + c; (a,b)為a,b的最大公因子，
??Ⅱ.簡化了求最大公因子的作業量，因為任意整數和0的公因子為其本身，若余數c=0時，b即為最大公因子，
2.輾轉相除法的證明：
??Ⅰ.因為(a,b)整除a，(a,b)整除b，根據整除的性質（即a整除b，a整除c，可以得到a整除mb+mc ）可以得到(a,b)整除c，所以有(b,c)>=(a,b)（因為(a,b)是c的因子，也是b的因子，所以(b,c)>=(a,c)，)，同理可得c<=(a,b)，所以可以得到結果：(a,b) = (b,c)
3.輾轉相除法的遞回實作
int digui(int a , int b){
if(b==0) return b;
return digui(b,a%b);
}
二.進制表示法
??Ⅰ.任何整數n都可以表示為a進制：r(t)*a^t + r(t-1)a^(t-1) + … +r1a + r0.
??Ⅱ.證明：對于整數n，可表示為 n = q0 * a + r0，現在將q0分解 q0 = q1 * a + r1，原式等于 n = (q1 * a + r1) * a + r0，遞推可得到存在 0 <= q(t-1) < a，使得 q(t-1) = rt，所以可以得到Ⅰ中的式子，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/184967.html
標籤：其他
上一篇：Oracle 非常詳細的 PL/SQL入門教程,PL/SQL語法格式/回圈陳述句/條件判斷/例外處理
下一篇：MySQL性能調優【一】