1、C程序設計的常用算法算法Algorithm：計算機解題的根本思想方法和步驟。算法的描述：是對要解決一個問題或要完成一項任務所采取的方法和步驟的描述，包括需要什么數據輸入什么數據、輸出什么結果、采用什么結構、使用什么語句以及如何安排這些語句等。通常使用自然語言、結構化流程圖、偽代碼等來描述算法。一、簡單數值類算法此類問題都要使用循環，要注意根據問題確定循環變量的初值、終值或結束條件，更要注意用來表示計數、和、階乘的變量的初值。1、 求階乘：n!=1*2*384.*n; n!= n*(n-1)!= 以下程序用于求n的階乘.在累乘之前,一定要將用于存放乘積的變量的值初始化為1.long func(i

2、nt n) int i; long t=1; for(i=2;i<=n;i+) t*=i; return t;printf("n");main() int n;scanf("%d", &n);printf("n!=%ldn", fac(n);2、整數拆分問題：把一個整數各個位上的數字存到數組中#define N 4 /* N代表整數位數*/viod split(int n, int a /* 1478: a 3=8, a2 =7, a1 =4*/int i; for(i=N-1;i!=0; i-) ai=n%10; n=

3、n/10; main()int i,m=1478,bN-1;split(m, b;for(i=0;i<4; i+)printf(“%5d, bi);3、求整數的因子之和12=1*2*3*4long factor(int n) int i; long sum=0; for(i=1;i<=n;i+) if(n%i= =0) sum+=i; return sum;注意：因子包括1和自身。二、求兩個整數的最大公約數、最小公倍數分析：求最大公約數的算法為輾轉相除法。(最小公倍數=兩個整數之積/最大公約數) 求最大公約數的算法步驟：(1) 對于兩數m，n，使得m>n；(2) m除以n得余

4、數r； r=m%n;(3) 假設r= =0，那么n為求得的最大公約數，算法結束；否那么執行(4)；(4) mn，nr，再重復執行(2)。例如: 求 m=14 ,n=6 的最大公約數. m n r14 %6= 26 %2= 0 輸出2void main() int nm,r,n,m,t;printf("please input two numbers:n");scanf("%d,%d",&m,&n);nm=n*m;if (m<n) t=n; n=m; m=t; r=m%n;while (r!=0) m=n; n=r; r=m%n; p

5、rintf("最大公約數:%dn",n);printf("最小公倍數:%dn", nm/n);將其寫成一函數,返回最大公約數。int gcd(int m,int n) int t,r; if(m<n) t=m;m=n;n=t; r=m%n; while(r!=0) m=n; n=r; r=m%n; return n;int gcd(int m,int n) int t,r; if(m<n) t=m;m=n;n=t; do r=m%n; m=n; n=r; while(n!=0) return m;如果求最小公倍數，其函數形式稍作調整：int

6、gcd(int m,int n) int a=m, b=n;int t,r; if(m<n) t=m;m=n;n=t; r=m%n; while(r!=0) m=n; n=r; r=m%n; return (a*b)/n;三、判斷素數只能被1和本身整除的正整數稱為素數。根本思想：在判斷數m是否為素數時，首先把m作為被除數，將2sqrt(m)的所有數字依次作為除數，去除m，只要有一個數能將m整除，那么m不是素數；否那么，如果都除不盡，那么m就是素數。可用以下程序段實現#include <math.h>void main() int m,i,k;printf("plea

7、se input a number:n");scanf("%d",&m);k=sqrt(m); /*使用此函數一定要加頭文件#include <math.h>*/for(i=2;i<k;i+)if(m%i=0) break;if(i>=k)printf("該數是素數");elseprintf("該數不是素數");將其寫成一函數,假設為素數返回1，不是那么返回0int prime( int m)int i,k;k=sqrt(m); /*使用此函數一定要加頭文件#include <math.

8、h>*/for(i=2;i<k;i+)if(m%i=0) return 0;return 1;四、求最值例如求最小值算法思想：定義變量min用于存放當前所有找到的最小數，a為數組。算法步驟如下：1在min中存放第1個數，比較從數組中的第二個元素開始。2數組a中每個元素依次與min中的數組相比，小者放入min中。3比較完數組的最后一個元素，算法結束。Min中數為所求。求最大值:max=a0; for(i=0;i<n;i+) if(ai>max) max=ai;程序如下：int minvalue(int a,int n)int i,min; min=a0; for(i=0;

9、i<n;i+) if(ai<min) min=ai; return min;main() int a10=12,45,7,8,96,4,10,48,2,46,i,min; for(i=0;i<10;i+) printf(“%3d,ai); printf(“n); min=minvalue(a,10); printf(“the result is:%d, min); 五、排序問題1選擇法排序升序根本思想：1對有n個數的序列存放在數組a(n)中，從中選出最小的數，與第1個數交換位置；2除第1 個數外，其余n-1個數中選最小的數，與第2個數交換位置；3依次類推，選擇了n-1次后，這

10、個數列已按升序排列。自定義函數形式void sort(int a, int n) int i,j,imin,s;for(i=0;i<n-1;i+) imin=i;for(j=i+1;j<n;j+)if(aimin>aj) imin=j;if(i!=imin)s=ai; ai=aimin; aimin=s; 程序代碼如下：void main() int i,j,imin,s,a10;printf("n input 10 numbers:n");for(i=0;i<10;i+)scanf("%d",&ai);for(i=0;i

11、<9;i+) imin=i;for(j=i+1;j<10;j+)if(aimin>aj) imin=j;if(i!=imin)s=ai; ai=aimin; aimin=s; printf("%dn",ai); 2冒泡法排序升序根本思想：(將相鄰兩個數比較，小的調到前頭)1有n個數存放在數組a(n)中，第一趟將每相鄰兩個數比較，小的調到前頭，經n-1次兩兩相鄰比較后，最大的數已“沉底，放在最后一個位置，小數上升“浮起；2第二趟對余下的n-1個數最大的數已“沉底按上法比較，經n-2次兩兩相鄰比較后得次大的數；3依次類推，n個數共進行n-1趟比較，在第j趟中要

12、進行n-j次兩兩比較。自定義函數形式：void sort(int a, int n) int i,j,t;for(j=0;j<=8;j+)for(i=0;i<9-j;i+)if(ai>ai+1)t=ai;ai=ai+1;ai+1=t; 程序段如下void main() int a10;int i,j,t;printf("input 10 numbersn");for(i=0;i<10;i+)scanf("%d",&ai);printf("n");for(j=0;j<=8;j+)for(i=0;i&

13、lt;9-j;i+)if(ai>ai+1)t=ai;ai=ai+1;ai+1=t;printf("the sorted numbers:n");for(i=0;i<10;i+)printf("%d，",ai); 3合并法排序將兩個有序數組A、B合并成另一個有序的數組C，升序根本思想：1先在A、B數組中各取第一個元素進行比較，將小的元素放入C數組；2取小的元素所在數組的下一個元素與另一數組中上次比較后較大的元素比較，重復上述比較過程，直到某個數組被先排完；3將另一個數組剩余元素抄入C數組，合并排序完成。程序段如下：void main() int

14、 a10,b10,c20,i,ia,ib,ic;printf("please input the first array:n");for(i=0;i<10;i+)scanf("%d",&ai);for(i=0;i<10;i+)scanf("%d",&bi);printf("n");ia=0;ib=0;ic=0;while(ia<10&&ib<10) if(aia<bib) cic=aia;ia+;else cic=bib;ib+;ic+;while(ia

15、<=9) cic=aia;ia+;ic+;while(ib<=9) cic=bib;ib+;ic+;for(i=0;i<20;i+)printf("%dn",ci);六、查找問題1順序查找法在一列數中查找某數x思考：將上面程序改寫一查找函數Find，假設找到那么返回下標值，找不到返回-1采用另外一種方法自定義函數，假設找到那么返回下標值，找不到返回-1：int seek(int a,int n, int x) int p=0;while(x!=ap&&p<n)p+;if(p>=n) return -1;else return p

16、;根本思想：一列數放在數組a1-an中，待查找的關鍵值為key，把key與a數組中的元素從頭到尾一一進行比較查找，假設相同，查找成功，假設找不到，那么查找失敗。(查找子過程如下。index：存放找到元素的下標。)void main() int a10,index,x,i;printf("please input the array:n");for(i=0;i<10;i+)scanf("%d",&ai);printf("please input the number you want find:n");scanf(&quo

17、t;%d",&x);printf("n");index=-1;for(i=0;i<10;i+)if(x=ai) index=i; break;if(index=-1)printf("the number is not found!n");elseprintf("the number is found the no%d!n",index);2折半查找法只能對有序數列進行查找根本思想：設n個有序數從小到大存放在數組a1-an中，要查找的數為x。用變量bot、top、mid 分別表示查找數據范圍的底部數組下界、頂部數

18、組的上界和中間，mid=(top+bot)/2，折半查找的算法如下：1x=a(mid)，那么已找到退出循環，否那么進行下面的判斷；2x<a(mid)，x必定落在bot和mid-1的范圍之內，即top=mid-1；3x>a(mid)，x必定落在mid+1和top的范圍之內，即bot=mid+1；4在確定了新的查找范圍后，重復進行以上比較，直到找到或者bot>=top。將上面的算法寫成如下程序：void main()int a10,mid,bot,top,x,i,find;printf("please input the array:n");for(i=0;i

19、<10;i+)scanf("%d",&ai);printf("please input the number you want find:n");scanf("%d",&x);printf("n");bot=0;top=9;find=0;while(bot<top&&find=0) mid=(top+bot)/2;if(x=amid) find=1;break;else if(x<amid) top=mid-1;else bot=mid+1;if (find=1)p

20、rintf("the number is found the no%d!n",mid);elseprintf("the number is not found!n");七、插入法把一個數插到有序數列中，插入后數列仍然有序根本思想：n個有序數從小到大存放在數組a(1)a(n)中，要插入的數x。首先確定x插在數組中的位置P；可由以下語句實現#define N 10void insert(int a,int x) int p, i;p=0;while(x>ap&&p<N)p+;for(i=N; i>p; i-)ai=ai-1;

21、ap=x;main() int aN+1=1,3,4,7,8,11,13,18,56,78, x, i;for(i=0; i<N; i+) printf("%d,", ai);printf("nInput x:");scanf("%d", &x);insert(a, x);for(i=0; i<=N; i+) printf("%d,", ai);printf("n");八、矩陣二維數組運算1矩陣的加、減運算C(i,j)=a(i,j)+b(i,j) 加法C(i,j)=a(i,j

22、)-b(i,j) 減法2矩陣相乘矩陣A有M*L個元素，矩陣B有L*N個元素，那么矩陣C=A*B有M*N個元素。矩陣C中任一元素 (i=1,2,m; j=1,2,n)#define M 2#define L 4#define N 3void mv(int aML, int bLN, int cMN) int i, j, k;for(i=0; i<M; i+)for(j=0; j<N; j+) cij=0;for(k=0; k<L; k+)cij+=aik*bkj;main() int aML=1,2,3,4,1,1,1,1;int bLN=1,1,1,1,2,1,2,2,1,2

23、,3,1, cMN;int i, j;mv(a,b,c);for(i=0; i<M; i+) for(j=0; j<N; j+)printf("%4d", cij);printf("n"); 3矩陣轉置算法思想：指將矩陣中元素的行下標和列下標交換，形成的新矩陣就是原矩陣的轉置矩陣。在轉置方陣時須注意，只用遍歷方陣的上三角形或下三角形，將其中的元素和其對應元素進行一次交換即可。如果是遍歷整個方陣，并將每個元素都和它對應元素交換，結果會發現方陣沒有發生變化，原因是每個元素都做了兩次交換，最終又換回到原來的位置上。例:有二維數組a(5,5)，要對它

24、實現轉置，可用下面兩種方式：#define N 3void ch1(int aNN) /*只遍歷方陣的上三角形*/ int i, j, t;for(i=0; i<N; i+)for(j=i+1; j<N; j+) t=aij;aij=aji;aji=t;void ch2(int aNN) /*只遍歷方陣的下三角形*/ int i, j, t;for(i=1; i<N; i+)for(j= 0; j<i; j+) t=aij;aij=aji;aji=t;main() int aNN=1,2,3,4,5,6,7,8,9, i, j;ch1(a); /*或ch2(a);*/f

25、or(i=0; i<N; i+) for(j=0; j<N; j+)printf("%4d", aij);printf("n");4求二維數組中最小元素及其所在的行和列 根本思路同一維數組，可用下面程序段實現以二維數組a34為例：變量minx中存放最小值，row,column存放最小值所在行列號#define N 4#define M 3void min(int aMN) int min, row, column, i, j;min=a00; row=0;column=0;for(i=0; i<M; i+)for(j=0; j<N

26、; j+)if(aij<min) min=aij;row=i;column=j; printf("Min=%dnAt Row%d,Column%dn", min, row, column);main() int aMN=1,23,45,-5,5,6,-7,6,0,33,8,15;min(a);九、迭代法算法思想：對于一個問題的求解x，可由給定的一個初值x0，根據某一迭代公式得到一個新的值x1，這個新值x1比初值x0更接近要求的值x；再以新值作為初值，即：x1x0,重新按原來的方法求x1,重復這一過和直到|x1-x0|<(某一給定的精度)。此時可將x1作為問題的解

27、。例：用迭代法求某個數的平方根。 求平方根的迭代公式為： #include <math.h>float fsqrt(float a) float x0, x1;x1=a/2;dox0=x1;x1=0.5*(x0+a/x0); while(fabs(x1-x0)>0.00001);return(x1);main() float a;scanf("%f", &a);printf("genhao =%fn", fsqrt(a);十、數制轉換將一個十進制整數m轉換成 r(216)進制字符串。方法：將m不斷除 r 取余數，直到商為零，以反

28、序得到結果。下面寫出一轉換函數，參數idec為十進制數，ibase為要轉換成數的基如二進制的基是2，八進制的基是8等，函數輸出結果是字符串。char *trdec(int idec, int ibase) char strdr20, t;int i, idr, p=0;while(idec!=0) idr=idec % ibase;if(idr>=10)strdrp+=idr-10+65;elsestrdrp+=idr+48;idec/=ibase;main() int x, d;scanf("%d%d", &x, &d);printf("%

29、sn", trdec(x,d);for(i=0; i<p/2; i+) t=strdri;strdri=strdrp-i-1;strdrp-i-1=t;strdrp=0;return(strdr);十一、字符串的一般處理1簡單加密和解密加密的思想是： 將每個字母C加或減一序數K，即用它后的第K個字母代替，變換式公式： c=c+k例如序數k為5，這時 A F， af，B?G 當加序數后的字母超過Z或z那么 c=c+k -26例如：You are good Dtz fwj ltti 解密為加密的逆過程將每個字母C減或加一序數K，即 c=c-k,例如序數k為5，這時 ZU，zu，YT

30、 當加序數后的字母小于A或a那么 c=c-k +26下段程序是加密處理：#include<stdio.h>char *jiami(char stri) int i=0;char strp50,ia;while(strii!=0) if(strii>=A&&strii<=Z) ia=strii+5;if (ia>Z) ia-=26;else if(strii>=a&&strii<=z) ia=strii+5;if (ia>z) ia-=26;else ia=strii;strpi+=ia;strpi=0;return

31、(strp);main() char s50;gets(s);printf("%sn", jiami(s);2統計文本單詞的個數 輸入一行字符，統計其中有多少個單詞，單詞之間用格分隔開。算法思路：1從文本字符串的左邊開始，取出一個字符；設邏輯量word表示所取字符是否是單詞內的字符，初值設為02假設所取字符不是“空格，“逗號，“分號或“感慨號等單詞的分隔符，再判斷word是否為1，假設word不為1那么表是新單詞的開始，讓單詞數num = num +1，讓word =1;3假設所取字符是“空格，“逗號，“分號或“感慨號等單詞的分隔符， 那么表示字符不是單詞內字符，讓word=0;(4) 再依次取下一個字符，重得2(3)直到文本結束。下面程序段是字符串string中包含的單詞數#include "stdio.h"main()char c,string80;int i,num=0,word=0;gets(string);for(i=0;(c=stringi)!='0'i+)if(c=' ') word=0;el