C語言基本算法(簡單級別)

1、C語言常用算法一、基本 1交換（兩量交換借助第三者）例1、任意讀入兩個整數(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為中間變量，起到“空杯子”的作用。注意：三句賦值語句賦值號左右的各量之間的

2、關(guān)系！【應(yīng)用】例2、任意讀入三個整數(shù)，然后按從小到大的順序輸出。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í)行，

3、從而實現(xiàn)累加功能?！癆”通常是有規(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 = i + 1”為特殊的累加式，每次累加的值為1，這樣的累加器又稱為計數(shù)器。3累乘累乘算法的要領(lǐng)是形如“s=s*A”的累乘式，此式必須出現(xiàn)在循環(huán)中才能被反復(fù)執(zhí)行，

4、從而實現(xiàn)累乘功能。“A”通常是有規(guī)律變化的表達式，s在進入循環(huán)前必須獲得合適的初值，通常為1。例1、求10！分析10！=1×2×3××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ù)相等

5、，比如：13+53+33=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+) for(s=0

6、;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ù)為9×10×10=900），即900個三位正整數(shù)。與法一判斷的次數(shù)一樣。2排序（1）冒泡排序（起泡排序）假設(shè)要對含有n個數(shù)的序列進行升

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

8、) /*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ù)的下標（算法見下面的“求最值”），然后將最小數(shù)與第1個數(shù)交換位置；除第1個數(shù)以外，再從其余n-1個數(shù)中找出最小數(shù)（即n個數(shù)中的次小數(shù)）的下標，將此數(shù)與第2個數(shù)交換位置；重復(fù)步驟n-1趟，即可完成所

9、求。例1、任意讀入10個整數(shù)，將其用選擇法按升序排列后輸出。#define n 10 main()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記錄其下標*/ for(j=i+1;j<n;j+) if(aj < ak) k = j; if (k != i)t = ai; ai = ak; ak = t; for(i=0;i<n;i+) printf(&quo

10、t;%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(x>an-2) an-1=x ; /*比最后一個數(shù)還大就往最后一個元素中存放*/ else /*查找待插位置*/ j=0; whi

11、le( j<=n-2 && x>aj) j+; /*從最后一個數(shù)開始直到待插位置上的數(shù)依次后移一位*/ for(k=n-2; k>=j; k- -) ak+1=ak; aj=x; /*插入待插數(shù)*/ for(j=0;j<=n-1;j+) printf("%d ",aj);插入法排序的要領(lǐng)就是每讀入一個數(shù)立即插入到最終存放的數(shù)組中，每次插入都使得該數(shù)組有序。例2、任意讀入10個整數(shù)，將其用插入法按降序排列后輸出。#define n 10 main()int an,i,j,k,x; scanf("%d",&a0

12、); /*讀入第一個數(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&&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;

13、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,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=a

14、i; 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ù)全部存放到c中*/ ck=ai; k+; i+; for(i=0;i<m+n;i+) printf("%d ",ci);3查找（1）順序查找（即線性查找）順序查找的思路是：將待查找的量與數(shù)組中的每一個元素進行比較，若有一個元素與之相等則找到；若沒有一個元

15、素與之相等則找不到。例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); /*以下讀入待查找數(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

16、");（2）折半查找（即二分法）順序查找的效率較低，當(dāng)數(shù)據(jù)很多時，用二分法查找可以提高效率。使用二分法查找的前提是數(shù)列必須有序。二分法查找的思路是：要查找的關(guān)鍵值同數(shù)組的中間一個元素比較，若相同則查找成功，結(jié)束；否則判別關(guān)鍵值落在數(shù)組的哪半部分，就在這半部分中按上述方法繼續(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",&

17、amp;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ū)間下界*/ 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)鍵是“描述出通項”，而通項的描述法有兩種：一為直接法、二

18、為間接法又稱遞推法。直接法的要領(lǐng)是：利用項次直接寫出通項式；遞推法的要領(lǐng)是：利用前一個（或多個）通項寫出后一個通項?？梢杂弥苯臃枋鐾椀募墧?shù)計算例子有：（1）1+2+3+4+5+（2）1+1/2+1/3+1/4+1/5+等等?？梢杂瞄g接法描述通項的級數(shù)計算例子有：（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(&qu

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

20、 /*以下求下一項的分子分母*/ fz1=fz; /*將前項分子值保存到fz1中*/ fz=fm; /*后項分子等于前項分母*/ fm=fz1+fm; /*后項分母等于前項分子、分母之和*/ t=fz/fm; printf("1+1/2+2/3+.=%fn",s);下面舉一個通項的一部分用直接法描述，另一部分用遞推法描述的級數(shù)計算的例子：例3、計算級數(shù)的值，當(dāng)通項的絕對值小于eps時計算停止。#include <math.h>float g(float x,float eps);main()float x,eps; scanf("%f%f",

21、&x,&eps); printf("n%f,%fn",x,g(x,eps);float g(float x,float eps)int n=1;float 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迭代法其基本思想是把一個復(fù)雜的計算過程轉(zhuǎn)化為簡單過程的多次重復(fù)。每次重復(fù)都從舊值的基礎(chǔ)上遞推出新值，并由新值代替舊值。例如，猴子吃桃問題。猴子第一天摘下若干個桃子，當(dāng)

22、即吃了一半，還不過癮，又多吃了一個。第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半零一個。到第10天早上想再吃時，就只剩一個桃子了。編程求第一天共摘多少桃子。main()int day,peach; peach=1; for(day=9;day>=1;day-) peach=(peach+1)*2; printf("The first day:%dn",peach);2進制轉(zhuǎn)換（1）十進制數(shù)轉(zhuǎn)換為其他進制數(shù)一個十進制正整數(shù)m轉(zhuǎn)換成r進制數(shù)的思路是，將m不斷除以r取余數(shù)，直到商為0時止，以反序輸出余數(shù)序列即得到結(jié)果。注意，轉(zhuǎn)換得到的不

23、是數(shù)值，而是數(shù)字字符串或數(shù)字串。例如，任意讀入一個十進制正整數(shù)，將其轉(zhuǎ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; i+; while(m!=0); *n=i;main()int x,r0; /*r0為進制基數(shù)*/ int i,n; /*n中存放生成序列的元素個數(shù)*/ char a50; scanf("%d%d",&x,&r0); if(x>0&a

24、mp;&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)展開”，例如，有二進制數(shù)101011，則其十進制形式為1×25+0×24+1×23+0×22+1×21+1×20=43。若r進制數(shù)ana2a1（n位數(shù)）轉(zhuǎn)換成十進制數(shù)，方法是an&#

25、215;r n-1+a2×r1+a1×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); /*輸入待處理的進制基數(shù)2-16*/ d=Tran(x,r); printf("%s=%dn",x,d);int Tran(char *p

26、,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; return(d); 4字符處理（1）字符統(tǒng)計：對字符串中各種字符出現(xiàn)的次數(shù)的統(tǒng)計。典型例題：任意讀入一個只含小寫字母的字符串，統(tǒng)計其中每個字母的個數(shù)。#incl

27、ude "stdio.h "main()char a100; int n26=0; int i; /*定義26個計數(shù)器并置初值0*/ gets(a); for(i=0;ai!= '0' ;i+) /*n0中存放a的個數(shù)，n1 中存放b的個數(shù)*/ nai-'a' +; /*各字符的ASCII碼值減去a的ASCII碼值，正好得到對應(yīng)計數(shù)器下標*/ for(i=0;i<26;i+) if(ni!=0) printf("%c :%dn ", i+'a', ni);（2）字符加密例如、對任意一個只含有英文字母的

28、字符串，將每一個字母用其后的第三個字母替代后輸出（字母X后的第三個字母為A，字母Y后的第三個字母為B，字母Z后的第三個字母為C。） #include "stdio.h"#include "string.h"main()char a80= "China" int i; for(i=0; i<strlen(a); i+) if(ai>='x'&&ai<='z'|ai>='X'&&ai<='Z') ai= ai-26

29、+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); if(x<0) printf("-,"); x=-x; w=x/10000; /*求萬位上的數(shù)字*/ q=x/1000%10; /*求千位上的數(shù)字*/ b=x/100%10; /*求百位上的數(shù)

30、字*/ 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ù)為6并輸出；將x/10得379后賦值給x。再執(zhí)行x%10后得余數(shù)為9并輸出；將x/10得37后賦值給x直到商x為0時終止。main()long x; scanf("%ld",&x); if(x&l

31、t;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ù)組將依次求得的低位到高位的數(shù)字保存后，再逆序輸出。main()long x; int a20,i,j; scanf("%ld",&x); if(x<0) printf("- "); x=-

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

33、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)時，最大公約數(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; w

34、hile(r!=0); printf("%dn",a);【引申】可以利用最大公約數(shù)求最小公倍數(shù)。提示：兩個正整數(shù)a和b的最小公倍數(shù)=a×b/最大公約數(shù)。例2、任意讀入兩個正整數(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原來的值*/ r=a%b; while(r!=0) a=b;b=r;r=a%b; printf(&qu

35、ot;%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; while(a*i%b!=0) i+; printf("%dn",i*a);7求最值 即求若干數(shù)據(jù)中的最大值（或最小值）。算法要領(lǐng)是：首先將若干數(shù)據(jù)存放于數(shù)組中，通常假設(shè)第一個元素即為最大值（或最小值），賦值給最終存放最大值（或最小值）的max（或min）變量中，然后

36、將該量max（或min）的值與數(shù)組其余每一個元素進行比較，一旦比該量還大（或?。?，則將此元素的值賦給max（或min）所有數(shù)如此比較完畢，即可求得最大值（或最小值）。例1、任意讀入10個數(shù)，輸出其中的最大值與最小值。#define N 10main()int aN,i,max,min; 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=%d

37、n",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 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

38、); else printf("%d is not sushun",x);以上例題可以用以下兩種變形來解決（需要使用輔助判斷的邏輯變量）：【變形一】將“2自身-1”的范圍縮小至“2自身的一半”main()int x,k,flag; do 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()int x,k,flag; do scanf("%d",&x);