• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      用C語(yǔ)言對(duì)高中教材中關(guān)于計(jì)算最大公因數(shù)算法的實(shí)際檢驗(yàn)

      2019-03-25 07:34:40張凡
      中國(guó)科技縱橫 2019年4期

      張凡

      摘 要:最大公因數(shù),在數(shù)學(xué)領(lǐng)域運(yùn)用十分廣泛,也是計(jì)算機(jī)領(lǐng)域自發(fā)展以來的熱門話題之一。本文就高中數(shù)學(xué)課本中所羅列的輾轉(zhuǎn)相除法與更相減損法以C語(yǔ)言為工具,對(duì)這兩種算法在實(shí)際計(jì)算機(jī)的應(yīng)用中做出的檢驗(yàn)做出評(píng)價(jià)與分析,并給出實(shí)驗(yàn)的測(cè)試數(shù)據(jù)。

      關(guān)鍵詞:C語(yǔ)言;最大公因數(shù);算法思想

      中圖分類號(hào):TP311.11 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1671-2064(2019)04-0037-02

      0 引言

      我們?cè)诟咧袑W(xué)習(xí)中,曾學(xué)習(xí)過一個(gè)章節(jié)算法與程序框圖,這一章中,我們?cè)敿?xì)地了解了有關(guān)怎樣尋找最大公因數(shù)的應(yīng)用算法以及有關(guān)的程序框圖,算法包括輾轉(zhuǎn)相除法和更相減損法。在現(xiàn)代計(jì)算機(jī)社會(huì)中,一個(gè)算法能否在實(shí)際中快速有效地達(dá)到目的是非常重要的一個(gè)參考指標(biāo),它決定著算法的優(yōu)劣。因此,本文旨在以實(shí)際操作的方式,對(duì)這兩種算法進(jìn)行深入的剖析研究,并對(duì)其實(shí)用性做出論定。最大公因數(shù),又稱最大公約數(shù),是指兩個(gè)或兩個(gè)以上整數(shù)共有約數(shù)中最大的一個(gè),本文著重介紹對(duì)兩個(gè)數(shù)最大公約數(shù)的實(shí)際檢驗(yàn)。

      1 質(zhì)因數(shù)分解法

      學(xué)生時(shí)代剛剛接觸到最大公因數(shù)這個(gè)概念的時(shí)候,老師通常會(huì)讓我們使用質(zhì)因數(shù)分解法。所謂質(zhì)因數(shù)分解,它指的是將一個(gè)合數(shù)(除了1和自身外還有其他因數(shù)的數(shù))分解為若干質(zhì)數(shù)(只有1和自身這兩個(gè)因數(shù))的乘積的形式。舉個(gè)簡(jiǎn)單的例子,對(duì)于數(shù)字180,我們對(duì)從2開始的質(zhì)數(shù)進(jìn)行逐個(gè)的檢驗(yàn),首先:180=2*90,那么可以分解出了一個(gè)2;繼續(xù)分解,90=2*45,這個(gè)時(shí)候,不難發(fā)現(xiàn)45不能被2整除,那么可以檢驗(yàn)是否能被3整除,通過45=3*15,15=3*5這兩個(gè)算式,可以得到了5,而5是一個(gè)質(zhì)數(shù),故分解完畢后180=2*2*3*3*5。那么如果要計(jì)算180和120的最大公因數(shù),只需要對(duì)120也做上述工作,這樣可以得到120=2*2*2*3 *5,再將兩個(gè)數(shù)字分解后多個(gè)質(zhì)因數(shù)中的相同部分,選出并計(jì)算其乘積,如對(duì)180和120進(jìn)行上述運(yùn)算可以得到2*2*3*5=60,那么180和120的最大公因數(shù)就是60。

      質(zhì)因數(shù)分解法,看似非常簡(jiǎn)單的一個(gè)方法,在計(jì)算機(jī)程序的運(yùn)行中卻很少涉及,其原因在于計(jì)算機(jī)的運(yùn)行方式和人不同,計(jì)算機(jī)更習(xí)慣于重復(fù)的、循環(huán)的、相同的任務(wù)體系。對(duì)于計(jì)算機(jī),我們要尋求更加方便“計(jì)算機(jī)”領(lǐng)悟的方法技巧,這也是本文接下來要給大家介紹的這兩種方法。

      2 輾轉(zhuǎn)相除法

      2.1 算法原理

      輾轉(zhuǎn)相除法[2],最早是由歐幾里得在公元前300年左右提出的,因此又叫歐幾里得算法。它是指用開始的兩個(gè)數(shù)(本文只討論兩數(shù)中最大公約數(shù)的求法,下同)中較大的數(shù)除以較小的數(shù),得到商和余數(shù),由于初始兩數(shù)與所得余數(shù)的最大公因數(shù)相等,所以用較小的數(shù)和余數(shù)重復(fù)上述過程,最終得到兩個(gè)數(shù),其中一個(gè)能被另一個(gè)整除。在計(jì)算機(jī)的算法中,這種重復(fù)的、可操作性強(qiáng)的方法,比起傳統(tǒng)的質(zhì)因數(shù)分解法,它更適合計(jì)算機(jī)程序進(jìn)行工作。

      我們先來看一下這種算法的普通應(yīng)用。以高中教材的數(shù)據(jù)為例,使用輾轉(zhuǎn)相除法求8251和6105的最大公因數(shù),首先用其中較大的那個(gè)數(shù)除以較小數(shù),所得商和余數(shù)8251=6105*1+2146。通過這個(gè)式子,可以得到了余數(shù)2146。由最大公因數(shù)的定義可知,6105、8251以及所得余數(shù)2146它們的最大公約數(shù)其實(shí)是相等的,那么接下來只需要計(jì)算6105與2146的最大公約數(shù),這無疑大大地減少了計(jì)算量,距離得到結(jié)果又更近了一步。

      我們對(duì)6105和2146重復(fù)上述步驟(使用輾轉(zhuǎn)相除的時(shí)候,我們盡量選擇較小的兩個(gè)數(shù),這樣可以大大地減少計(jì)算量):

      6105=2146*2+1813

      2146=1813*1+333

      1813=333*5+148

      333=148*2+37

      148=37*4

      到這里,不難發(fā)現(xiàn),我們得到了一個(gè)無法取余的式子,那么這個(gè)時(shí)候,求出的最大公約數(shù)即為37。

      2.2 算法實(shí)現(xiàn)

      經(jīng)過對(duì)輾轉(zhuǎn)相除的嘗試,可以初步了解輾轉(zhuǎn)相除法的基本流程,對(duì)于其在計(jì)算機(jī)上的實(shí)用性,我們采用了最常用的開發(fā)工具M(jìn)icrosoft Visual C++進(jìn)行了實(shí)驗(yàn)的檢測(cè)[1,4],整個(gè)程序與算法所使用的方式基本一致,我們首先采用了課本中所給出的數(shù)據(jù),并且類似地進(jìn)行了以下幾組實(shí)驗(yàn):

      實(shí)驗(yàn)所用代碼如下:

      #include

      int main()

      {

      int a,b,m;

      printf("請(qǐng)輸入兩個(gè)正整數(shù),該程序?qū)⑹褂幂氜D(zhuǎn)相除法求其最大公因數(shù):a=");

      scanf("%d",&a);

      printf("b=");

      scanf("%d",&b);

      while(a%b!=0)

      {

      m=a%b;

      a=b;b=m;

      }

      printf("a與b最大公因數(shù)為%d\n",b);

      return 0;

      }

      2.3 算法結(jié)果及評(píng)價(jià)

      將實(shí)驗(yàn)中所使用的數(shù)據(jù)列成一張表格,實(shí)驗(yàn)結(jié)果如表1所示。

      對(duì)于每一個(gè)實(shí)驗(yàn),均采用了變量交換的方法進(jìn)行驗(yàn)證,這樣做可以更全面地確定實(shí)驗(yàn)的準(zhǔn)確性與完整性。除去課本上的例子,我們還選取了一組數(shù)值較大且明顯互質(zhì)的數(shù)字進(jìn)行檢驗(yàn)。

      計(jì)算機(jī)所呈現(xiàn)出來的結(jié)果與我們所預(yù)想的結(jié)果基本一致,在重重考核下,計(jì)算機(jī)都出色地完成了任務(wù)。此后進(jìn)行的其他多組重復(fù)數(shù)據(jù),也向我們證實(shí)了輾轉(zhuǎn)相除法在計(jì)算機(jī)領(lǐng)域中應(yīng)用的優(yōu)勢(shì)。

      那么是不是直接使用輾轉(zhuǎn)相除計(jì)算最大公因數(shù)就可以了呢?當(dāng)然不是,從數(shù)據(jù)結(jié)構(gòu)的角度而言,輾轉(zhuǎn)相除還有許多不夠完善的方面。諸如,當(dāng)我們涉及到較大的變量時(shí),由于計(jì)算機(jī)的除法運(yùn)算和我們的除法運(yùn)算的機(jī)理是完全不同的,計(jì)算機(jī)的除法需要進(jìn)行許多額外的繁雜工作,這樣高額的除法運(yùn)算量所帶來的工作量在實(shí)際生產(chǎn)生活中無疑會(huì)帶來巨大的成本問題。

      3 更相減損法

      3.1 算法原理

      更相減損術(shù)出自《九章算術(shù)》,即“可半者半之,不可半者,副置分母、子之?dāng)?shù),以少減多,更相減損,求其等也,以等數(shù)約之”。用現(xiàn)在的話來講,就是先判斷是否都為偶數(shù),用2約減后,再以較大的數(shù)減去較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù),繼續(xù)這個(gè)操作,直到所得的數(shù)大小相等為止,則這個(gè)數(shù)與開始約減的數(shù)乘積即為所求最大公約數(shù)[3]。

      也就是說,輾轉(zhuǎn)相除法分為兩個(gè)步驟,一個(gè)步驟為“約減”,另一個(gè)為“減損”,舉個(gè)例子,我們計(jì)算196和126的最大公因數(shù),首先這兩個(gè)數(shù)都是偶數(shù),那么同時(shí)將其除以2,得到98和63。顯然,98和63的最大公因數(shù)也是196和126的公因數(shù),只是比196和126的最大公因數(shù)要少了一半。進(jìn)行這個(gè)環(huán)節(jié)以后,由于63不是偶數(shù),那么約減完畢,接下來就是進(jìn)行減損工作。把98和63以大數(shù)減小數(shù),并進(jìn)行“輾轉(zhuǎn)相減”,得到:

      98-63=35;63-35=28;35-28=7;28-7=14;14-7=7

      由于進(jìn)行最后一步操作后得到的是兩個(gè)相等的整數(shù),那么7就是98和63的最大公因數(shù)了(這也側(cè)面反映了計(jì)算兩個(gè)奇數(shù)的最大公因數(shù),使用輾轉(zhuǎn)相減法是個(gè)非常不錯(cuò)的方法)。但是要計(jì)算196和126的最大公因數(shù),我們還要將7乘上剛才所約掉的2。

      3.2 算法實(shí)現(xiàn)

      如同輾轉(zhuǎn)相除法,針對(duì)更相減損法,我們也進(jìn)行了實(shí)際檢驗(yàn)的過程,所使用的代碼如下:

      #include

      int main()

      {

      long a,b,m,t,r;

      printf("請(qǐng)輸入兩個(gè)正整數(shù),該程序?qū)⑹褂酶鄿p損法求其最大公因數(shù):a=");

      scanf("%d",&a);

      printf("b=");

      scanf("%d",&b);

      t=1;

      while((a%2==0)&&(b%2==0))

      {

      t=t*2;

      a=a/2;

      b=b/2;

      }

      while(1)

      {

      if(a

      {

      r=b;

      b=a;

      a=r;

      }

      while((a!=b)&&(a>b))

      {

      m=b;

      b=a-b;

      a=m;

      }

      if(a==b) break;

      }

      a=a*t;

      printf("a與b最大公因數(shù)為%d\n",a);

      return 0;

      }

      3.3 算法結(jié)果及評(píng)價(jià)

      更相減損實(shí)驗(yàn)結(jié)果,如表2所示。

      經(jīng)過實(shí)驗(yàn)可以發(fā)現(xiàn),更相減損法也是計(jì)算最大公因數(shù)的良好途徑之一。然而實(shí)驗(yàn)發(fā)現(xiàn),更相減損所需要的代碼比輾轉(zhuǎn)相除多一倍之多,此時(shí)我們要將約減和減損分開作為一個(gè)程序的兩個(gè)不同的部分進(jìn)行分別處理。而如果去掉約減環(huán)節(jié),大量的迭代會(huì)使較大的、有一定規(guī)律的數(shù)據(jù)的處理效率顯著降低。比如計(jì)算999999和3的最大公因數(shù),使用輾轉(zhuǎn)相除法可以一步到位,然而使用更相減損卻要進(jìn)行巨大的工作量。除了約減的繁瑣以外,每循環(huán)一次,都要進(jìn)行一次對(duì)變量a,b的大小比較,也就是說,這一程序一共需要進(jìn)行三次不同的循環(huán)迭代,包括一個(gè)循環(huán)的嵌套,在一個(gè)較大的程序中,計(jì)算最大公因數(shù)不過是一個(gè)極小的環(huán)節(jié)而已,如果這樣一個(gè)小環(huán)節(jié)都需要耗費(fèi)如此經(jīng)歷,那么這個(gè)算法也是不夠成熟的。

      4 結(jié)語(yǔ)

      雖然說計(jì)算兩個(gè)數(shù)的最大公因數(shù),在我們看來也許是非常簡(jiǎn)單容易的操作,但是在現(xiàn)代的計(jì)算機(jī)領(lǐng)域卻仍然存在各種各樣的問題。除了高中數(shù)學(xué)課本中給我們所展示的這兩種算法外,計(jì)算兩個(gè)數(shù)的最大公因數(shù)的辦法還有許多,許多方法仍然需要我們?nèi)ゲ粩嗤晟婆c修改。相信在科技的不斷發(fā)展中,一定會(huì)有更加完美的算法去適應(yīng)當(dāng)今的時(shí)代趨勢(shì)。

      參考文獻(xiàn)

      [1] 譚浩強(qiáng).C程序設(shè)計(jì)(第四版)[J].計(jì)算機(jī)教育,2010,No.128(20):113-113.

      [2] 邊晶,杜威.深入探析計(jì)算機(jī)求解大整數(shù)最大公約數(shù)問題[J].長(zhǎng)春大學(xué)學(xué)報(bào),2012,(12):1476-1479.

      [3] 邱建林,劉維富,顧暉.C語(yǔ)言程序設(shè)計(jì)教學(xué)的研究與實(shí)踐[J].電氣電子教學(xué)學(xué)報(bào),2003,25(4):96-98.

      [4] 黃定華,孫炳達(dá).嵌入式系統(tǒng)中的軟件設(shè)計(jì)技術(shù)──語(yǔ)言程序設(shè)計(jì)[J].工業(yè)控制計(jì)算機(jī),2001,14(5):3-6.

      原阳县| 叙永县| 广饶县| 滦平县| 仙桃市| 河西区| 宁陵县| 鹤庆县| 博野县| 浦江县| 湘潭市| 榕江县| 文登市| 中江县| 楚雄市| 汽车| 凉城县| 上饶县| 郓城县| 博白县| 榆中县| 东光县| 西贡区| 紫云| 迭部县| 蓬溪县| 贵州省| 平武县| 阜城县| 辛集市| 鄯善县| 巧家县| 博罗县| 耒阳市| 东阳市| 毕节市| 商水县| 高阳县| 瓮安县| 新余市| 南郑县|