計(jì)算代數(shù)與計(jì)算數(shù)論

1、 實(shí)驗(yàn)報(bào)告 題 目：*課程名稱：* 學(xué) 院： * 專 業(yè)： * 年 級(jí)： * 學(xué) 號(hào)： * 學(xué)生姓名： * 指導(dǎo)教師： * 成績(jī)?cè)u(píng)語(yǔ) 年 月 日目錄一、前言.4二、輾轉(zhuǎn)相除法的計(jì)算原理.4三、輾轉(zhuǎn)相除法的實(shí)例.4四、為什么用輾轉(zhuǎn)相除法能得到兩個(gè)數(shù)的最大公因數(shù).5五、多項(xiàng)式的輾轉(zhuǎn)相除法.5六、求兩個(gè)整數(shù)最大公因數(shù)的程序算法.7七、運(yùn)行結(jié)果.7八、實(shí)驗(yàn)總結(jié).9一、前言輾轉(zhuǎn)相除法， 又名歐幾里得算法（Euclidean algorithm）乃求兩個(gè)正整數(shù)之最大公因子的算法。它是已知最古老的算法， 其可追溯至3000年前。這種算法，在中國(guó)則可以追溯至東漢出現(xiàn)的九章算術(shù)。二、輾轉(zhuǎn)相除法的計(jì)算原理設(shè)兩數(shù)為

2、a、b(b1)，則m=kn+xd=kyd+xd=(ky+x)d，則a=mc=(ky+x)dc，b=nc=ycd，故a與b最大公約數(shù)成為cd，而非c，與前面結(jié)論矛盾】從而可知gcd(b,r)=c，繼而gcd(a,b)=gcd(b,r)。三、輾轉(zhuǎn)相除法的實(shí)例例1 、求兩個(gè)正數(shù)8251和6105的最大公因數(shù).（分析：輾轉(zhuǎn)相除余數(shù)為零得到結(jié)果） 8251610512146顯然8251與6105的最大公因數(shù)也必是2146的因數(shù),同樣6105與2146的公因數(shù)也必是8251的因數(shù),所以8251與6105的最大公因數(shù)也是6105與2146的最大公因數(shù)。 6105214621813 214618131333

3333148237 1483740則37為8251與6105的最大公因數(shù)。四、為什么用輾轉(zhuǎn)相除法能得到兩個(gè)數(shù)的最大公因數(shù)利用輾轉(zhuǎn)相除法求最大公因數(shù)的步驟如下：第一步：用較大的數(shù)m除以較小的數(shù)n得到一個(gè)商q0和一個(gè)余數(shù)r0；第二步：若r00,則n為m,n的最大公因數(shù)；若r00,則用除數(shù)n除以余數(shù)r0得到一個(gè)商q1和一個(gè)余數(shù)r1；第三步：若r10,則r1為m,n的最大公因數(shù)；若r10,則用除數(shù)r0除以余數(shù)r1得到一個(gè)商q2和一個(gè)余數(shù)r2；依次計(jì)算直至rn0,此時(shí)所得到的rn1即為所求的最大公因數(shù)。五、多項(xiàng)式的輾轉(zhuǎn)相除法整數(shù)固然有輾轉(zhuǎn)相除法的現(xiàn)象，多項(xiàng)式也有相似的性質(zhì)。假定a

4、(x)與b(x)是兩個(gè)多項(xiàng)式。用b(x)除a(x)得商式a0(x)，得余式r(x)，也就是a(x)=a0(x)b(x)+r(x)， 而r(x)的次數(shù)小于b(x)的次數(shù)。如果r(x)0，則a(x)、 b(x)的最大公因式就是b(x)。如果r(x)0，則以r(x)除b(x)得商式a1(x)，余式r1(x)，即b(x)=a1(x)r(x)+r1(x)，而r1(x)的次數(shù)小于r(x)的次數(shù)。如果r1(x)0，則r(x)就是a(x)與b(x)的最大公因式。如果r1(x)0，則以r1(x)除r(x)得r(x)=a2(x)r1(x)+r2(x)，r2(x)的次數(shù)小于r1(x)的次數(shù)。這樣一直下去，得出一系列

5、的多項(xiàng)式r(x)，r1(x)，r2(x)，它們的次數(shù)一個(gè)比一個(gè)小。當(dāng)然不能無(wú)限下去，一定有時(shí)候會(huì)出現(xiàn)rn-1(x)=an+1(x)rn(x)+rn+1(x)及 rn(x)=an+2(x)rn+1(x)的現(xiàn)象。 這樣便可以得出：rn+1(x)是a(x)與b(x)的最大公因式。同樣，如果d(x)是a(x)，b(x)的最大公因式，則一定有兩個(gè)多項(xiàng)式p(x)與q(x)，使a(x)p(x)+b(x)q(x)=d(x)。特別有：如果a(x)和b(x)無(wú)公因式，則有p(x)與q(x)使a(x)p(x)+b(x)q(x)=1。 由此我們不難看出，輾轉(zhuǎn)相除法不止能求兩個(gè)數(shù)的最大公因數(shù)，也能用于求多項(xiàng)式的公因式。六、求兩個(gè)整數(shù)最大公因數(shù)的程序算法#includeintmain()inta,b,r,result;printf(pleaseinput2integers:n);scanf(%d%d,&a,&b);if(a=b)r=a%b;elser=a;a=b;b=r;r=a%b;while(r!=0)a=b;b=r;r=a%b;printf(result=%d,b);七、運(yùn)行結(jié)果：8、 實(shí)驗(yàn)總結(jié) 通過(guò)此次實(shí)驗(yàn)，我學(xué)會(huì)了用輾轉(zhuǎn)相除法計(jì)算兩個(gè)整數(shù)