C语言常用算法总结(2011.12)

1C语言常用算法归纳编程题考查学生对一种C语言常用算法的设计能力，以下对二级C语言考试中常用算法进行分类解析。1．计数、求和、求阶乘等算法。这类问题使用循环实现，需注意根据问题确定循环变量的初值、终值及结束条件，以及用于表示计数、和、阶乘的变量的初值。程序段一：用随机函数产生100个[0,99]范围内的随机整数，统计个位上的数字分别为1,2,3,4,5,6,7,8,9,0的数的个数并打印出来。本题使用数组来处理，用数组a[100]存放产生的100个随机整数，数组x[11]存放个位上的数字分别为1,2,3,4,5,6,7,8,9,0的数的个数。即个位是1的个数存放在x[1]中，个位是2的个数存放在x[2]中……个位是0的个数存放在x[10]中。#includestdio.hvoidmain（）｛inta[101],x[11],i,p；for(i=0;i11;i++)x[i]=0；for(i=1;i=100;i++)｛a[i]=rand()%100；printf（%4d，a[i］）；if（i%10==0）printf（\n）；｝for(i=1;i=100;i++)｛p=a[i]%10；if（p==0）p=10；x[p]=x[p]+1；｝for(i=l;i=10;i++）{p=i;if（i==10）p=0；printf（%d,%d\n,p,x[i]）；｝printf（\n）；｝2．求两个整数的最大公约数、最小公倍数算法。求最大公约数的算法思想：（1）对于已知两数m,n,使得mn；（2）除以n得余数r；（3）若r=0，则n为求得的最大公约数，算法结束，否则执行(4)；（4）m←n，n←r，再重复执行（2）。2求最小公倍数的算法思想：最小公倍数=两个整数之积/最大公约数。例如，求m=14,n=6的最大公约数。#includestdio.hvoidmain（）｛intnm,r,n,m,t；printf（pleaseinputtwonumbers:\n”）；scanf（％d,％d,&m,＆n）；nm=n*m；if（mn）｛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)；｝3.判断素数算法。只能被1或本身整除的数称为素数，其基本思想是：把m作为被除数，将2～m-1作为除数，如果都除不尽，m就是素数，否则就不是。#includestdio.hvoidmain（）｛intm,i；printf（PleaseInputanumber:\n）；scanf（%d,&m）;for（i=2;im;i++）if(m%i==0）break;if（i=m）printf（该数是素数）；elseprintf（该数不是素数）；}将其写成一个函数，若为素数返回1，不是则返回0。intprime(m)｛inti；for(i=2;im;i++)if(m%i==0）return0；return1；｝4．排序算法。程序段一：选择法排序（升序）3基本思想：（1)对有n个数的序列（存放在数组a[n]中），从中选出最小的数，与第1个数交换位置；(2）除第1个数外，其余n-1个数中选最小的数，与第2个数交换位置；（3）依次类推，选择了n-1次后，这个数列已按升序排列。#includestdio.hvoidmain（）｛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;j10;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]）；}}程序段二：冒泡法排序（升序）基本思想：将相邻两个数比较，小的调到前头。(1)有n个数（存放在数组a[n]中），第一趟将每相邻两个数比较，小的调到前头，经n-1次两两相邻比较后，最大的数己“沉底”，放在最后一个位置，小数上升“浮起”；(2）第二趟对余下的n-1个数（最大的数己“沉底”）按上法比较，经n-2次两两相邻比较后得次大的数；(3)依次类推，n个数共进行n-1趟比较，在第j趟中要进行n-j次两两比较。#includestdio.hvoidmain()｛inta[10]；inti,j,t；printf(Input10numbers＼n）；for(i=0;i10;i++)scanf(%d,&a[i])；printf(＼n)；for(j=0;j9;j++)for(i=0;i9-j;i++)if(a[i]a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t；}printf(thesortednumbers\n)；4for(i=0;i＜10;i++)printf(%d\n,a[i])；}程序段三：合并法排序（将两个有序数组A,B合并成另一个有序的数组C，升序）。基本思想：（1)先在A,B数组中各取第一个元素进行比较，将小的元素放入C数组；(2）取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较，重复上述比较过程，直到某个数组被先排完；（3)将另一个数组剩余元素插入C数组，合并排序完成。#includestdio.hvoidmain（）｛inta[10］,b[10],c[20],i,ia,ib,ic；printf(Pleaseinputthefirstarray:\n);for（i=0;i10;i++）scanf（%d,&a［i］）；for（i=0;i＜10;i++）scanf（%d，&b[i］）；printf（\n）；ia=0；ib=0；ic=0；while（ia10&&ib10）｛if（a[ia]b[ib]）{c[ic]=a[ia]；ia++;｝else｛c[ic]=b[ib]；ib++；｝ic++；}while（ia=9)｛c[is]=a[is]：ia++；ic++；}while（ib=9)｛c[ic]=b[ib];ib++;ic++;｝for（i=0;i20;i++）printf(%d\n,c[i]）;｝程序段四：插入法排序（把一个数插到有序数列中，插入后数列仍然有序）。基本思想：n个有序数（从小到大）存放在数组a[1]～a[n]中，要插入的数为x。首先确定x插在数组中的位置p。5#defineN10voidinsert（inta[]，intx）｛intp,i;p=0；while（xa[p]＆&pN）p++；for（i=N;ip;i--）a[i]=a[i-1]；a[p]=x；｝voidmain（）｛inta[N+1]=｛1,3,4,7,8,11,13,18,56,78｝，x，i；for（i=0;iN;i++）printf（%d,,a［i］）；printf（\nInputx：）；scanf（%d,&x）；insert（a,x）；for(i=0;i=N;i++)printf（％d,,a[i]）；printf（＼n）；｝}5.查找算法。程序段一：顺序查找。基本思想：一列数放在数组a[1]-a恤］中，待查找的数放在x中，把x与a数组中的元素从头到尾一一进行比较查找。用变量p表示a数组元素下标，p初值为1，使x与a[p]比较，如果x不等于a[p]，则使p=p+1，不断重复这个过程；一旦x等于a[p]则退出循环。另外，如果P大于数组长度，循环也应该停止。voidmain()｛inta[10],p,x,i;printf（Pleaseinputthearray\n）;for（i=0;i10;i++）scanf（%d,&a[i]）;printf（Pleaseinputthenumberyouwantfind:\n）；scanf（%d,＆x）;printf（\n）;p=0;while（x!=a[p]&&p10）p++;if(p=10)printf(thenumberisnotfound！\n);else6printf(thenumberisfoundtheno%d！＼n,p);｝程序段二：折半查找法（只能对有序数列进行查找）。基本思想：设n个有序数（从小到大）存放在数组a[1]-a[n]中，要查找的数为x.用变量bot,top,mid分别表示查找数据范围的底部（数组下界）、顶部（数组上界）和中间，mid=（top+bot）/2。折半查找的算法如下：（1)x=a[mid]，则已找到退出循环，否则进行下面的判断；(2）xa[mid]，x必定落在bot和mid-1的范围之内，即top=mid-1；(3）xa[mid]，x必定落在mid+1和top的范围之内，即bot=mid+l；(4)在确定了新的查找范围后，重复进行以上比较，直到找到或者bot=top。voidmain()｛inta[10],mid,bot,top,x,i,find；printf（pleaseinputthearray:\n）；for（i=O;i10;i++）scanf（%d,&a[i]）；printf（pleaseinputthenumberyouwantfind：\n）；scanf（％d，&x）；printf（\n）；bot＝0;top＝9;find=0;while(bottop&&find==0)｛mid=(top+bot)/2；if（x==a[mid］）｛find=1；break；｝elseif（xa[mid]）top=mid-1；elsebot=mid+l；}if（find==1）prinf(thenumberisfoundtheno％d！\n，mid)；elseprintf（thenumberisnotfound！\n）；｝6.矩阵（二维数组）运算算法。矩阵包括加、减、乘、转置等运算。程序段一：矩阵转置。有二维数组a[5,5]，要对它实现转置，可用下面两种方式实现：#defineN3voidchl(inta[N][N］)／*方式一*／7｛inti,j,t；for（i=0;iN;i++）for（j=i＋1;jN;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;iN;i++）for（j=0;ji;j++）{t=a[i][j];a[i][j]=a[j][i];a[j][i]=t;｝｝main（）｛inta[N][N]=｛｛1,2,3｝,{4,5,6},{7,8,9｝},i,j;chl(a）；／*或ch2（a）；*／for(i=0;iN;i++){for(j=0;jN;j++)printf（％4d，a[i][j]）；printf（\n）；｝｝程序段二：求二维数组中最小元素及其所在的行和列。以二维数组a[3][4]为例，变量max中存放最大值，row,column分别存放最大值列号。#defineN4#defineM3voidmin(inta[M][N］）{intmin,row,column,I,j;min=a[0][0]；row=0；column=0；for（i=0;iM;i++）for（j=0;jN;j++）if（a[i][j]min）｛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）;｝87.迭代算法。基本思想：对于一个问题的求解x，可由给定的一个初值x0，根据某一迭代公式得到一个新的值x1，这个新值x1比初值x0更接近要求的值x；再以新值作为初值，即x1→x0,重新按