C語(yǔ)言常用算法歸納

1、歐陽(yáng)學(xué)文創(chuàng)編C語(yǔ)言常用算法歸納歐陽(yáng)學(xué)文應(yīng)當(dāng)掌握的一般算法一、基本算法：交換、累加、累乘二、非數(shù)值計(jì)算常用經(jīng)典算法：窮舉、排序（冒泡，選擇）、查找（順序即線性）三、數(shù)值計(jì)算常用經(jīng)典算法：級(jí)數(shù)計(jì)算（直接、簡(jiǎn)接即遞推）、一元非線性方程求根 （牛頓迭代法、二分法）、定積分計(jì)算（矩形法、梯形 法）四、其他：迭代、進(jìn)制轉(zhuǎn)換、矩陣轉(zhuǎn)置、字符處理（統(tǒng)計(jì)、數(shù)字 串、字母大小寫(xiě)轉(zhuǎn)換、加密等）、整數(shù)各數(shù)位上數(shù)字的獲 取、輾轉(zhuǎn)相除法求最大公約數(shù)（最小公倍數(shù)）、求最值、 判斷素?cái)?shù)（各種變形）、數(shù)組元素的插入（刪除）、二維 數(shù)組的其他典型問(wèn)題（方陣的特點(diǎn)、楊輝三角形）詳細(xì)講解一、基本算法.交換（兩量交換借助第三者）歐陽(yáng)學(xué)

2、文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編例1、任意讀入兩個(gè)整數(shù)，將二者的值交換后輸出。main。int a,b,t;scanf(%d%d”,&a,&b);printf(%d,%dn”,a,b);t=a; a=b; b=t;printf(%d,%dn”,a,b);)【解析】程序中加粗部分為算法的核心，如同交換兩個(gè) 杯子里的飲料，必須借助第三個(gè)空杯子。假設(shè)輸入的值分別為3、7,則第一行輸出為3, 7；第二 行輸出為7, 3。其中t為中間變量，起到“空杯子”的作用。注意：三句賦值語(yǔ)句賦值號(hào)左右的各量之間的關(guān)系！【應(yīng)用】例2、任意讀入三個(gè)整數(shù)，然后按從小到大的順序輸 出。main()int a,b,c,t;scanf(%d

3、%d%d”,&a,&b,&c);/*以下兩個(gè)if語(yǔ)句使得a中存放的數(shù)最小*/if(ab) t=a; a=b; b=t; if(ac) t=a; a=c; c=t; /*以下if語(yǔ)句使得b中存放的數(shù)次小*/if(bc) t=b; b=c; c=t; printf(%d,%d,%dn”,a,b,c);.累加累加算法的要領(lǐng)是形如s=s+A”的累加式，此式必須 出現(xiàn)在循環(huán)中才能被反復(fù)執(zhí)行，從而實(shí)現(xiàn)累加功能?！癆”歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編通常是有規(guī)律變化的表達(dá)式，s在進(jìn)入循環(huán)前必須獲得合適 的初值，通常為0。例1、求1+2+3+ + 100的和。main。int i,s;s=0; i=1;while(i

4、=100)s=s+i;/*累加式*/i=i+1;/*特殊的累加式*/)printf(1+2+3+.+100=%dn”,s);)【解析】程序中加粗部分為累加式的典型形式，賦值號(hào) 左右都出現(xiàn)的變量稱為累加器，其中“i = i+1”為特殊的 累加式，每次累加的值為1，這樣的累加器又稱為計(jì)數(shù)器。.累乘累乘算法的要領(lǐng)是形如s=s*A”的累乘式，此式必須 出現(xiàn)在循環(huán)中才能被反復(fù)執(zhí)行，從而實(shí)現(xiàn)累乘功能?！癆” 通常是有規(guī)律變化的表達(dá)式，s在進(jìn)入循環(huán)前必須獲得合適 的初值，通常為1。例1、求10!分析10!=1*2義3義X10main()int i; long c;c=1; i=1;while(i = 10)

5、c=c*i;/*累乘式*/i=i+1;)printf(1*2*3*.*10=%ldn,c);)歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編、非數(shù)值計(jì)算常用經(jīng)典算法1.窮舉也稱為“枚舉法”，即將可能出現(xiàn)的每一種情況一一測(cè) 試，判斷是否滿足條件，一般采用循環(huán)來(lái)實(shí)現(xiàn)。例1、用窮舉法輸出所有的水仙花數(shù)(即這樣的三位正 整數(shù)：其每位數(shù)位上的數(shù)字的立方和與該數(shù)相等，比如：1*1*1+5*5*5+3*3*3=153）。法一main。int x,g,s,b;for(x=100;x=999;x+)g=x%10; s=x/10%10; b=x/100;if(b*b*b+s*s*s+g*g*g=x)printf(%dn,x);)【解析

6、】此方法是將100到999所有的三位正整數(shù)一一 考察，即將每一個(gè)三位正整數(shù)的個(gè)位數(shù)、十位數(shù)、百位數(shù) 一一求出(各數(shù)位上的數(shù)字的提取算法見(jiàn)下面的“數(shù)字處 理”)，算出三者的立方和，一旦與原數(shù)相等就輸出。共 考慮了 900個(gè)三位正整數(shù)。法二main()int g,s,b;for(b=1;b=9;b+)for(s=0;s=9;s+)for(g=0;g=9;g+)if(b*b*b+s*s*s+g*g*g=b*100+s*10+g) printf(%dn,b *100+s*10+g);)歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編【解析】此方法是用1到9做百位數(shù)字、0到9做十位 和個(gè)位數(shù)字，將組成的三位正整數(shù)與每一組的三個(gè)

7、數(shù)的立 方和進(jìn)行比較，一旦相等就輸出。共考慮了 900個(gè)組合(外 循環(huán)單獨(dú)執(zhí)行的次數(shù)為9,兩個(gè)內(nèi)循環(huán)單獨(dú)執(zhí)行的次數(shù)分別 為10次，故if語(yǔ)句被執(zhí)行的次數(shù)為9X10X10=900),即 900個(gè)三位正整數(shù)。與法一判斷的次數(shù)一樣。2.排序(1)冒泡排序(起泡排序)假設(shè)要對(duì)含有n個(gè)數(shù)的序列進(jìn)行升序排列，冒泡排序算 法步驟是：從存放序列的數(shù)組中的第一個(gè)元素開(kāi)始到最后一個(gè)元 素，依次對(duì)相鄰兩數(shù)進(jìn)行比較，若前者大后者小，則交換 兩數(shù)的位置；第趟結(jié)束后，最大數(shù)就存放到數(shù)組的最后一個(gè)元素 里了，然后從第一個(gè)元素開(kāi)始到倒數(shù)第二個(gè)元素，依次對(duì) 相鄰兩數(shù)進(jìn)行比較，若前者大后者小，則交換兩數(shù)的位 置；重復(fù)步驟n1趟，

8、每趟比前一趟少比較一次，即可完 成所求。例1、任意讀入10個(gè)整數(shù)，將其用冒泡法按升序排列后 輸出。#define n 10main。int an,i,j,t;for(i=0;in;i+)scanf(%d,&ai);for(j = 1;j=n1;j+) /*n 個(gè)數(shù)處理 n1 趟*/for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t;for(i=0;in;i+) printf(%dn,ai);歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編(2)選擇法排序選擇法排序是相對(duì)好理解的排序算法。假設(shè)要對(duì)含有n 個(gè)數(shù)的序列進(jìn)行升序排列，算法步驟是：從數(shù)組存放的n個(gè)數(shù)中找出最小數(shù)的下標(biāo)(算法見(jiàn)下 面的“求最值”)

9、，然后將最小數(shù)與第1個(gè)數(shù)交換位置；除第1個(gè)數(shù)以外，再?gòu)钠溆嗫?個(gè)數(shù)中找出最小數(shù)(即 口個(gè)數(shù)中的次小數(shù))的下標(biāo)，將此數(shù)與第2個(gè)數(shù)交換位置；重復(fù)步驟n1趟，即可完成所求。例1、任意讀入10個(gè)整數(shù)，將其用選擇法按升序排列后 輸出。#define n 10main。int an,i,j,k,t;for(i=0;in;i+) scanf(%d,&ai);for(i=0;in1;i+)/*處理 n1 趟*/k = i;/*總是假設(shè)此趟處理的第一個(gè)(即全部數(shù)的第i個(gè))數(shù)最小，k記錄其下標(biāo)*/for(j=i+1;jn;j + +)if(aj ak) k = j;if (k != i)t = ai; ai =

10、ak; ak = t;)for(i=0;ian2) an1=x ; /*比最后一個(gè)數(shù)還大就往最后一個(gè) 元素中存放*/else /*查找待插位置*/j=。；while( jaj)j +;for(k=n2; k=j; k ) /*從最后一個(gè)數(shù)開(kāi)始直到待插位置 上的數(shù)依次后移一位*/ak+1=ak;aj=x; /*插入待插數(shù)*/for(j=0;j=n1;j+) printf(%d ,aj);插入法排序的要領(lǐng)就是每讀入一個(gè)數(shù)立即插入到最終存 放的數(shù)組中，每次插入都使得該數(shù)組有序。例2、任意讀入10個(gè)整數(shù)，將其用插入法按降序排列后 輸出。(提示：將第2至第10個(gè)數(shù)一一有序插入到數(shù)組a中)#define

11、n 10main。int an,i,j,k,x;scanf(%d”,&a0); /*讀入第一個(gè)數(shù)，直接存到a0中 */for(j = 1;jn;j + +) /*將第2至第10個(gè)數(shù)一一有序插入 到數(shù)組a中*/scanf(%d,&x);if(xaj1) aj=x;/*比原數(shù)列最后一個(gè)數(shù)還小就往最后 一個(gè)元素之后存放新讀的數(shù)*/歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編else /*以下查找待插位置*/i=0；while(xai&i=i;k) ak+1=ak;ai=x; /*插入待插數(shù)*/)for(i=0;in;i+) printf(%dn,ai);)(4)歸并排序即將兩個(gè)都升序(或降序)排列的數(shù)據(jù)序列合并成一 個(gè)

12、仍按原序排列的序列。例1、有一個(gè)含有6個(gè)數(shù)據(jù)的升序序列和一個(gè)含有4個(gè) 數(shù)據(jù)的升序序列，將二者合并成一個(gè)含有10個(gè)數(shù)據(jù)的升序 序列。#define m 6#define n 4main。int am = 3,6,19,26,68,100 ,bn = 8,10,12,22;int i,j,k,cm+n;i=j=k=0;while(im & jn) /*將a、b數(shù)組中的較小數(shù)依次存放 到c數(shù)組中*/if(ai=m & j=n & im) /*若b中數(shù)據(jù)全部存放完畢，將 a中余下的數(shù)全部存放到c中*/ck=ai; k+; i+;for(i=0;im+n;i+) printf(%d ,ci);3.查找(

13、1)順序查找(即線性查找)順序查找的思路是：將待查找的量與數(shù)組中的每一個(gè)元 素進(jìn)行比較，若有一個(gè)元素與之相等則找到；若沒(méi)有一個(gè) 元素與之相等則找不到。例1、任意讀入10個(gè)數(shù)存放到數(shù)組a中，然后讀入待查 找數(shù)值，存放到x中，判斷&中有無(wú)與x等值的數(shù)。#define N 10main。int aN,i,x;for(i=0;iN;i+) scanf(%d,&ai);/*以下讀入待查找數(shù)值*/scanf(%d,&x);for(i=0;iN;i+)if(ai=x)break ; /*一旦找到就跳出循環(huán)*/if(iN) printf(Found!n);else printf(Not found!n);(2

14、)折半查找(即二分法)順序查找的效率較低，當(dāng)數(shù)據(jù)很多時(shí)，用二分法查找可 以提高效率。使用二分法查找的前提是數(shù)列必須有序。二分法查找的思路是：要查找的關(guān)鍵值同數(shù)組的中間一 個(gè)元素比較，若相同則查找成功，結(jié)束；否則判別關(guān)鍵值 落在數(shù)組的哪半部分，就在這半部分中按上述方法繼續(xù)比 較，直到找到或數(shù)組中沒(méi)有這樣的元素值為止。歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編例1、任意讀入一個(gè)整數(shù)*，在升序數(shù)組a中查找是否有 與x等值的元素。#define n 10main。int an = 2,4,7,9,12,25,36,50,77,90;int x,high,low,mid;/*x 為關(guān)鍵值*/scanf(%d,&x);hi

15、gh=n1; low=0; mid=(high+low)/2;while(amid!=x&lowhigh)if(xamid) high=mid1; /*修改區(qū)間上界*/else low=mid+1;/*修改區(qū)間下界*/mid=(high+low)/2;if(x=amid) printf(Found %d,%dn”,x,mid);else printf(Not foundn);三、數(shù)值計(jì)算常用經(jīng)典算法.級(jí)數(shù)計(jì)算級(jí)數(shù)計(jì)算的關(guān)鍵是“描述出通項(xiàng)”，而通項(xiàng)的描述法有 兩種：一為直接法、二為間接法又稱遞推法。直接法的要領(lǐng)是：利用項(xiàng)次直接寫(xiě)出通項(xiàng)式；遞推法的 要領(lǐng)是：利用前一個(gè)(或多個(gè))通項(xiàng)寫(xiě)出后一個(gè)通項(xiàng)。

16、可以用直接法描述通項(xiàng)的級(jí)數(shù)計(jì)算例子有：1+2+3+4+5+(2)1 + 1/2+1/3+1/4+1/5+等等?？梢杂瞄g接法描述通項(xiàng)的級(jí)數(shù)計(jì)算例子有： 1+1/2+2/3+3/5+5/8+8/13+(2) 1 + 1/2!+1/3!+1/4! +1/5!+等等。(1)直接法求通項(xiàng)例 1、求 1 + 1/2+1/3+1/4+1/5+ 1/100 的和。歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編main。float s; int i;s=0.0;for(i=1;i = 100;i+) s=s+1.0/i ;printf(1 + 1/2+1/3+.+1/100=%fn”,s);)【解析】程序中加粗部分就是利用項(xiàng)次i的倒

17、數(shù)直接描 述出每一項(xiàng)，并進(jìn)行累加。注意：因?yàn)?是整數(shù)，故分子必 須寫(xiě)成1.0的形式！(2)間接法求通項(xiàng)(即遞推法)例2、計(jì)算下列式子前20項(xiàng)的和： 1+1/2+2/3+3/5+5/8+8/13+。分析此題后項(xiàng)的分子是前項(xiàng)的分母，后項(xiàng)的分母是前 項(xiàng)分子分母之和。main()float s,fz,fm,t,fz1; int i;s=1;/*先將第一項(xiàng)的值賦給累加器s*/fz=1;fm=2;t=fz/fm; /*將待加的第二項(xiàng)存入1中*/for(i=2;i=20;i+)s=s+t;/*以下求下一項(xiàng)的分子分母*/fz1=fz; /*將前項(xiàng)分子值保存到fz1中*/fz=fm;/*后項(xiàng)分子等于前項(xiàng)分母*/

18、fm=fz1+fm; /*后項(xiàng)分母等于前項(xiàng)分子、分母之和*/ t=fZ/fm;)printf(1 + 1/2+2/3+.=%fn”,s);)下面舉一個(gè)通項(xiàng)的一部分用直接法描述，另一部分用遞 推法描述的級(jí)數(shù)計(jì)算的例子：歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編二 十 I j 例3、計(jì)工kR,算級(jí)數(shù)的值，當(dāng)通項(xiàng)的絕對(duì)值 小于eps時(shí)計(jì)算停止。#include float g(float x,float eps);main。float x,eps;scanf(%f%f,&x,&eps);printf(n%f,%fn,x,g(x,eps);)float g(float x,float eps)int n=1;float

19、 s,t;s=1; t=1;do t=t*x/(2*n);s=s+(n*n+1)*t; /*加波浪線的部分為直接法描述部 分，t為遞推法描述部分*/n+;while(fabs(t)eps);return s;.一元非線性方程求根(1)牛頓迭代法牛頓迭代法又稱牛頓切線法：先任意設(shè)定一個(gè)與真實(shí)的 根接近的值x0作為第一次近似根，由x0求出f(x0)，過(guò)(x0, f(x0)點(diǎn)做f(x)的切線，交x軸于x1,把它作為第二次近似 根，再由x1求出f(x1)，過(guò)(x1, f(x1)點(diǎn)做f(x)的切線，交x軸 于*2,如此繼續(xù)下去，直到足夠接近(比如|x x0|=1e5);printf (%fn,x);(2

20、)二分法算法要領(lǐng)是：先指定一個(gè)區(qū)間x1, x2，如果函數(shù)f(x)在 此區(qū)間是單調(diào)變化的，則可以根據(jù)f(x1)和f(x2)是否同號(hào)來(lái) 確定方程f(x)=0在區(qū)間x1, *2內(nèi)是否有一個(gè)實(shí)根；如果f(x1) 和取2)同號(hào)，則f(x)在區(qū)間x1, *2內(nèi)無(wú)實(shí)根，要重新改變 x1和x2的值。當(dāng)確定f(x)在區(qū)間x1, *2內(nèi)有一個(gè)實(shí)根后， 可采取二分法將x1, x2一分為二，再判斷在哪一個(gè)小區(qū)間中 有實(shí)根。如此不斷進(jìn)行下去，直到小區(qū)間足夠小為止。具體算法如下：輸入力和x2的值。求 f(x1)和 f(x2)。(3)如果 取1)和取2)同號(hào)說(shuō)明在x1, x2內(nèi)無(wú)實(shí)根，返 同步驟(1)，重新輸入x1和x2的

21、值；若f(x1)和次2)不同 號(hào)，則在區(qū)間x1, *2內(nèi)必有一個(gè)實(shí)根，執(zhí)行步驟(4)。(4)求 x1 和 x2 的中點(diǎn):x0=(x1+ x2)/2。(5)求 f(x0)。歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編(6)判斷f(x0)與f(x1)是否同號(hào)。如果同號(hào)，則應(yīng)在x0, x2中尋找根，此時(shí)x1已不起作 用，用*0代替幻，用取0)代替f(x1)。如果不同號(hào)，則應(yīng)在x1, x0中尋找根，此時(shí)x2已不起 作用，用x0代替x2，用f(x0)代替f(x2)。(7)判斷f(x0)的絕對(duì)值是否小于某一指定的值(例如 105)。若不小于105,則返回步驟(4)重復(fù)執(zhí)行步驟 (4)、(5)、(6)；否則執(zhí)行步驟(8)。(8

22、)輸出x0的值，它就是所求出的近似根。例如，用二分法求方程2x34x2+3x6=0在(10，10)之間的 根。#include math.hmain。float x1,x2,x0,fx1,fx2,fx0;do printf(Enter x1&x2);scanf(%f%P,&x1,&x2);fx1=2*x1*x1*x14*x1*x1+3*x16;fx2=2*x2*x2*x24*x2*x2+3*x26;while(fx1*fx20);do x0=(x1+x2)/2;fx0=2*x0*x0*x04*x0*x0+3*x06;if(fx0*fx1)1e5);printf(%fn,x0);.梯形法計(jì)算定積

23、分定積分/二口.的幾何意義是求曲線y=f(x)、x=a、x=b歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編以及X軸所圍成的面積?？梢越频匕衙娣e視為若干小的梯形面積之和。例如， 把區(qū)間a, b分成n個(gè)長(zhǎng)度相等的小區(qū)間，每個(gè)小區(qū)間的長(zhǎng)度 為 h=(ba)/n，第i個(gè)小梯形的面積為 f(a+(i1)h)+f(a+ih)h/2,將n個(gè)小梯形面積加起來(lái)就 得到定積分的近似值：根據(jù)以上分析，給出“梯形法”求定積分的NS結(jié)構(gòu)圖：輸入?yún)^(qū)間端點(diǎn)：a, b輸入等分?jǐn)?shù)nh=(ba)/2, s=0i從1至U nsi=(f(a+(i1)*h)+f(a+i*h)*h/2s=s+si輸出s上述程序的幾何意義比較明顯，容易理解。但是其中存在

24、重復(fù)計(jì)算，每次循環(huán)都要計(jì)算小梯形的上、下底。其實(shí)， 前一個(gè)小梯形的下底就是后一個(gè)小梯形的上底，完全不必 重復(fù)計(jì)算。為此做出如下改進(jìn)：矩形法求定積分則更簡(jiǎn)單，就是將等分出來(lái)的圖形當(dāng)作 矩形，而不是梯形。例如：求定積分的值。等分?jǐn)?shù) n=1000。#include math.hfloat DJF(float a,float b)float t,h; int n,i;float HSZ(float x);n=1000; h=fabs(ab)/n;歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編t=(HSZ(a)+HSZ(b)/2;for(i=1;i=1;day) peach=(peach+1)*2;printf(The fi

25、rst day:%dn”,peach);又如，用迭代法求x=W的根。求平方根的迭代公式是：xn+1=0.5X(xn+a/xn )歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編算法(1)設(shè)定一個(gè)初值X0。(2)用上述公式求出下一個(gè)值x1。(3)再將燈代入上述公式，求出下一個(gè)值x2。(4)如此繼續(xù)下去，直到前后兩次求出的x值(xn+1 和*口)滿足以下關(guān)系：| xn+1 xn| = 1e5);printf(%fn,x1);.進(jìn)制轉(zhuǎn)換(1)十進(jìn)制數(shù)轉(zhuǎn)換為其他進(jìn)制數(shù)一個(gè)十進(jìn)制正整數(shù)m轉(zhuǎn)換成r進(jìn)制數(shù)的思路是，將m不 斷除以r取余數(shù)，直到商為0時(shí)止，以反序輸出余數(shù)序列即 得到結(jié)果。注意，轉(zhuǎn)換得到的不是數(shù)值，而是數(shù)字字符串或數(shù)字

26、 串。例如，任意讀入一個(gè)十進(jìn)制正整數(shù)，將其轉(zhuǎn)換成二至十 六任意進(jìn)制的字符串。void tran(int m,int r,char str,int *n)char sb=0123456789ABCDEF； int i=0,g;dog=m%r;stri=sbg;m=m/r;歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編i+;while(m!=0);*n=i;.main。int x,r0; /*r0為進(jìn)制基數(shù)*/int i,n; /*n中存放生成序列的元素個(gè)數(shù)*/char a50;scanf(%d%d,&x,&r0);if(x0&r0=2&r0=0;i) printf(%c,ai);printf(n);else exit

27、(0);(2)其他進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)其他進(jìn)制整數(shù)轉(zhuǎn)換為十進(jìn)制整數(shù)的要領(lǐng)是：“按權(quán)展開(kāi)”，例如，有二進(jìn)制數(shù)101011，則其十進(jìn)制形式為1 X25+0X24+1 X23+0X22+1 X21 + 1 X20=43O r 進(jìn)制數(shù)ana2a1 ( n位數(shù))轉(zhuǎn)換成十進(jìn)制數(shù)，方法是anXr n1 +a2Xr1+a1Xr0。注意：其他進(jìn)制數(shù)只能以字符串形式輸入。例1、任意讀入一個(gè)二至十六進(jìn)制數(shù)(字符串)，轉(zhuǎn)換 成十進(jìn)制數(shù)后輸出。#include string.h#include ctype.hmain()char x20; int r,d;gets(x);/*輸入一個(gè)r進(jìn)制整數(shù)序列*/scanf(%d,

28、&r); /*輸入待處理的進(jìn)制基數(shù)216*/ d=Tran(x,r);歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編printf(%s=%dn,x,d);)int Tran(char *p,int r)int d,i,cr; char fh,c;d=0; fh=*p;if(fh=)p+；for(i=0;i=A) cr=toupper(c)A+10;else cr=c0;d=d*r+cr;)if(fh=) d=d;return(d);).矩陣轉(zhuǎn)置矩陣轉(zhuǎn)置的算法要領(lǐng)是：將一個(gè) m行n列矩陣(即 mXn矩陣)的每一行轉(zhuǎn)置成另一個(gè)nXm矩陣的相應(yīng)列。例1、將以下2X3矩陣轉(zhuǎn)置后輸出。即將 1 2 3 轉(zhuǎn)置成1 45 62

29、53 6main()int a23,b32,i,j,k=1;for(i=0;i2;i+)for(j=0;j3;j + +)aij=k+;/*以下將a的每一行轉(zhuǎn)存到b的每一列*/for(i=0;i2;i+)for(j=0;j3;j+)bji=aij;歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編for(i=0;i3;i+)/*輸出矩陣a/for(j=0;j2;j+)printf(%3d,bij);printf(n);).字符處理(1)字符統(tǒng)計(jì)：對(duì)字符串中各種字符出現(xiàn)的次數(shù)的統(tǒng) 計(jì)。典型例題：任意讀入一個(gè)只含小寫(xiě)字母的字符串，統(tǒng)計(jì) 其中每個(gè)字母的個(gè)數(shù)。#include stdio.h main。char a100; i

30、nt n26 = 0; int i; /*定義 26 個(gè)計(jì)數(shù)器并置初 值0*/gets(a);for(i=0;ai!=0, ;i+) /*n0中存放&的個(gè)數(shù)，n1中 存放的個(gè)數(shù)*/naia+; /*各字符的 ASCII 碼值減a的 ASCII 碼 值，正好得對(duì)應(yīng)計(jì)數(shù)器下標(biāo)*/for(i=0;i26;i+)if(ni!=0) printf(%c :%dn , i+a, ni);(2)字符加密例如、對(duì)任意一個(gè)只含有英文字母的字符串，將每一個(gè) 字母用其后的第三個(gè)字母替代后輸出(字母X后的第三個(gè) 字母為A,字母Y后的第三個(gè)字母為B,字母Z后的第三 個(gè)字母為C。)#include stdio.h#inc

31、lude string.hmain()歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編char a80= China; int i;for(i=0; i=x&ai=X&ai=Z) ai= ai 26+3;else ai= ai+3;puts(a);).整數(shù)各數(shù)位上數(shù)字的獲取算法核心是利用“任何正整數(shù)整除10的余數(shù)即得該數(shù)個(gè) 位上的數(shù)字”的特點(diǎn)，用循環(huán)從低位到高位依次取出整數(shù) 的每一數(shù)位上的數(shù)字。例1、任意讀入一個(gè)5位整數(shù)，輸出其符號(hào)位及從高位 到低位上的數(shù)字。main。long x; int w,q,b,s,g;scanf(%ld,&x);if(x0) printf(,); x=x;w=x/10000;/*求萬(wàn)位上的

32、數(shù)字*/q=x/1000%10; /*求千位上的數(shù)字*/b=x/100%10; /*求百位上的數(shù)字*/s=x/10%10;/*求十位上的數(shù)字*/g=x%10;/*求個(gè)位上的數(shù)字*/printf(%d,%d,%d,%d,%dn,w,q,b,s,g);例2、任意讀入一個(gè)整數(shù)，依次輸出其符號(hào)位及從低位 到高位上的數(shù)字。分析此題讀入的整數(shù)不知道是幾位數(shù)，但可以用以下 示例的方法完成此題：例如讀入的整數(shù)為3796,存放在x中，執(zhí)行x%10后得 余數(shù)為6并輸出；將x/10得379后賦值給x。再執(zhí)行x%10歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編后得余數(shù)為9并輸出；將x/10得37后賦值給x直到商 x為0時(shí)終止。main。

33、long x; scanf(%ld,&x);if(x0) printf( ); x=x;do /*為了能正確處理0，要用do_while循環(huán)*/printf(%d , x%10);x=x/10;while(x!=0);printf(n);例3、任意讀入一個(gè)整數(shù)，依次輸出其符號(hào)位及從高位 到低位上的數(shù)字。分析此題必須借助數(shù)組將依次求得的低位到高位的數(shù) 字保存后，再逆序輸出。main()long x; int a20,i,j;scanf(%ld,&x);if(x=0;j)printf(%d ,aj);printf(n);.輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)的最大公約數(shù)該算法的要領(lǐng)是：假設(shè)兩個(gè)正整數(shù)為a和b,先

34、求出前 者除以后者的余數(shù)，存放到變量r中，若r不為0,則將b歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編的值得賦給a,將r的值得賦給b；再求出a除以b的余 數(shù)，仍然存放到變量r中如此反復(fù)，直至r為0時(shí)終 止，此時(shí)b中存放的即為原來(lái)兩數(shù)的最大公約數(shù)。例1、任意讀入兩個(gè)正整數(shù)，求出它們的最大公約數(shù)。法一：用while循環(huán)時(shí)，最大公約數(shù)存放于b中main。int a,b,r;do scanf(%d%d”,&a,&b);while(a=0|b=0); /*確保 a 和 b 為正整數(shù)*/ r=a%b;while(r!=0)a=b;b=r;r=a%b;printf(%dn,b);法二：用d。while循環(huán)時(shí)，最大公約數(shù)存放于

35、&中 main()int a,b,r;do scanf(%d%d”,&a,&b);while(a=0|b=0); /*確保 a 和 b 為正整數(shù)*/do r=a%b;a=b;b=r;while(r!=0);printf(%dn,a);【引申】可以利用最大公約數(shù)求最小公倍數(shù)。提示：兩 個(gè)正整數(shù)a和b的最小公倍數(shù)=a義b/最大公約數(shù)。例2、任意讀入兩個(gè)正整數(shù)，求出它們的最小公倍數(shù)。法一：利用最大公約數(shù)求最小公倍數(shù)main()int a,b,r,x,y;do scanf(%d%d”,&a,&b);while(a=0|b=0); /*確保 a 和 b 為正整數(shù)*/x=a; y=b; /*保留a、b原來(lái)

36、的值*/歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編r=a%b;while(r!=0) a=b;b=r;r=a%b;printf(%dn,x*y/b);法二：若其中一數(shù)的最小倍數(shù)也是另一數(shù)的倍數(shù)，該 最小倍數(shù)即為所求main。int a,b,r,i;do scanf(%d%d”,&a,&b);while(a=0|b=0); /*確保 a 和 b 為正整數(shù)*/i=l；while(a*i%b!=0) i+;printf(%dn,i*a);.求最值即求若干數(shù)據(jù)中的最大值(或最小俏)。算法要領(lǐng) 是：首先將若干數(shù)據(jù)存放于數(shù)組中，通常假設(shè)第一個(gè)元素 即為最大值(或最小值)，賦值給最終存放最大值(或最 小值)的max (或mi

37、n)變量中，然后將該量 max (或 min)的值與數(shù)組其余每一個(gè)元素進(jìn)行比較，一旦比該量還 大(或小)，則將此元素的值賦給max (或min)所有 數(shù)如此比較完畢，即可求得最大值(或最小值)。例1、任意讀入10個(gè)數(shù)，輸出其中的最大值與最小值。#define N 10main()int aN,i,max,min;for(i=0;iN;i+) scanf(%d,&ai);max=min=a0;for(i=1;imax) max=ai;else if(aimin) min=ai;歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編printf(max=%d,min=%dn”,max,min);).判斷素?cái)?shù)素?cái)?shù)又稱質(zhì)數(shù)，即“只

38、能被1和自身整除的大于1的自 然數(shù)”。判斷素?cái)?shù)的算法要領(lǐng)就是依據(jù)數(shù)學(xué)定義，即若該 大于1的正整數(shù)不能被2至自身減1整除，就是素?cái)?shù)。例1、任意讀入一個(gè)正整數(shù)，判斷其是否為素?cái)?shù)。main。int x,k;do scanf(%d,&x);while(x = 1); /*確保讀入大于1的正整數(shù)*/for(k=2;k=x1;k+)if(x%k=0)break; /*一旦能被2自身1整除，就不可 能是素?cái)?shù)*/if(k=x) printf(%d is sushun,x);else printf(%d is not sushun,x);)以上例題可以用以下兩種變形來(lái)解決(需要使用輔助判 斷的邏輯變量)：【變形

39、一】將“2自身1”的范圍縮小至“2自身的一 半，main()int x,k,flag;do scanf(%d,&x); while(x=1);flag=1; /*先假設(shè)x就是素?cái)?shù)*/for(k=2;k=x/2;k+)if(x%k=0)flag=0; break;/*一且不可能是素?cái)?shù)，即 置 flag 為 0*/if(flag= = 1) printf(%d is sushun,x);else printf(%d is not sushun,x);歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編【變形二】將“2自身1”的范圍縮小至“2自身的平 方根”#include math.hmain。int x,k,flag;do

40、 scanf(%d,&x); while(x = 1);flag=1; /*先假設(shè)x就是素?cái)?shù)*/for(k=2;k=(int)sqrt(x);k+)if(x%k=0)flag=0; break;/* 一且不可能是素?cái)?shù)，即置 flag 為 0*/if(flag= = 1) printf(%d is sushun,x);else printf(%d is not sushun,x);例2、用篩選法求得100以內(nèi)的所有素?cái)?shù)。算法為：(1)定義一維數(shù)組a，其初值為：2,3，100；(2)若ak不為0，則將該元素以后的所有2代的倍 數(shù)的數(shù)組元素置為0；(3) a中不為0的元素，均為素 數(shù)。.#inclu

41、de #include main( )int k,j,a101;clrscr(); /*清屏函數(shù)*/for(k=2;k101;k+)ak=k;for(k=2;ksqrt(101);k+)for(j=k+1;j101;j+)if(ak!=0&aj!=0)if(aj%ak=0)aj=0;for(k=2;k101;k+)if(ak!=0)printf(%5d,ak);歐陽(yáng)學(xué)文創(chuàng)編歐陽(yáng)學(xué)文創(chuàng)編)9.數(shù)組元素的插入、刪除(1)數(shù)組元素的插入此算法一般是在已經(jīng)有序的數(shù)組中再插入一個(gè)數(shù)據(jù)，使 數(shù)組中的數(shù)列依然有序。算法要領(lǐng)是：假設(shè)待插數(shù)據(jù)為X，數(shù)組a中數(shù)據(jù)為升序序列。先將x與a數(shù)組當(dāng)前最后一個(gè)元素進(jìn)行比較，

42、若比最 后一個(gè)元素還大，就將x放入其后一個(gè)元素中；否則進(jìn)行以 下步驟；先查找到待插位置。從數(shù)組a的第1個(gè)元素開(kāi)始找到 不比x小的第一個(gè)元素，設(shè)其下標(biāo)為i；將數(shù)組a中原最后一個(gè)元素至第i個(gè)元素依次一一后 移一位，讓出待插數(shù)據(jù)的位置，即下標(biāo)為i的位置；將*存放到a(i)中。例題參見(jiàn)前面“排序中插入法排序的例1”。(2)數(shù)組元素的刪除此算法的要領(lǐng)是：首先要找到(也可能找不到)待刪除 元素在數(shù)組中的位置(即下標(biāo))，然后將待刪元素后的每 一個(gè)元素向前移動(dòng)一位，最后將數(shù)組元素的個(gè)數(shù)減1。例1、數(shù)組a中有若干不同考試分?jǐn)?shù)，任意讀入一個(gè)分 數(shù)，若與數(shù)組a中某一元素值相等，就將該元素刪除。#define N 6main。int fsN = 69,90,85,56,44,80,x; int i,j,n;n=N;scanf(%d,&x); /*任意讀入一個(gè)分?jǐn)?shù)值*/*以下查找待刪分?jǐn)?shù)的位