C程序設(shè)計的常用算法匯編

信息技術(shù)學(xué)院計算機(jī)基礎(chǔ)教學(xué)部2011最新修訂

算法(Algorithm)：計算機(jī)解題的基本思想方法和步驟。算法的描述：是對要解決一個問題或要完成

一項任務(wù)所采取的方法和步驟的描述，包括需要什么數(shù)據(jù)(輸入什么數(shù)據(jù)、輸出什么結(jié)果)、采用什么結(jié)

構(gòu)、使用什么語句以及如何安排這些語句等。通常使用自然語言、結(jié)構(gòu)化流程圖、偽代碼等來描述算法。

一、簡單數(shù)值類算法

此類問題都要使用循環(huán)，要注意根據(jù)問題確定循環(huán)變量的初值、終值或結(jié)束條件，更要注意用來表示

計數(shù)、和、階乘的變量的初值。

1、求階乘4、求回文數(shù)的函數(shù)

下列程序用于求n的階乘.在累乘之前，

一定要將用于存放乘積的變量的值初始化為1.inthws(inta)

longfunc(intn){intc=0;

(while(a>0)

inti;{c=c*10+a%10;

longt=1;a/=I0;

fbr(i=2;i<=n;i++))

t*=i;rcturn(c);

returnt;

printf("\n");

2、整數(shù)拆分問題：把一個整數(shù)各個位上的數(shù)字存到數(shù)組中

(1)確定3位數(shù)(2)不確定數(shù)字位數(shù),

利用數(shù)組存儲數(shù)字利用變量存儲數(shù)字?jǐn)?shù)組定義足夠大

#defineN3a,b,c依次保存?zhèn)€十百位

viodsplit(in(n,int)intsplit(intn,inta[10])

a[]a=n%10;

{inti;{inti;

b=n/10%10;

for(i=N-l;n!=0;i—)for(i=0;n!=0;i++)

c=n/100%10;

{a[il=n%IO;{a[i]=n%I0;

n=n/10;n=n/10;

)

}returni;/*返回數(shù)字個數(shù)*/

}

3、求整數(shù)的因子之和，注意：因子包括1和自身。

longfactor(intn)

{inti;

longsum=0;

for(i=l;i<=n;i++)

if(n%i==0)

sum+=i;

returnsum;

二、求兩個整數(shù)的最大公約數(shù)、最小公倍數(shù)

分析：求最大公約數(shù)的算法為輾轉(zhuǎn)相除法。(最小公倍數(shù)二兩個整數(shù)之積/最大公約數(shù))

求最大公約數(shù)的算法步驟：

(1)對于已知兩數(shù)m,n,使得m>n；

⑵m除以n得余數(shù)r；

(3)若r=0,則n為求得的最大公約數(shù)，算法結(jié)束；否則執(zhí)行(4)；

(4)m-n,n-r,再重復(fù)執(zhí)行(2)。

例如：求m=14,n=6的最大公約數(shù).mnr

14%6=2

6%2=0

voidmain()

{int

printf("pleaseinputtwonumbers:\nn);

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;}

printf("最大公約數(shù):%d\ii",n);

printff最小公倍數(shù):％d\n”,nm/n);

)

將其寫成一函數(shù)，返回最大公約數(shù)。

in(gcd(intm,intn)

{intt,r;

if(m<n){t=m;m=n;n=t;}

r=m%n;

while(r!=0)

{m=n;n=r;r=m%n;}

returnn;

)

如果求最小公倍數(shù)，其函數(shù)形式稍作調(diào)整：

intgcd(in(m,intn)

{inta=m,b=n;

intt,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;

三、判斷素數(shù)

只能被1和本身整除的正整數(shù)稱為素數(shù)。

基本思想：在判斷數(shù)m是否為素數(shù)時，首先把m作為被除數(shù)，將2—sqrt(m)的所有數(shù)字依次作為除數(shù),

去除m,只要有一個數(shù)能將m整除，則m不是素數(shù)；否則，如果都除不盡，則m就是素數(shù)。(可用以卜.程

序段實現(xiàn))

#include<math.h>

voidmain()

{intm,i,k;

printf("pleaseinputanumberin'');

scanf("%d".&m);

k=sqrt(m);/*使用此函數(shù)一定要加頭文件#include<math.h>*/

for(i=2;i<=k;i++)

if(m%i==0)break;

if(i>k)

printf("該數(shù)是素數(shù))

else

printf(”該數(shù)不是素數(shù))

)

將其寫成一函數(shù),若為素數(shù)返回1,不是則返回0

intprime(intm)

{inti;

if(m==l)return0;

fbr(i=2;i<=ni-l;i++)

if(m%i==0)return0;

return1;

)

四、求最值

例如求最小值算法思想：

定義變量min用于存放當(dāng)前所有找到的最小數(shù)，a為已知數(shù)組。算法步驟如下：

1)在min中存放第1個數(shù)，比較從數(shù)組中的第二個元素開始。

2)數(shù)組a中每個元素依次與min中的數(shù)組相比，小者放入min中。

3)比較完數(shù)組的最后一個元素，算法結(jié)束。Min中數(shù)為所求。

程序如下：

intminvalue(inta[],inln)

{int求最大值：

min=a[01；rnax=a(O];

for(i=0;i<n;i++)for(i=0;i<n;i++)

if(a[i]<min)min=a[i];if(a[i]>max)max=a[i];

returnmin;

)

main()

{inta[10]={12,45,7,8,96,4,10,48,2,46},i,min;

for(i=0;i<10;i++)

printf("\n")；min=minvalue(a,10);printf(<4theresultis:%d,\min);}

五、排序問題

1.選擇法排序(升序)

基本思想：

1)對有n個數(shù)的序列(存放在數(shù)組a(n)中)，從中選出最小的數(shù)，與第1個數(shù)交換位置;

2)除第I個數(shù)外，其余n-1個數(shù)中選最小的數(shù)，與第2個數(shù)交換位置；

3)依次類推，選擇了n-1次后，這個數(shù)列已按升序排列。

程序代碼如下：

voidrnain()自定義函數(shù)形式

{inti.j,imin,s,a|10|;voidsort(inla[],intn)

printf("\ninput10numbcrs:\n');{inti,j,imin,s;

for(i=0;i<IO;i++)for(i=0;i<n-l;i++)

scanf("%d",&a[i]);{imin=i;

for(i=0;i<9;i++)fbr(j=i+l;j<n;j++)

{imin=i;if(a[imin]>a[jl)imin=j;

for(j=i+l；j<IO;j++)if(i!=imin)

if(a[imin]>a[j])imin^j;{s=a[i];a[i]=a[imin];a[iminl=s;}

if(i!=imin)

{s=afi];a[i]=a[iminl;a[imin]=s;}

printf("%d\n",a[i]);

2.冒泡法排序(升序)

基本思想：(將相鄰兩個數(shù)比較，小的調(diào)到前頭)

I)有n個數(shù)(存放在數(shù)組a(n)中)，第一趟將每相鄰兩個數(shù)比較，小的調(diào)到前頭，經(jīng)n-1次兩兩相鄰

比較后，最大的數(shù)已“沉底”，放在最后一個位置，小數(shù)上升“浮起”；

2)第二趟對余下的n-1個數(shù)(最大的數(shù)己“沉底”)按上法比較，經(jīng)n-2次兩兩相鄰比較后得次大的

數(shù)；

3)依次類推，n個數(shù)共進(jìn)行n-1趟比較，在第j趟中要進(jìn)行n?j次兩兩比較。

程序段如下

voidmain()

{inta[10];

自定義函數(shù)形式：

inti,j,t;

printf("input10numbers?");voidsort(inta[],intn)

for(i=0;i<IO;i++){int

scanf("%d'\&afi]);for(j=D；j<=8;j++)

printf("\n");fbr(i=0;i<9-j;i++)

for(j=0;j<=8;j++)if(a[i]>a[i+l])

for(i=0;i<9-j;i++){t=a[i];a[i]=a[i+l];a[i+l]=t;)

if(a[i]>a[i+l])

{t=a[i];a[i]=a[i+1];a[i+l]=t;}

printf("thesortednumbers:\n");

for(i=0;i<10;i++)

prinlf("%d\n",a[i]);

}

3.合并法排序(將兩個有序數(shù)組A、B合并成另個有序的數(shù)組C,力序)

基本思想：

1)先在A、B數(shù)組中各取第一個元素進(jìn)行比較，將小的元素放入C數(shù)組；

2)取小的元素所在數(shù)組的下一個元素與另一數(shù)組中上次比較后較大的元素比較，重復(fù)上述比較過程,

直到某個數(shù)組被先排完；

3)將另一個數(shù)組剩余元素抄入C數(shù)組，合并排序完成。

程序段如下：

voidmain()

{inta[10],b[10],c[20]JJa,ib,ic;

printt("pleaseinputthefirstarray:\n");

for(i=0;i<10;i++)

scanf("%d",&a[i]);

for(i=0;i<10;i++)

scanf("%d",&b[i]);

printf("\n");

ia=O;ib=O;ic=O;

while(ia<10&&ib<10)

{if(a[ia]<b[ib])

{c[ic]=a[ia];ia++;(

else

{c[ic]=b[ib];ib++;}

ic++;

)

while(ia<=9)

{clicj=a[iaj;

ia++;ic++;

I

while(ib<=9)

{c[ic]=b[ib];

ib++;ic++;

)

for(i=0;i<20;i++)

printf("%d\n",c[i]);

六、查找問題

1.①順序查找法(在一列數(shù)中查找某數(shù)X)

思考：將上面程序改寫一查找函數(shù)Find,若找到則返回下標(biāo)值，找不到返回-1

②基本思想：一列數(shù)放在數(shù)組a[l]…a[n]中，待杳找的關(guān)鍵值為key,把key與a數(shù)組中的元素從頭到

尾一一進(jìn)行比較查找，若相同，查找成功，若找不到，則查找失敗。(查找子過程如下。index：存放找到

元素的下標(biāo)。)

voidmain()

{inta[10],index,x,i；采用另外一種方法自定義函數(shù),若找到

printf("pleaseinputthearrayAn");則返回下標(biāo)值，找不到返回-1：

for(i=0;i<IO;i++)intscck(inta[],intn,intx)

scanf("%d",&ali]);[intp=0;

printf("pleaseinput(henumberyouwantflndAn1');while(x!=a[p]&&p<n)

scanf("%d'\&x);p++；

printf("\n");if(p>=n)return-1;

index="l;elsereturnp;

for(i=();i<IO;i++)

if(x==a[i])

{index=i;break;

I

if(index==-l)

printf("thenumberisnotfbund!\n");

else

printf("thenumberisfoundtheno%d!\n",index);

)

2.折半查找法(只能對有序數(shù)列進(jìn)行查找)

基本思想：設(shè)n個有序數(shù)(從小到大)存放在數(shù)組a[n]中，要查找的數(shù)為x。用變量bol、top、

mid分別表示杳找數(shù)據(jù)范圍的底部(數(shù)組下界)、頂部(數(shù)組的上界)和中間，mid=(top+bot)/2,折半查找

的算法如下：

(1)x=a(mid),則已找到退出循環(huán),否則進(jìn)行下面的判斷;

(2)x<a(mid),x必定落在bol和mid-1的范圍之內(nèi)，即top=mid-l；

(3)x>a(mid),x必定落在mid+1和top的范圍之內(nèi),BPbot=mid+l；

(4)在確定了新的查找范圍后，重生進(jìn)行以上比較，直到找到或者bot>=top°

將上面的算法寫成如下程序：

voidmain()

(

intaf10Lmid,bot,top,x,i,find;

printf("pleaseinputthearray:\n");

for(i=0;i<10;i++)

scanf("%d",&a[i]);

printf("pleaseinputthenumberyouwantfind:\n");

scanf("%d",&x);

prinlf("\n");

bot=0:top=9;find=0;

while(bot<(op&&find==0)

{mid=(top+bot)/2;

if(x=a[mid]){find=l;break;}

elseif(A<a[inid])lup-iiiid-1;

elsebot=mid+1;

if(find==l)

prinlf("thenumberisfound(heno%d!\n",mid);

else

printf("thenumberisnotfbund!\n");

七、插入法

把一個數(shù)插到有序數(shù)列中，插入后數(shù)列仍然有序

基本思想：n個有序數(shù)(從小到大)存放在數(shù)組a(l)—a(n)中，要插入的數(shù)X。首先確定x插在數(shù)組中

的位置P；(可由以下語句實現(xiàn))

#defineN10

voidinsert(inta[].intx)

{intp,i;

p=0;

whi!e(x>a[p]&&p<N)

P++；

for(i=N;i>p;i-)

a[i]=a[i-l];

a[p]=x;

)

main()

{inta[N+1]={1,34,7,8,11,13,18,56,78},x,i;

for(i=0;i<N;i++)prinlf("%d,",a[i]);

printf("\nlnputx:");

scanf("%d'\&x);

insert(a,x);

for(i=0;i<=N;i++)printf("%d,H,a[ij);

printf("\n");

八、矩陣(二維數(shù)組)運算

(1)矩陣的加、減運算

C(ij)=a(ij)+b(iJ)加法

C(i,j)=a(i,j)-b(iJ)減法

(2)矩陣相乘

(矩陣A有M*L個元素，矩陣B有L*N個元素，則矩陣C=A*B有M*N個元素)。矩陣C中任一元

素(i=l,2,…,m;j=l,2,…,n)

#defineM2

#defineL4

#detineN3

voidmv(inta[MJ[L],intb[L][N],intc[MJ[NJ)

{inti,j,k;

for(i=0;i<M;i++)

for(j=0;j<N;j++)

{c[i]U]=0;

for(k=0;k<L;k++)

c[i]Ul+=a[i][k]*b[k][j]：

main()

{inta[M][L]={{1,2,3,4),{1,1,U))；

intb[L][N]={{1}1,1},{1,2,1},{2,2,1},{2,3,1}},c[M][N];

inti,j;

mv(a,b,c);

for(i=0;i<M;i++)

{for(j=0；j<N;j++)

pnntf("%4d",c[i]|j]);

printf("\n");

(3)矩陣轉(zhuǎn)置

算法思想：指將矩陣中元素的行下標(biāo)和列下標(biāo)交換，形成的新矩陣就是原矩陣的轉(zhuǎn)置矩陣。

在轉(zhuǎn)置方陣時須注意，只用遍歷方陣的上三角形(或下三帶形)，將其中的元素和其對應(yīng)元素進(jìn)行一

次交換即可。如果是遍歷整個方陣，并將每個元素都和它對應(yīng)元素交換，結(jié)果會發(fā)現(xiàn)方陣沒有發(fā)生變化，

原因是每個元素都做了兩次交換，最終乂換回到原來的位置上。

例:有二維數(shù)組a(5,5),要對它實現(xiàn)轉(zhuǎn)置，可用下面兩種方式：

#defineN3

voidchi(inta[N][Nl)/*只遍歷方陣的上三角形*/

{inti,j,t;

for(i=0;i<N;i++)

fbr(j=i+l;j<N;j++)

{t=a[i][j];

aUl[i]=t；

)

voidch2(inta[N][NJ)/*只遍歷方陣的下三角形*/

{inii,j,I；

for(i=I;i<N;i++)

for(j=O;j<i;j++)

{t=a[i][j];

a[i][j]=aUl[i]；

a|j][i]=t;

main()

{inta[NJ[N曰{1,2,3},{4,5,6J,{7,8,9)},i,j;

chl(a);/*或ch2(a);*/

for(i=0;i<N;i++)

{for(j=0;j<N;j++)

printf("%4d,',a[i][j])；

printf("\n");

(4)求二維數(shù)組中最小元素及其所在的行和列

基本思路同一維數(shù)組，可用下面程序段實現(xiàn)(以二維數(shù)組a[3][4]為例):

'變量minx中存放最小值，row,column存放最小值所在行列號

#defineN4

#defineM3

voidmin(inta[Mj[NJ)

{intmin,row,column,i,j;

min=alOJlOJ;

row=0;

column：。；

for(i=0;i<M;i++)

for(j=0;j<N;j++)

if(a[i][j]<min)

{min=a[i]Ul；

row=i;

column=j;

)

prinlf("Min=%d\nAtRow%d,Column%d\n",min,row,column)；

)

main()

{inta[M][N]={{1,23,45,-5},{5,6,-7,6},{0,33,8,15}};

min(a);

九、迭代法

算法思想：對于一個問題的求解X,可由給定的一個初值xO,根據(jù)某一迭代公式得到一個新的值xl,

這個新值xl比初值xO更接近要求的值x；再以新值作為初值，即：xl-xO,重新按原來的方法求xl,重復(fù)

這一過和直到|xI-xO|<E(某一給定的精度)。此時可將X1作為問題的解。

例：用迭代法求某個數(shù)的平方根。已知求平方根的迭代公式為：

#include<math.h>

floatfsqrt(floata)

{floatxO,x1;

xl=a/2;

do{

xO=x1;

xl=0.5*(x0+a/x0);

}while(fabs(x1-x0)>0.00001);

return(xl);

)

main()

{floata;

scanf("%f,&a);

printf("genhao=%f\n",fsqrl(a));

)

十、數(shù)制轉(zhuǎn)換

將一個十進(jìn)制整數(shù)m轉(zhuǎn)換成-*r(2—l6)進(jìn)制字符串。

方法：將m不斷除r取余數(shù)，直到商為零，以反序得到結(jié)果。下面寫出一轉(zhuǎn)換函數(shù)，參數(shù)idee為十

進(jìn)制數(shù)，ibase為要轉(zhuǎn)換成數(shù)的基(如二進(jìn)制的基是2,八進(jìn)制的基是8等)，函數(shù)輸出結(jié)果是字符串。

char*trdec(intidee,intibase)

{charstrdr[2O],t;

inti,idr,p=0;

while(idec!=O)

{idr=idec%ibase;

if(idr>=10)

strdr[p++J=idr-10+65;

else

strdr[p++]=idr+48;

idec/=ibase;

}

for(i=0;i<p/2;i++)

{t=strdr[i];main()

strdr[i]=strdr[p-i-1];{intx,d;

strdr[p-i-1]=t;scanf("%d%d”,&x,&d);

)printf("%s\n",trdec(x,d));

strdr[p]=>\0';

return(strdr);

十一、字符串的一般處理

1.簡單加密和解密

加密的思想是：將每個字母C力口(或減)一序數(shù)K,即用它后的第K個字母代替，變換式公式：c=c+k

例如序數(shù)k為5,這時A-F,a-*f,B-?G…當(dāng)加序數(shù)后的字母超過Z或z則c=c+k-26

例如：Youaregood-*Dtzfv/jkti

解密為加密的逆過程

將每個字母C減(或加)一序數(shù)K,即c=c-k,

例如序數(shù)k為5,這時Z-*U,z-u,Y—T…當(dāng)加序數(shù)后的字母小于A或a則c=c-k+26

下段程序是加密處理：

#include<stdio.h>

char*jiami(charstriU)

{inti=0;

charstrp[50],ia;

while(stri[i]]=>\0')

{if(stri[i]>=,A'&&stri[i]<=,Z')

{ia=striliJ+5;

if(ia>，Z')ia-=26;

)

elseif(strifi]>=>a'&&stri[i]<=,L)

{ia=stri[i]+5;

if(ia>>z')ia-=26;

I

elseia=stri[i];

strp[i++]=ia;

)

strp[i]='\0';

rcturn(strp);

)

niain()

{chars[50];

gets(s);

printf("%s\n",jiami(s));

I

2.統(tǒng)計文本單詞的個數(shù)

輸入一行字符，統(tǒng)計其中有多少個單詞，單詞之間用格分隔開。

算法思路：

(1)從文本(字符串)的左邊開始，取出一個字符；設(shè)邏輯量word表示所取字符是否是單詞內(nèi)的字

符，初值設(shè)為0

(2)若所取字符不是“空格”，“逗號”，“分號”或“感嘆號”等單詞的分隔符，再判斷word是否為

I,若word不為1則表是新單詞的開始,讓單詞數(shù)num=num-1,讓word=1;

(3)若所取字符是“空格”，“逗號”，