1 模數(shù)“模”是指一個(gè)計(jì)量系統(tǒng)的計(jì)數(shù)范圍。如時(shí)鐘等。計(jì)算機(jī)也可以看成一個(gè)計(jì)量機(jī)器，它也有一個(gè)計(jì)量范圍，即都存在一個(gè)“模”。例如： 時(shí)鐘的計(jì)量范圍是0～11，模=12。表示n位的計(jì)算機(jī)計(jì)量范圍是0～2^(n)-1，模=2^(n)。 “?！睂?shí)質(zhì)上是計(jì)量器產(chǎn)生“溢出”的量，它的值在計(jì)量器上表示不出來，計(jì)量器上只能表示出模的余數(shù)。任何有模的計(jì)量器，均可化減法為加法運(yùn)算。 例如：假設(shè)當(dāng)前時(shí)針指向10點(diǎn)，而準(zhǔn)確時(shí)間是6點(diǎn)，調(diào)整時(shí)間可有以下兩種撥法：一種是倒撥4小時(shí)，即：10-4=6；另一種是順撥8小時(shí)：10+8=12+6=6 在以12模的系統(tǒng)中，加8和減4效果是一樣的，因此凡是減4運(yùn)算，都可以用加8來代替。對(duì)“?！倍?，8和4互為補(bǔ)數(shù)。實(shí)際上以12模的系統(tǒng)中，11和1，10和2，9和3，7和5，6和6都有這個(gè)特性。共同的特點(diǎn)是兩者相加等于模。 對(duì)于16進(jìn)制，16就是這個(gè)進(jìn)制系統(tǒng)中的模，其使用的字符只有：0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F。 對(duì)于8進(jìn)制，8就是這個(gè)進(jìn)制系統(tǒng)中的模，其使用的字符只有：0,1,2,3,4,5,6,7。 對(duì)于2進(jìn)制，2就是這個(gè)進(jìn)制系統(tǒng)中的模，其使用的字符只有：0,1。 對(duì)于計(jì)算機(jī)，其概念和方法完全一樣。n位計(jì)算機(jī)，設(shè)n=8， 所能表示的最大數(shù)是11111111，若再加1成為100000000(9位），但因只有8位，最高位1自然丟失。又回了00000000，所以8位二進(jìn)制系統(tǒng)的模為2^8。在這樣的系統(tǒng)中減法問題也可以化成加法問題，只需把減數(shù)用相應(yīng)的補(bǔ)數(shù)表示就可以了。把補(bǔ)數(shù)用到計(jì)算機(jī)對(duì)數(shù)的處理上，就是補(bǔ)碼。 2 素?cái)?shù)質(zhì)數(shù)（prime number）又稱素?cái)?shù)，有無限個(gè)。質(zhì)數(shù)定義為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。 int isPrime(int n){ if(n<= 1)// 小于等于1的整數(shù)不可能是素?cái)?shù) return 0; if(n == 2); // 2 是素?cái)?shù) return 1; if(n%2 == 0); // 能被2整除的其他整數(shù)都不是素?cái)?shù) return 0; int limit = (int)sqrt((double)n)+1; for(int i = 3; i <= limit; i=i+2) { if(n % i == 0) return 0; } return 1;} isPrime沒有必要枚舉所有的因子。 I 只要發(fā)現(xiàn)任何一個(gè)大于1小于n的因子，就能停下來報(bào)告n不是素?cái)?shù)。 II 如果n能被2整除，直接報(bào)告n不是素?cái)?shù)。如果n不能被2整除，那么它也不可能被4或6或其他偶數(shù)整除。因此，isPrime只需要檢查2和奇數(shù)（由3開始，步長(zhǎng)為2）。但注意有個(gè)特例，2能被2整除，但2是素?cái)?shù)。 III 如果n不是素?cái)?shù)，則必有一個(gè)因子小于√n 。因此不需要檢查到n為止。只需檢查到√n 。 因?yàn)槿绻鹡能被2~n-1之間任一整數(shù)整除，其二個(gè)因子必定有一個(gè)小于或等于√n，另一個(gè)大于或等于√n。例如24可以表示為：2*12、3*8、4*6，前面的因子小于√24，后面的因子大于√24，檢驗(yàn)出了小因子，即可判斷n是否為素?cái)?shù)，就像邏輯運(yùn)算的短路求值。 3 用輾轉(zhuǎn)相除法（又名歐幾里德算法）求最大公約數(shù)和最小公倍數(shù)設(shè)c是a、b的最大公約數(shù)，記為c=gcd(a,b)，a>=b 令r=a mod b 要證明b與r的最大公約數(shù)也是c 設(shè)a=kc，b=jc，則k、j互素，否則c不是最大公約數(shù)。 設(shè)m為任一整數(shù)。 據(jù)上，r=a-mb=kc-mjc=(k-mj)c 可知r也是c的倍數(shù)，且k-mj與j互素，否則與前述k，j互素矛盾。 由此可知，b與r的最大公約數(shù)也是c，即gcd(a,b)=gcd(b,a mod b)。 這樣就可以通過不斷求余、不斷互換，直到余數(shù)為零，最后的結(jié)果就是最大公約數(shù)。 I a ÷ b，令r為所得余數(shù)（0≤r ） II 互換：置 a←b，b←r，并返回第一步。 最小公倍數(shù)=兩數(shù)之積除于它們的最大公約數(shù)。 實(shí)例： 輸入兩個(gè)正整數(shù)m和n，求其最大公約數(shù)和最小公倍數(shù)。 #include<iostream>using namespace std;int isPrime(int n);int main(){ int a,b,t,r; printf('請(qǐng)輸入兩個(gè)數(shù)字：\n'); scanf('%d %d',&a,&b); if(a<b) {t=b;b=a;a=t;} r=a%b; int n=a*b; while(r!=0) { a=b; b=r; r=a%b; } printf('這兩個(gè)數(shù)的最大公約數(shù)是%d，最小公倍數(shù)是%d\n',b,n/b); system('pause'); return 0;}/*請(qǐng)輸入兩個(gè)數(shù)字：18 24這兩個(gè)數(shù)的最大公約數(shù)是6，最小公倍數(shù)是72/*同樣對(duì)于兩個(gè)數(shù)1,000,005和1,000,000，用歐幾里得算法只需要執(zhí)行兩次循環(huán)體。 －End－ |
|
|
