C語言常用算法歸納

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

2、整數(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）;【解析】程序中加粗部分為算法的核心，如同交換兩個杯子里的飲料，必須借助第三個 空杯子。假設(shè)輸入的值分別為 3、7，則第一行輸出為 3 ，7 ；第二行輸出為 7 ，3 。 其中 t 為中間變量，起到 “空杯子 ”的作用。注意：三句賦值語句賦值號左右的各量之間的關(guān)系！【應(yīng)用】例 2 、任意讀入三個整數(shù)，然后按從小

3、到大的順序輸出。 main() int a,b,c,t; scanf("%d%d%d",&a,&b,&c);/*以下兩個 if 語句使得 a 中存放的數(shù)最小 */ if(a>b) t=a; a=b; b=t; if(a>c) t=a; a=c; c=t; /*以下 if 語句使得 b 中存放的數(shù)次小 */ if(b>c) t=b; b=c; c=t; printf("%d,%d,%dn",a,b,c);2累加累加算法的要領(lǐng)是形如“s=s+A勺累加式，此式必須出現(xiàn)在循環(huán)中才能被反復(fù)執(zhí)行，從而實現(xiàn)累加功能。“ A”常

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

5、常是有規(guī)律變化的表達式，s在進入循環(huán)前必須獲得合適的初值，通常 為 1 。例 1 、求 10 ！分析10 ! =1X 2X 3X X 10main() int i; long c;c=1; i=1;while(i<=10) c=c*i; /* 累乘式 */i=i+1; printf("1*2*3*.*10=%ldn",c); 二、非數(shù)值計算常用經(jīng)典算法1窮舉也稱為“枚舉法”，即將可能出現(xiàn)的每一種情況一一測試，判斷是否滿足條件，一般采用 循環(huán)來實現(xiàn)。例 1 、用窮舉法輸出所有的水仙花數(shù)(即這樣的三位正整數(shù)：其每位數(shù)位上的數(shù)字的立 方和與該數(shù)相等，比如： 1*1*1+5*

6、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);【解析】此方法是將 100 到 999 所有的三位正整數(shù)一一考察，即將每一個三位正整數(shù)的 個位數(shù)、十位數(shù)、百位數(shù)一一求出(各數(shù)位上的數(shù)字的提取算法見下面的 “數(shù)字處理 ”)，算 出三者的立方和，一旦與原數(shù)相等就輸出。共考慮了 900 個三位正整數(shù)。法二main()int g,s,b;for(b=1;b<=9;b+) fo

7、r(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);【解析】此方法是用 1 到 9 做百位數(shù)字、 0 到 9 做十位和個位數(shù)字，將組成的三位正整 數(shù)與每一組的三個數(shù)的立方和進行比較，一旦相等就輸出。共考慮了 900 個組合(外循環(huán)單 獨執(zhí)行的次數(shù)為 9，兩個內(nèi)循環(huán)單獨執(zhí)行的次數(shù)分別為10 次，故 if 語句被執(zhí)行的次數(shù)為9X10X10=900 )，即900個三位正整數(shù)。與法一判斷的次數(shù)一樣。2排序(1) 冒泡排序 (起泡排序)假設(shè)

8、要對含有 n 個數(shù)的序列進行升序排列，冒泡排序算法步驟是： 從存放序列的數(shù)組中的第一個元素開始到最后一個元素，依次對相鄰兩數(shù)進行比較， 若前者大后者小，則交換兩數(shù)的位置； 第趟結(jié)束后，最大數(shù)就存放到數(shù)組的最后一個元素里了，然后從第一個元素開始到 倒數(shù)第二個元素，依次對相鄰兩數(shù)進行比較，若前者大后者小，則交換兩數(shù)的位置； 重復(fù)步驟 n-1 趟，每趟比前一趟少比較一次，即可完成所求。例 1 、任意讀入 10 個整數(shù)，將其用冒泡法按升序排列后輸出。#define n 10main() int an,i,j,t;for(i=0;i<n;i+)scanf("%d",&a

9、i);for(j=1;j<=n-1;j+)/*n 個數(shù)處理 n-1 趟*/for(i=0;i<=n-1-j;i+)/*每趟比前一趟少比較一次 */if(ai>ai+1) t=ai;ai=ai+1;ai+1=t; for(i=0;i<n;i+) printf("%dn",ai);( 2) 選擇法排序選擇法排序是相對好理解的排序算法。假設(shè)要對含有 n 個數(shù)的序列進行升序排列，算法 步驟是： 從數(shù)組存放的 n 個數(shù)中找出最小數(shù)的下標(biāo)(算法見下面的 “求最值”) ，然后將最小數(shù) 與第 1 個數(shù)交換位置； 除第 1 個數(shù)以外，再從其余 n-1 個數(shù)中找出最小數(shù)

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

11、!= i) t = ai; ai = ak; ak = t; for(i=0;i<n;i+) printf("%dn",ai);(3)插入法排序 要想很好地掌握此算法，先請了解 “有序序列的插入算法 ”，就是將某數(shù)據(jù)插入到一個有 序序列后，該序列仍然有序。插入算法參見下面的 “數(shù)組元素的插入 ”。例 1 、將任意讀入的整數(shù) x 插入一升序數(shù)列后，數(shù)列仍按升序排列。#define n 10main() int an=-1,3,6,9,13,22,27,32,49,x,j,k;/* 注意留一個空間給待插數(shù) */scanf("%d",&x);if

12、(x>an-2) an-1=x ; /* 比最后一個數(shù)還大就往最后一個元素中存放 */ else /* 查找待插位置 */ j=0;while( j<=n-2 && x>aj) j+;for(k=n-2; k>=j; k- -)/*從最后一個數(shù)開始直到待插位置上的數(shù)依次后移一位 */ak+1=ak;aj=x;/* 插入待插數(shù) */for(j=0;j<=n-1;j+) printf("%d ",aj); 插入法排序的要領(lǐng)就是每讀入一個數(shù)立即插入到最終存放的數(shù)組中，每次插入都使得該 數(shù)組有序。例 2 、任意讀入 10 個整數(shù)，將其用

13、插入法按降序排列后輸出。(提示：將第 2 至第 10 個數(shù)一一有序插入到數(shù)組 a 中)#define n 10main() int an,i,j,k,x;scanf("%d",&a0); /*讀入第一個數(shù)，直接存到 a0 中*/for(j=1;j<n;j+)/* 將第 2 至第 10 個數(shù)一一有序插入到數(shù)組 a 中 */ scanf("%d",&x); if(x<aj-1) aj=x;/* 比原數(shù)列最后一個數(shù)還小就往最后一個元素之后存放新讀的數(shù) */ else /* 以下查找待插位置 */ i=0; while(x<ai

14、&&i<=j-1) i+;/* 以下 for 循環(huán)從原最后一個數(shù)開始直到待插位置上的數(shù)依次后移一位 */ for(k=j-1;k>=i;k-) ak+1=ak;ai=x;/* 插入待插數(shù) */ for(i=0;i<n;i+) printf("%dn",ai);(4)歸并排序 即將兩個都升序(或降序)排列的數(shù)據(jù)序列合并成一個仍按原序排列的序列。例 1 、有一個含有 6 個數(shù)據(jù)的升序序列和一個含有 4 個數(shù)據(jù)的升序序列，將二者合并成 一個含有 10 個數(shù)據(jù)的升序序列。#define m 6#define n 4main() int am=-3,

15、6,19,26,68,100 ,bn=8,10,12,22;int i,j,k,cm+n;i=j=k=0;while(i<m && j<n)/*將 a、b 數(shù)組中的較小數(shù)依次存放到 c 數(shù)組中 */ if(ai<bj) ck=ai; i+;else ck=bj; j+;k+;while(i>=m && j<n) /*若 a 中數(shù)據(jù)全部存放完畢，將 b 中余下的數(shù)全部存放到 c 中*/ ck=bj; k+; j+; while(j>=n && i<m) /* 若 b 中數(shù)據(jù)全部存放完畢， 將 a 中余下的數(shù)

16、全部存放到 c 中 */ ck=ai; k+; i+; for(i=0;i<m+n;i+) printf("%d ",ci);3查找(1)順序查找(即線性查找)順序查找的思路是：將待查找的量與數(shù)組中的每一個元素進行比較，若有一個元素與之 相等則找到；若沒有一個元素與之相等則找不到。例 1 、任意讀入 10 個數(shù)存放到數(shù)組 a 中，然后讀入待查找數(shù)值，存放到 x 中，判斷 a 中 有無與 x 等值的數(shù)。#define N 10main() int aN,i,x;for(i=0;i<N;i+) scanf("%d",&ai);/* 以下讀

17、入待查找數(shù)值 */scanf("%d",&x);for(i=0;i<N;i+)if(ai=x) break ;/*一旦找到就跳出循環(huán) */if(i<N) printf("Found!n");else printf("Not found!n");(2) 折半查找(即二分法) 順序查找的效率較低，當(dāng)數(shù)據(jù)很多時，用二分法查找可以提高效率。使用二分法查找的 前提是數(shù)列必須有序。二分法查找的思路是： 要查找的關(guān)鍵值同數(shù)組的中間一個元素比較， 若相同則查找成功， 結(jié)束；否則判別關(guān)鍵值落在數(shù)組的哪半部分，就在這半部分中按上述方法

18、繼續(xù)比較，直到找 到或數(shù)組中沒有這樣的元素值為止。例1、任意讀入一個整數(shù)X,在升序數(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);high=n-1; low=0; mid=(high+low)/2;while(amid!=x&&low<high) if(x<amid) high=mid-1;/*修改區(qū)間上界 */else low=mid+1; /* 修改區(qū)間下

19、界 */mid=(high+low)/2;if(x=amid) printf("Found %d,%dn",x,mid);else printf("Not foundn");三、數(shù)值計算常用經(jīng)典算法1級數(shù)計算級數(shù)計算的關(guān)鍵是 “描述出通項 ”，而通項的描述法有兩種：一為直接法、二為間接法又 稱遞推法。直接法的要領(lǐng)是：利用項次直接寫出通項式；遞推法的要領(lǐng)是：利用前一個(或多個) 通項寫出后一個通項?？梢杂弥苯臃枋鐾椀募墧?shù)計算例子有：(1) 1+2+3+4+5+(2) 1+1/2+1/3+ 1/4+1/5+ 等等。 可以用間接法描述通項的級數(shù)計算例子有：

20、( 1)1+1/2+2/3+3/5+5/8+8/13+ ( 2)1+1/2!+1/3!+1/4! +1/5!+ 等等。( 1 )直接法求通項例 1、求 1+1/2+1/3+1/4+1/5+ +1/100 的和。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); 【解析】程序中加粗部分就是利用項次 i 的倒數(shù)直接描述出每一項，并進行累加。注意： 因為i是整數(shù)，故分子必須寫成1.0的形式！( 2 )間接法求通項(即遞推法)例 2、計算下列

21、式子前 20 項的和：1+1/2+2/3+3/5+5/8+8/13+ 。 分析此題后項的分子是前項的分母，后項的分母是前項分子分母之和。main() float s,fz,fm,t,fz1; int i;s=1;/*先將第一項的值賦給累加器 s*/fz=1;fm=2;t=fz/fm;/*將待加的第二項存入 t 中*/for(i=2;i<=20;i+) s=s+t;/*以下求下一項的分子分母 */ fz1=fz; /* 將前項分子值保存到 fz1 中 */ fz=fm; /* 后項分子等于前項分母 */ fm=fz1+fm; /* 后項分母等于前項分子、分母之和 */ t=fz/fm;pr

22、in tf("1+1/2+2/3+.=%fn",s);下面舉一個通項的一部分用直接法描述，另一部分用遞推法描述的級數(shù)計算的例子:例3、計算級 呎 U /數(shù)的值，當(dāng)通項的絕對值小于eps時計算停止。#in elude <math.h>float g(float x,float eps);mai n() float x,eps;sca nf("%f%f", &x,&eps);prin tf("n%f,%fn",x,g(x,eps);float g(float x,float eps) int n=1;float

23、 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;2 .一元非線性方程求根(1)牛頓迭代法牛頓迭代法又稱牛頓切線法：先任意設(shè)定一個與真實的根接近的值xO作為第一次近似根，由x0求出f(x0),過(x0 , f(x0)點做f(x)的切線，交x軸于x1，把它作為第二次近似根， 再由x1求出f(x1),過(x1，f(x1)點做f(x)的切線，交x軸于x2，如此繼續(xù)下去，直到足 夠接近(比如|x- x0|<1e-6時)真正的根x*為止

24、。而 f '(x0)=f(x0)/( x1- x0) 所以 x1= x0- f(x0)/ f ' (x0)例如，用牛頓迭代法求下列方程在 1.5附近的根：2x3-4x2+3x-6=0#i nclude "math.h"mai n() float x,x0,f,f1; x=1.5;do x0=x;f=2*x0*x0*x0-4*x0*x0+3*x0-6;f仁 6*x0*x0-8*x0+3;x=x0-f/f1;while(fabs(x-x0)>=1e-5); printf ("%fn",x);(2) 二分法算法要領(lǐng)是：先指定一個區(qū)間x1,

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

26、)和f(x2)不同號，則在區(qū)間x1, x2內(nèi)必有一個實根，執(zhí)行步驟(4)。(4) 求 x1 和 x2 的中點：x0=(x1+ x2 ) /2。(5 )求 f(xO)。(6) 判斷f(xO)與f(x1)是否同號。 如果同號，則應(yīng)在x0, x2中尋找根，此時x1已不起作用，用x0代替x1，用f(xO)代 替 f(x1)。 如果不同號，則應(yīng)在x1, x0中尋找根，此時x2已不起作用，用x0代替x2，用f(xO) 代替f(x2)。(7) 判斷f(xO)的絕對值是否小于某一指定的值(例如 1O-5)。若不小于1O-5，則返回 步驟(4)重復(fù)執(zhí)行步驟(4)、( 5)、( 6);否則執(zhí)行步驟(8)。(8)

27、輸出 x0 的值，它就是所求出的近似根。 例如，用二分法求方程 2x3-4x2+3x-6=0 在(-10 ，10)之間的根。 #include "math.h"main() float x1,x2,x0,fx1,fx2,fx0;do printf("Enter x1&x2"); scanf("%f%f",&x1,&x2); fx1=2*x1*x1*x1-4*x1*x1+3*x1-6; fx2=2*x2*x2*x2-4*x2*x2+3*x2-6;while(fx1*fx2>0);do x0=(x1+x2)/

28、2; fx0=2*x0*x0*x0-4*x0*x0+3*x0-6; if(fx0*fx1)<0) x2=x0; fx2=fx0; else x1=x0; fx1=fx0; while(fabs(fx0)>1e-5);printf("%fn",x0);3梯形法計算定積分定積分 的幾何意義是求曲線 y=f(x) 、x=a、x=b 以及 x 軸所圍成的面積?？梢越频匕衙娣e視為若干小的梯形面積之和。例如，把區(qū)間a, b分成n個長度相等的小區(qū)間，每個小區(qū)間的長度為 h=(b-a)/n，第i個小梯形的面積為f(a+(i-1) h)+f(a+i h) h/2， 將 n 個小

29、梯形面積加起來就得到定積分的近似值：根據(jù)以上分析，給出 “梯形法”求定積分的 N-S 結(jié)構(gòu)圖： 輸入?yún)^(qū)間端點： a，b 輸入等分?jǐn)?shù) n h=(b-a)/2, s=0i從1到nsi=(f(a+(i-1)*h)+f(a+i*h)*h/2s=s+si 輸出 s 上述程序的幾何意義比較明顯，容易理解。但是其中存在重復(fù)計算，每次循環(huán)都要計算小梯 形的上、下底。其實，前一個小梯形的下底就是后一個小梯形的上底，完全不必重復(fù)計算。 為此做出如下改進：矩形法求定積分則更簡單，就是將等分出來的圖形當(dāng)作矩形，而不是梯形。例如：求定積分 的值。等分?jǐn)?shù) n=1000 。 #include "math.h&qu

30、ot;float DJF(float a,float b) float t,h; int n,i;float HSZ(float x);n=1000; h=fabs(a-b)/n;t=(HSZ(a)+HSZ(b)/2;for(i=1;i<=n-1;i+) t=t+HSZ(a+i*h);t=t*h;return(t);float HSZ(float x) return(x*x+3*x+2); main() float y;y=DJF(0,4);printf("%fn",y);四、其他常見算法1迭代法 其基本思想是把一個復(fù)雜的計算過程轉(zhuǎn)化為簡單過程的多次重復(fù)。每次重復(fù)都從

31、舊值的 基礎(chǔ)上遞推出新值，并由新值代替舊值。例如，猴子吃桃問題。猴子第一天摘下若干個桃子，當(dāng)即吃了一半，還不過癮，又多吃 了一個。第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半零一個。 到第 10 天早上想再吃時， 就只剩一個桃子了。 編程求第一天共摘多少桃 子。main（） int day,peach;peach=1; for（day=9;day>=1;day-） peach=（peach+1）*2;printf（"The first day:%dn",peach）;又如，用迭代法求 x= 的根。求平方根的迭代公式是：Xn+1 =

32、0.5 Nxn+a/ xn ）算法（ 1）設(shè)定一個初值 x0。 （2）用上述公式求出下一個值 x1。（ 3）再將 x1 代入上述公式，求出下一個值 x2。（4）如此繼續(xù)下去，直到前后兩次求出的x 值（ xn+1 和 xn ）滿足以下關(guān)系：| xn+1- x n|<10 -5#include "math.h"main() float a,x0,x1;scanf("%f",&a);x0=a/2; x1=(x0+a/x0)/2;do x0=x1;x1=(x0+a/x0)/2;while(fabs(x0-x1)>=1e-5);printf(&

33、quot;%fn",x1);2進制轉(zhuǎn)換( 1 )十進制數(shù)轉(zhuǎn)換為其他進制數(shù)一個十進制正整數(shù) m轉(zhuǎn)換成r進制數(shù)的思路是，將m不斷除以r取余數(shù)，直到商為0時 止，以反序輸出余數(shù)序列即得到結(jié)果。注意，轉(zhuǎn)換得到的不是數(shù)值，而是數(shù)字字符串或數(shù)字串。 例如，任意讀入一個十進制正整數(shù)，將其轉(zhuǎn)換成二至十六任意進制的字符串。 void tran(int m,int r,char str,int *n) char sb="0123456789ABCDEF" int i=0,g;do g=m%r; stri=sbg; m=m/r; i+;while(m!=0);*n=i;main() i

34、nt x,r0; /*r0 為進制基數(shù) */int i,n; /*n 中存放生成序列的元素個數(shù) */char a50;scanf("%d%d",&x,&r0); if(x>0&&r0>=2&&r0<=16) tran(x,r0,a,&n); for(i=n-1;i>=0;i-) printf("%c",ai); printf("n");else exit(0); (2)其他進制數(shù)轉(zhuǎn)換為十進制數(shù) 其他進制整數(shù)轉(zhuǎn)換為十進制整數(shù)的要領(lǐng)是： “按權(quán)展開 ”，例如，

35、有二進制數(shù) 101011 ，則其十進制形式為1X25+0X24+1X23+0X22+1X21+1X20=43。若r進制數(shù)ana2a1 (n位數(shù)) 轉(zhuǎn)換成十進制數(shù)，方法是 anXr n-1+a2X r1+a1 X r0注意：其他進制數(shù)只能以字符串形式輸入。例 1 、任意讀入一個二至十六進制數(shù)(字符串)，轉(zhuǎn)換成十進制數(shù)后輸出。#include "string.h"#include "ctype.h"main() char x20; int r,d;gets(x); /* 輸入一個 r 進制整數(shù)序列 */ scanf("%d",&r

36、); /* 輸入待處理的進制基數(shù) 2-16*/ d=Tran(x,r);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<strlen(p);i+) c=*(p+i);if(toupper(c)>='A') cr=toupper(c)-'A'+10;else cr=c-'0'd=d*r+cr;if(fh='-') d=-d;ret

37、urn(d);3矩陣轉(zhuǎn)置nXm矩陣轉(zhuǎn)置的算法要領(lǐng)是：將一個m行n列矩陣(即mKn矩陣)的每一行轉(zhuǎn)置成另一個 矩陣的相應(yīng)列。例1、將以下2X3矩陣轉(zhuǎn)置后輸出。即將1 2 3轉(zhuǎn)置成 1 44 5 62 53 6main() int a23,b32,i,j,k=1;for(i=0;i<2;i+)for(j=0;j<3;j+)aij=k+;/*以下將a的每一行轉(zhuǎn)存到b的每一列*/for(i=0;i<2;i+)for(j=0;j<3;j+)bji=aij;for(i=0;i<3;i+)/* 輸出矩陣 b*/ for(j=0;j<2;j+)printf("%3

38、d",bij);printf("n");4字符處理 (1)字符統(tǒng)計：對字符串中各種字符出現(xiàn)的次數(shù)的統(tǒng)計。 典型例題：任意讀入一個只含小寫字母的字符串，統(tǒng)計其中每個字母的個數(shù)。#include "stdio.h "main() char a100; int n26=0; int i; /* 定義 26 個計數(shù)器并置初值 0*/ gets(a);for(i=0;ai!= '0' ;i+)/*n0中存放的個數(shù)，n1中存放的個數(shù)*/nai-'a' +; /*各字符的ASCII碼值減的ASCII碼值，正好得對應(yīng)計數(shù)器下標(biāo)*

39、/ for(i=0;i<26;i+)if(ni!=0) printf("%c :%dn ", i+'a', ni);(2)字符加密 例如、對任意一個只含有英文字母的字符串，將每一個字母用其后的第三個字母替代后輸出(字母X后的第三個字母為A，字母丫后的第三個字母為B，字母Z后的第三個字母為 C。)#include "stdio.h"#include "string.h"main() char a80= "China" int i;for(i=0; i<strlen(a); i+) if(a

40、i>='x'&&ai<='z'|ai>='X'&&ai<='Z') ai= ai-26+3; else ai= ai+3;puts(a);5整數(shù)各數(shù)位上數(shù)字的獲取算法核心是利用 “任何正整數(shù)整除 10的余數(shù)即得該數(shù)個位上的數(shù)字 ”的特點，用循環(huán)從低 位到高位依次取出整數(shù)的每一數(shù)位上的數(shù)字。例 1 、任意讀入一個 5 位整數(shù)，輸出其符號位及從高位到低位上的數(shù)字。main() long x; int w,q,b,s,g;scanf("%ld",&x);

41、if(x<0) printf("-,"); x=-x;w=x/10000;/* 求萬位上的數(shù)字 */q=x/1000%10;/* 求千位上的數(shù)字 */b=x/100%10;/* 求百位上的數(shù)字 */s=x/10%10;/* 求十位上的數(shù)字 */g=x%10;/* 求個位上的數(shù)字 */ printf("%d,%d,%d,%d,%dn",w,q,b,s,g);例 2 、任意讀入一個整數(shù)，依次輸出其符號位及從低位到高位上的數(shù)字。 分析此題讀入的整數(shù)不知道是幾位數(shù)，但可以用以下示例的方法完成此題：例如讀入的整數(shù)為3796 ,存放在x中，執(zhí)行x%10后得余數(shù)

42、為6并輸出；將x/10得379 后賦值給x。再執(zhí)行x%10后得余數(shù)為9并輸出；將x/10得37后賦值給x直到商x為0 時終止。main() long x; scanf("%ld",&x);if(x<0) printf("- "); x=-x;do /* 為了能正確處理 0，要用 do_while 循環(huán) */printf("%d ", x%10);x=x/10;while(x!=0);printf("n");例 3、任意讀入一個整數(shù)，依次輸出其符號位及從高位到低位上的數(shù)字。 分析此題必須借助數(shù)組將依次求

43、得的低位到高位的數(shù)字保存后，再逆序輸出。 main() long x; int a20,i,j;scanf("%ld",&x);if(x<0) printf("- "); x=-x; i=0;do ai=x%10;x=x/10; i+;while(x!=0);for(j=i-1;j>=0;j-) printf("%d ",aj);printf("n");6輾轉(zhuǎn)相除法求兩個正整數(shù)的最大公約數(shù)該算法的要領(lǐng)是：假設(shè)兩個正整數(shù)為 a和b，先求出前者除以后者的余數(shù)，存放到變量 r 中，若r不為0,則將b的

44、值得賦給a,將r的值得賦給b;再求出a除以b的余數(shù)，仍然存 放到變量r中如此反復(fù)，直至r為0時終止，此時b中存放的即為原來兩數(shù)的最大公約 數(shù)。例 1、任意讀入兩個正整數(shù)，求出它們的最大公約數(shù)。 法一 ：用 while 循環(huán)時，最大公約數(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);法二：用dowhile循環(huán)時

45、，最大公約數(shù)存放于 a中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ù)。提示：兩個正整數(shù)a和b的最小公倍數(shù)=axb/ 最大公約數(shù)。例 2、任意讀入兩個正整數(shù)，求出它們的最小公倍數(shù)。 法一：利用最大公約數(shù)求最小公倍數(shù) main() int a,b,r,x,y;do scanf("%

46、d%d",&a,&b); while(a<=0|b<=0);/*確保 a 和 b 為正整數(shù) */x=a; y=b; /* 保留 a、b 原來的值 */ 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=1;

47、while(a*i%b!=0) i+; printf("%dn",i*a);7求最值即求若干數(shù)據(jù)中的最大值(或最小值)。算法要領(lǐng)是：首先將若干數(shù)據(jù)存放于數(shù)組中， 通常假設(shè)第一個元素即為最大值(或最小值)，賦值給最終存放最大值(或最小值)的 max (或 min )變量中，然后將該量 max (或 min )的值與數(shù)組其余每一個元素進行比較，一旦 比該量還大(或小)，則將此元素的值賦給max (或min)所有數(shù)如此比較完畢，即可求得最大值(或最小值)。例 1、任意讀入 10 個數(shù)，輸出其中的最大值與最小值。#define N 10main() int aN,i,max,min

48、;for(i=0;i<N;i+) scanf("%d",&ai);max=min=a0;for(i=1;i<N;i+)if(ai>max) max=ai;else if(ai<min) min=ai;printf("max=%d,min=%dn",max,min);8判斷素數(shù)素數(shù)又稱質(zhì)數(shù)，即 “只能被 1 和自身整除的大于 1 的自然數(shù)”。判斷素數(shù)的算法要領(lǐng)就是 依據(jù)數(shù)學(xué)定義，即若該大于 1 的正整數(shù)不能被 2 至自身減 1 整除，就是素數(shù)。例 1、任意讀入一個正整數(shù)，判斷其是否為素數(shù)。main() int x,k;do

49、scanf("%d",&x);while(x<=1); /* 確保讀入大于 1的正整數(shù)*/for(k=2;k<=x-1;k+)if(x%k=0) break; /* 一旦能被 2 自身-1 整除，就不可能是素數(shù) */if(k=x) printf("%d is sushun",x);else printf("%d is not sushun",x); 以上例題可以用以下兩種變形來解決(需要使用輔助判斷的邏輯變量)： 【變形一】將“2自身-1”的范圍縮小至 “2自身的一半”main() int x,k,flag;do

50、scanf("%d",&x); while(x<=1);flag=1; /* 先假設(shè) x 就是素數(shù) */for(k=2;k<=x/2;k+)if(x%k=0) flag=0; break; /* 一旦不可能是素數(shù)，即置 flag 為 0*/if(flag=1) printf("%d is sushun",x);else printf("%d is not sushun",x); 【變形二】將 “2自身-1”的范圍縮小至 “2自身的平方根 ” #include "math.h" main() in

51、t x,k,flag; do scanf("%d",&x); while(x<=1); flag=1; /* 先假設(shè) x 就是素數(shù) */ for(k=2;k<=(int)sqrt(x);k+)if(x%k=0) flag=0; break; /* 一旦不可能是素數(shù)，即置 flag 為 0*/ if(flag=1) printf("%d is sushun",x); else printf("%d is not sushun",x);例 2 、用篩選法求得 100 以內(nèi)的所有素數(shù)。 算法為：(1)定義一維數(shù)組a，其初

52、值為：2, 3,，100 ;(2)若ak不為0,則將該元素以后的所有ak的倍數(shù)的數(shù)組元素置為0； ( 3) a 中不為 0 的元素，均為素數(shù)。#include <math.h>#include <stdio.h>main( ) int k,j,a101; clrscr(); /* 清屏函數(shù) */ for(k=2;k<101;k+)ak=k;for(k=2;k<sqrt(101);k+) for(j=k+1;j<101;j+) if(ak!=0&&aj!=0) if(aj%ak=0)aj=0;for(k=2;k<101;k+) if

53、(ak!=0)printf("%5d",ak);9數(shù)組元素的插入、刪除( 1 )數(shù)組元素的插入 此算法一般是在已經(jīng)有序的數(shù)組中再插入一個數(shù)據(jù),使數(shù)組中的數(shù)列依然有序。算法要 領(lǐng)是：假設(shè)待插數(shù)據(jù)為X，數(shù)組a中數(shù)據(jù)為升序序列。 先將 x 與 a 數(shù)組當(dāng)前最后一個元素進行比較,若比最后一個元素還大,就將 x 放入其 后一個元素中；否則進行以下步驟； 先查找到待插位置。從數(shù)組 a的第1個元素開始找到不比x小的第一個元素，設(shè)其下 標(biāo)為 i ； 將數(shù)組 a 中原最后一個元素至第 i 個元素依次一一后移一位，讓出待插數(shù)據(jù)的位置， 即下標(biāo)為 i 的位置； 將 x 存放到 a(i) 中。例題參見前面 “排序'中插入法排序的例 1”。(2)數(shù)組元素的刪除 此算法的要領(lǐng)是：首先要找到(也可能找不到)待刪除元素在數(shù)組中的位置(即下標(biāo))， 然后將待刪元素后的每一個元素向前移動一位，最后將數(shù)組元素的個數(shù)減 1。例 1 、數(shù)組 a