C语言常用算法程序汇总.docx
《C语言常用算法程序汇总.docx》由会员分享，可在线阅读，更多相关《C语言常用算法程序汇总.docx（21页珍藏版）》请在冰点文库上搜索。
C语言常用算法程序汇总
C程序设计的常用算法
算法（Algorithm）：
计算机解题的基本思想方法和步骤。
算法的描述：
是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。
通常使用自然语言、结构化流程图、伪代码等来描述算法。
一、简单数值类算法
此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。
1、求阶乘：
n!
=1*2*384…..*n;n!
=n*（n-1）!
=
下列程序用于求n的阶乘.在累乘之前,一定要将用于存放乘积的变量的值初始化为1.
longfunc（intn）
{
inti;
longt=1;
for（i=2;i<=n;i++）t*=i;
returnt;
}
printf（"\n"）;
}
main（）
{intn;
scanf（"%d",&n）;
printf（"n!
=%ld\n",fac（n））;
}
2、整数拆分问题：
把一个整数各个位上的数字存到数组中#defineN4/*N代表整数位数*/viodsplit（intn,inta[]）
/*1478:
a[3]=8,a[2]=7,a[1]=4…*/
{inti;
for（i=N-1;i!
=0;i--）
{a[i]=n%10;
n=n/10;
}
}
main（）
{inti,m=1478,b[N-1];split（m,b）;for（i=0;i<4;i++）printf（“%5d”,b[i]）;}
3、求整数的因子之和12=1*2*3*4longfactor（intn）
{inti;
longsum=0;
for（i=1;i<=n;i++）
if（n%i==0）
sum+=i;
returnsum;
}
注意：
因子包括1和自身。
二、求两个整数的最大公约数、最小公倍数分析：
求最大公约数的算法为辗转相除法。
（最小公倍数=两个整数之积/最大公约数）
求最大公约数的算法步骤：
⑴对于已知两数m,n,使得m>n;
（2）m除以n得余数r；r=m%n;
（3）若r==0，则n为求得的最大公约数，算法结束；否则执行（4）;
（4）m—n,n—r,再重复执行
（2）。
例如:
求m=14,n=6的最大公约数.mnr
14%6=2
6%2=0输出2
voidmain（）
{intnm,r,n,m,t;
printf（"pleaseinputtwonumbers:
\n"）;
scanf（"%d,%d",&m,&n）;
nm=n*m;
if（m{t=n;n=m;m=t;}
r=m%n;
while（r!
=0）
{m=n;n=r;r=m%n;}
printf（"最大公约数:
%d\n",n）;
printf（"最小公倍数:
%d\n",nm/n）;
}
将其写成一函数,返回最大公约数。
intgcd（intm,intn）
{intt,r;
if（mr=m%n;
while（r!
=0）
{m=n;n=r;r=m%n;}
returnn;
}
intgcd（intm,intn）
{intt,r;
if（mdo
{r=m%n;
m=n;n=r;}while（n!
=0）
returnm;
}如果求最小公倍数，其函数形式稍作调整：
intgcd（intm,intn）
{inta=m,b=n;
intt,r;
if（mwhile（r!
=0）
{m=n;n=r;r=m%n;}return（a*b）/n;
}
三、判断素数
只能被1和本身整除的正整数称为素数。
基本思想：
在判断数m是否为素数时，首先把m作为被除数，将2—sqrt（m）的所有数字依次作为除数，去除m,只要
有一个数能将m整除，则m不是素数；否则，如果都除不尽，则m就是素数。
（可用以下程序段实现）
#include
voidmain（）
{intm,i,k;
printf（"pleaseinputanumber:
\n"）;
scanf（"%d",&m）;
k=sqrt（m）;/*使用此函数一定要加头文件
#include*/
for（i=2;iif（m%i==0）break;
if（i>=k）
printf（"该数是素数"）;
else
printf（"该数不是素数"）;
}
将其写成一函数,若为素数返回1，不是则返回0
intprime（intm）
{inti,k;
k=sqrt（m）;/*使用此函数一定要加头文件#inelude
*/
for（i=2;iif（m%i==O）return0;
return1;
}
四、求最值
例如求最小值算法思想：
定义变量min用于存放当前所有找到的最小数，a为已知数组。
算法步骤如下：
1）在min中存放第1个数，比较从数组中的第二个元素开始。
2）数组a中每个元素依次与min中的数组相比，小者放入min中。
3）比较完数组的最后一个元素，算法结束。
Min中数为所求。
求最大值：
max=a[0];
for（i=0;iif（a[i]>max）max=a[i];
程序如下：
intminvalue（inta[],intn）
{inti,min;
min=a[0];
for（i=1;iif（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（“%3d”,a[i]）;
printf（“\n”）;min=minvalue（a,10）;
printf（“theresultis:
%d”,min）;
}
五、排序问题
1•选择法排序（升序）基本思想：
1）对有n个数的序列（存放在数组a（n）中），从中选出最小的数，与第1个数交换位置；
2）除第1个数外，其余n-1个数中选最小的数，与第2个数交换位置；
程序代码如下：
voidmain（）
{inti,j,imin,s,a[10];
printf（"\ninput10numbers:
\n"）;for（i=0;i<10;i++）
scanf（"%d",&a[i]）;for（i=0;i<9;i++）{imin=i;
for（j=i+1;j<10;j++）
if（a[imin]>a[j]）imin=j;
if（i!
=imin）
{s=a[i];a[i]=a[imin];a[imin]=s;}printf（"%d\n",a[i]）;
}
自定义函数形式
voidsort（inta[],intn）
{inti,j,imin,s;
for（i=0;i{imin=i;
for（j=i+1;jif（a[imin]>a[j]）imin=j;
if（i!
=imin）
{s=a[i];a[i]=a[imin];
a[imin]=s;}
}
}
3）依次类推，选择了n-1次后，这个数列已按升序排列。
}
2•冒泡法排序（升序）
16,17,19,14,23,34,8,33,45,56,
基本思想：
（将相邻两个数比较，小的调到前头）
1）有n个数（存放在数组a（n）中），第一趟将每相邻两个数比较，小的调到前头，经n-1次两两相邻比较后，最大的数已“沉底”，放在最后一个位置，小数上升“浮起”；
3）依次类推，n个数共进行行n-j次两两比较。
程序段如下
voidmain（）
{inta[10];
inti,j,t;
printf（"input10numbers\n"）;for（i=O;i<1O;i++）
scanf（"%d",&a[i]）;
printf（"\n"）;
for（j=0;jv=8;j++）for（i=0;i<9-j;i++）if（a[i]>a[i+1]）
n-1趟比较，在第j趟中要进
自定义函数形式：
voidsort（inta[],intn）
{inti,j,t;
for（j=0;j<=8;j++）
for（i=0;i<9-j;i++）
if（a[i]>a[i+1]）
{t=a[i];a[i]=a[i+1];a[i+1]=t;}
}
2）第二趟对余下的n-1个数（最大的数已“沉底”）按上法比较，经n-2次两两相邻比较后得次大的数；
{t=a[i];a[i]=a[i+1];a[i+1]=t;}
printf（"thesortednumbers:
\n"）;
for（i=0;i<10;i++）
，",a[i]）;
}
3．合并法排序（将两个有序数组A、B合并成另一个有序的数组C,升序）
a[10]:
1,3,5,6
b[10]:
2,4,7,9,10.23
c[20]:
1,2,3,4,5,6,7,9,10.23
基本思想：
1）先在A、B数组中各取第一个元素进行比较,将小的元素放入C数组；
2）取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较,重复上述比较过程,直到某个数组被先排完；
3）将另一个数组剩余元素抄入C数组,合并排序完成。
程序段如下：
voidmain（）
{inta[10],b[10],c[20],i,ia,ib,ic;
printf（"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=0;ib=0;ic=0;while（ia<10&&ib<10）{if（a[ia]}while（ia<=9）{c[ic]=a[ia];ia++;ic++;
}while（ib<=9）{c[ic]=b[ib];
ib++;ic++;
}for（i=0;i<20;i++）printf（"%d\n",c[i]）;
}
六、查找问题
1•①顺序查找法（在一列数中查找某数X）
思考：
将上面程序改写一查找函数Find,若找到则返回下标值，找不到返回-1
②基本思想：
一列数放在数组a[1]---a[n]中，待查找的关
键值为key，把key与a数组中的元素从头到尾一一进行比较查找，若相同，查找成功，若找不到，则查找失败。
（查找子
采用另外一种方法自定义函数，若找到
则返回下标值，找不到返回-1：
intseek（inta[],intn,intx）
{intp=0;
while（x!
=a[p]&&pp++;
if（p>=n）return-1;
elsereturnp;
}
过程如下。
index:
存放找到元素的下标。
）
voidmain（）
{inta[10],index,x,i;
printf（"pleaseinputthearray:
'n"）;for（i=0;i<10;i++）
scanf（"%d",&a[i]）;
printf（"pleaseinputthenumberyouwantfind:
\n"）;
scanf（"%d",&x）;
printf（"\n"）;index=-1;
for（i=0;i<10;i++）if（x==a[i]）
{index=i;break;
}
if（index==-1）
printf（"thenumberisnotfound!
\n"）;
else
printf（"thenumberisfoundtheno%d!
\n",index）;
}2．折半查找法（只能对有序数列进行查找）基本思想：
设n个有序数（从小到大）存放在数组a[1]a[n]
中，要查找的数为X。
用变量bot、top、mid分别表示查找数据范围的底部（数组下界）、顶部（数组的上界）和中间，mid=（top+bot）/2,折半查找的算法如下：
（1）x=a（mid），则已找到退出循环，否则进行下面的判断；
（2）X（3）x>a（mid），x必定落在mid+1和top的范围之内，即
bot=mid+1；
（4）在确定了新的查找范围后，重复进行以上比较，直到找到或者bot>=top。
将上面的算法写成如下程序：
voidmain（）
{
inta[10],mid,bot,top,x,i,find;
printf（"pleaseinputthearray:
\n"）;
for（i=0;i<10;i++）
scanf（"%d",&a[i]）;
printf（"pleaseinputthenumberyouwantfind:
\n"）;scanf（"%d",&x）;
printf（"\n"）;
bot=0;top=9;find=0;while（botif（x==a[mid]）{find=1;break;}
elseif（xelsebot=mid+1;
}
if（find==1）printf（"thenumberisfoundtheno%d!
\n",mid）;else
printf（"thenumberisnotfound!
\n"）;
}
七、插入法把一个数插到有序数列中，插入后数列仍然有序
基本思想：
n个有序数（从小到大）存放在数组a
（1）—a（n）中，要插入的数X。
首先确定x插在数组中的位置P;（可由以下语句实现）
#defineN10voidinsert（inta[],intx）
{intp,i;
p=0;
while（x>a[p]&&pp++;
for（i=N;i>p;i--）
a[i]=a[i-1];
a[p]=x;
}
main（）
{inta[N+1]={1,3,4,7,8,11,13,18,56,78},x,i;
for（i=0;i"）;
scanf（"%d",&x）;
insert（a,x）;
for（i=0;i<=N;i++）printf（"%d,",a[i]）;printf（"\n"）;
}
八、矩阵（二维数组）运算
（1）矩阵的加、减运算
C（i,j）=a（i,j）+b（i,j）加法
C（i,j）=a（i,j）-b（i,j）减法
（2）矩阵相乘
（矩阵A有M*L个元素，矩阵B有L*N个元素，则矩阵C=A*B有M*N个元素）。
矩阵C中任一元素（i=1,2,…,m;j=1,2,…,n）
#defineM2
#defineL4
#defineN3
voidmv（inta[M][L],intb[L][N],intc[M][N]）
{inti,j,k;
for（i=0;ifor（j=0;j{c[i][j]=0;
for（k=0;kc[i][j]+=a[i][k]*b[k][j];
}
}
main（）
{inta[M][L]={{1,2,3,4},{1,1,1,1}};
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{for（j=0;jprintf（"%4d",c[i][j]）;
printf（"\n"）;
}
}
（3）矩阵转置
算法思想：
指将矩阵中元素的行下标和列下标交换，形成的新矩阵就是原矩阵的转置矩阵。
在转置方阵时须注意，只用遍历方阵的上三角形（或下三角形），将其中的元素和其对应元素进行一次交换即可。
如果是遍历整个方阵，并将每个元素都和它对应元素交换，结果会发现方阵没有发生变化，原因是每个元素都做了两次交换，最终又换回到原来的位置上。
例:
有二维数组a（5,5）,要对它实现转置，可用下面两种方
式：
#defineN3
voidch1（inta[N][N]）/*只遍历方阵的上三角形*/
{inti,j,t;
for（i=0;ifor（j=i+1;j{t=a[i][j];a[i][j]=a[j][i];a[j][i]=t;
}
}
voidch2（inta[N][N]）/*只遍历方阵的下三角形*/{inti,j,t;
for（i=1;ia[i][j]=a[j][i];a[j][i]=t;
}
}main（）
{inta[N][N]={{1,2,3},{4,5,6},{7,8,9}},i,j;ch1（a）;/*或ch2（a）;*/for（i=0;i{for（j=0;j}
（4）求二维数组中最小元素及其所在的行和列基本思路同一维数组，可用下面程序段实现（以二维数组a[3][4]为例）：
‘变量minx中存放最小值，row,column存放最小值所在行列号
#defineN4
#defineM3
voidmin（inta[M][N]）
{intmin,row,column,i,j;
min=a[0][0];
row=0;
column=0;
for（i=0;ifor（j=0;j{min=a[i][j];
row=i;
column=j;
}
printf（"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,可由给定的一个初值
X0,根据某一迭代公式得到一个新的值x1,这个新值x1比初值X0更接近要求的值X；再以新值作为初值，即：
Xi—X0,重新按原来的方法求Xi,重复这一过和直到|x1-xO|<£（某一给定的精度）。
此时可将X1作为问题的解。
例：
用迭代法求某个数的平方根。
已知求平方根的迭代公式为：
#include
floatfsqrt（floata）
{floatX0,Xi;
Xi=a/2;
do{
X0=Xi;
Xi=0.5*（X0+a/X0）;
}while（fabs（Xi-X0）>0.0000i）;
return（Xi）;
}
main（）
{floata;
scanf（"%f",&a）;
printf（"genhao=%f\n",fsqrt（a））;
}
十、数制转换
将一个十进制整数m转换成-r（2—16）进制字符串。
方法：
将m不断除r取余数，直到商为零，以反序得到结果。
下面写出一转换函数，参数idee为十进制数，ibase为要转换成数的基（如二进制的基是2,八进制的基是8等），函数输出结果是字符串。
char*trdee（intidee,intibase）
{charstrdr[20],t
inti,idr,p=0;
while（idec!
=O）
{idr=idec%ibase;
if（idr>=10）
strdr[p++]=idr-10+65;
else
strdr[p++]=idr+48;
idec/=ibase;
for（i=0;ivp/2;i++）{t=strdr[i];strdr[i]=strdr[p-i-1];strdr[p-i-1]=t;
}strdr[p]='\0';
}
main（）
{intx,d;
scanf（"%d%d",&x,&d）;
printf（"%s\n",trdec（x,d））;
}
return（strdr）;
}
十一、字符串的一般处理
1．简单加密和解密
加密的思想是：
将每个字母C加（或减）一序数K，即用它后的第K个字母代替，变换式公式：
c=c+k
例如序数k为5,这时A-F,a-f,B-?
G-当加序
数后的字母超过Z或z则c=c+k-26
例如：
Youaregood—DtzfwjItti
解密为加密的逆过程
将每个字母C减（或加）一序数K，即c=c-k,
例如序数k为5,这时Z—U,z—u,丫—T…当加序数后的字母小于A或a则c=c-k+26
下段程序是加密处理：
#incIude
char*jiami（charstri[]）
{inti=0;
charstrp[50],ia;
whiIe（stri[i]!
='\0'）
{if（stri[i]>='A'&&stri[i]<='Z'）
{ia=stri[i]+5;
if（ia>'Z'）ia-=26;
}
elseif（stri[i]>='a'&&stri[i]<='z'）{ia=stri[i]+5;
if（ia>'z'
升级会员 