二级C期末考试重点算法

二级C语言算法,刈必(201206).变量交换voidswap1(int*x,int*y){inttemp;temp=*x;*x=*y;*y=temp;)voidswap2(int*x,int*y){int*temp;*temp=*x;*x=*y;*y=*temp;)voidswap3(intx,inty){inttemp;temp=x;x=y;y=temp;).累加用C语言实现1+2+3+4+5+„+n的累加。【方法1】while循环实现intadd(intn),{inti,sum;sum=0;i=1;while(i<=n){sum=sum+i;i=i+1;}returnsum;main(){ints,n;printf("\nInputn:\n");scanf("%d”,n);s=add(n);/*函数调用*/printf("1+2+...+%d=%d\n”,n,s);)【方法2】for循环实现(main函数同上)intadd(intn){inti,sum=0;for(i=1;i<=n;i++)sum=sum+i;returnsum;)do-while循环也可以实现累加，请读者自己完成。.累乘用C语言求n的阶乘：n!=1x2x3x4x…xn(n，1)intproduct(intn){inti,p=1;for(i=2;i<=n;i++)p=p*i;returnp;)如果n的值比较大，函数返回值和存放乘积的变量p应定义为long或者double型。.排序(主函数参考教材181-182页)(1)冒泡排序(主函数main参考教材181-182页)voidBubbleSort(inta口，intn){inti,j,tmp;for(i=0;i<n-1;i++)/*排序趟次*/{for(j=0;j<n-1-i;j++)/*从前往后比*/if(a[j]>a[j+1])/*从小到大，升序*/{tmp=a[j];a[j]=a[j+1];a[j+1]=tmp;}/交换a[j]与a[j+1]，大数后移*/))(2)选择排序voidSelectSort(inta口，intn){inti,j,min,tmp;for(i=0;i<n-1;i++){min=i;/*假设第一个数最小，记录其下标*/for(j=i+1;j<n;j++)if(a[j]<a[min])min=j;/*找最小的数，将最小数的下标记录下来*/if(i!=min){tmp=a[i];a[i]=a[min];a[min]=tmp;}/*将最小的数与第一个数进行交换*/))(3)插入排序voidInsertSort(inta口，intn){inti,j,tmp;for(i=1;i<n;i++){tmp=a[i];/*空出a[i]单元*/for(j=i-1;j>=0&&a[j]>tmp;j--)a[j+1]=a[j];/*大于tmp的数向后移位*/a[j+1]=tmp;/*tmp归位*/)).归并(合并)将两个有序数组A、B合并成另一个有序的数组C(升序或降序)。升序合并步骤如下：①先在A、B数组中各取第一个元素进行比较，将小的元素放入C中。②取小的元素所在数组的下一个元素与另一个数组中上次比较后较大的元素进行比较。③重复上述比较过程，直到某个数组被先排完。④将另一个数组剩余元素抄入C中，合并排序完成。voidmerge(inta口，intm,intb[n],intn,intc口){intia=0,ib=0,ic=0;while(ia<m&&ib<n){if(a[ia]<b[ib])/*小的元素放入C中*/{c[ic]=a[ia];ia++;}else{c[ic]=b[ib];ib++;}ic++;)while(ia<m){c[ic]=a[ia];ia++;ic++;}/*a中剩余元素抄入c中*/while(ib<n){c[ic]=b[ib];ib++;ic++;}/*b中剩余元素抄入c中*/)6.查找(1)线性法查找线性法查找也叫顺序查找，对于没有排序的数组，只能采用线性法查找。将x与数组中的各个元素从头到尾进行比较，找到后返回数组下标，若找不到，返回。#defineN10intfind(inta[N],intkey){inti;for(i=0;i<N;i++)if(a[i]==key){return(i);break;}/*返回数组元素下标*/if(i==N)return(-1);)如果对一个升序数组进行线性法查找，循环结束条件改为“i<N&&a[i]<=key"，返回-1的条件为(i==N||a[i]>key)。(2)折半法查找(二分法查找)#defineN10intfind(inta[N],intkey){intm,p,q;P=0;q=N-1;/*p为第1个元素的下标，q为最后一个元素的下标*/while(p<=q){m=(p+q)/2;/*m为中间元素的下标*/if(a[m]==key){return(m);break;}elseif(key<a[m])q=m-1;elsep=m+1;}if(p>q)return(-1);}7.级数计算(递推法)递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。简单地说，就是后一项的值利用前面已求得的项的值得到，典型的递推算法如Fibonacci数列(斐波那契数列)，后一项为前两项的和。基本操作中的累加与累乘都可以看作递推法。递推公式包括两部分：开始项的值，以及从前面一、两项得到下一项的计算方法。用递推式比通项公式算得要快，因为计算每一项都充分利用了前一项的计算结果。例如，有一分数序列：2,3,5,8,13,21,…求出这个数列的前20项之和。(见教材)1235813.求最大、最小值(1)查找一维数组a[]中的最大值，n为数组的大小intfunmax(inta口，intn){inti,max=a[0];for(i=1;i<n;i++)if(max>a[i])max=a[i];returnmax;}(2)查找二维数组a中的最小值有一个3X4的矩阵，求所有元素的最小值及该元素的行号列号。因为函数只能返回一个值，要想得到最小元素的行号和列号，需要用指针作函数的参数。intfunmin(inta[][4],int*min_i,int*min_j){inti,j,min;min=a[0][0];for(i=0;i<3;i++)for(j=0;j<4;j++)if(a[i][j]<min){min=a[i][j];*min_i=i;*min_j=j;}returnmin;)main(){inti,j,min,min_i,min_j,a[3][4]={{3,6,9,12},{2,8,4,6},{5,7,9,10}};min=funmin(a,&min_i,&min_j);printf("\nmin=%d,min_i=%d,mim_j=%d\n”,min,min_i,min_j);)运行结果为：min=2,min_i=1,mim_j=0二维数组作函数的参数，第一维的长度可以缺省，第二维的长度不能缺省。.求和及平均值求数组的平均值，先用循环将数组的所有元素相加，最后返回所得的和除以数组元素的个数。floataverage(inta口，intn){inti;floatavg;avg=0;for(i=0;i<n;i++)avg=avg+a[i];/*若avg的初值为a[0],则i从1开始*/returnavg/n;/*若求数组的和，则返回avg，最好将avg变量用sum表示*/)若所求的数组的平均值不是从第一个元素开始的，不管从哪个元素开始，只要将开始元素的地址作为实际参数即可。例如，数组a共有20个元素，求最后5个元素的平均值的调用方式为：average(&a[151,5);最后5个元素的第一个元素为a[15]。.计数求满足要求的数的个数。一般在循环中对每一个元素都用if语句进行判断，满足条件时，计数的变量增1。例如，对数组中的n个学生成绩，求不及格人数的个数。intcount(inta口，intn){intc=0,i;for(i=0;i<n;i++)if(a[i]<60)c++;returnc;).数组元素逆序voidinv(inta口，intn){inti,j,t;for(i=0,j=n-1;i<j;i++,j--){t=a[i];a[i]=a[j];a[j]=t;})教材237页也可，或者238页用指针。.在数组中插入一个数、删除一个元素、数组元素移位(1)在数组的指定位置插入一个数如果在a[i]后插入一个x,从最后一个元素开始，将a[i+1]以后的元素往后移，空出位置后将x放在a[i+1]位置处。程序段如下：for(j=N-1;j>i;j--)a[j+1]=a[j];/*移位*/a[i+1]=x;/*插入x*/(2)在已排序的数组中插入一个数有一个已经排好序的数组，现有一个数x，要求按原来的规律将它插入数组中。首先判断此数是否大于最后一个数，然后再考虑插入中间的情况，找插入点，先将插入点之后的数依次后移一个位置。#defineN10voidinsert(inta[N],intnum){inti,j;if(num>a[N-2])a[N-1]=num;/*插在最后*/elsefor(i=0;i<N-1;i++)if(a[i]>num)/*找插入点，插在a[i]位置*/{for(j=N-2;j>=i;j--)a[j+1]=a[j];/*将a[i]以后的元素从最后一个元素开始后移*/a[i]=num;/*将num放在a[i]处*/break;))(3)删除数组中的一个元素a[i]删除数组中的元素a[i]，就是将a[i]以后的元素往前移一个位置。voiddel(inta口，intn,inti){intj;for(j=i;j<n-1;j++)a[j]=a[j+1];)(4)数组元素移位将数组中的一个元素a[i]移动到指定的位置上。例如，将一维数组下标为i的元素移到第j的位置。实际上先将该元素删除，然后再将其插到指定位置，元素在删除前先存放在临时变量中。voidmove(inta口，intn,inti,intj){intk,t;t=a[i];for(k=i;k<n-1;k++)a[k]=a[k+1];/*删除，a[i]以后的元素往前移一个位置*/for(k=n-1;k>=j;k--)a[k+1]=a[k];/*a[j]后的元素都要往后移位*/a[j]=t;/*插入*/)上面函数中的两个for可以合并为一个for，就是将a[i]与a[j]之间的元素往前移一位：for(k=i;k<j;k++)a[k]=a[k+1];若需要移动多个元素，则定义一个数组，用来临时存放需移动的元素，移动时在前面加上循环。例如，移动字符串中的内容。移动的规则如下：把第1到第m个字符平移到字符串的最后，把第m+1到最后的字符串移到字符串的前部。若字符串中原有的内容为：ABCDEFGHIJK，m的值为3，则移动后，字符串中的内容应该是DEFGHIJKABCovoidfun(chara[],intm){chart[80];inti,j,n;n=strlen(a);

for(i=0;i<m;i++)t[i]=a[i];/*移走*/for(i=m,j=0;i<n;i++,j++)a[j]=a[i];/*移位*/for(i=0;i<m;i++)a[n-m+i]=t[i];/*移入*/)main(){chara[80]="ABCDEFGHIJK”;intm=3;fun(a,m);printf("%s”,a);).素数问题#include<math.h>intprime(intm){inti,k;k=sqrt(m);for(i=2;i<=k;i++)if(m%i==0)return0;return1;)#include<math.h>intprime(intm){inti,k;k=sqrt(m);for(i=2;i<=k;i++)if(m%i==0)return0;return1;)/*用sqrt函数必须包含数学库函数math.h*//*k是不大于m平方根的最大整数*//*不是素数，返回0*//*素数返回1*/(2)把m〜n范围内的素数依次存入数组a中，返回素数个数#include<math.h>intprime(inta[N],intm,intn){inti,k,j;j=0;/*j为数组a的下标，最终结果为素数的个数*/for(i=m;i<=n;i++){for(k=2;k<=sqrt(i);k++)/*判断i是否是素数*/if(i%k==0)break;/*i不是素数，内循环结束*/if(k>sqrt(i))a[j++]=i;/*i是素数，存入数组a,下标增1*/)returnj;/*返回素数个数*/).求最大公约数和最小公倍数(1)求最大公约数(欧几里得算法)intgcd(intm,intn)(1)求最大公约数(欧几里得算法)intgcd(intm,intn){intt,r;if(m<n){t=m;m=n;n=t;}while(n){r=m%n;m=n;n=r;)returnm;)/*若m<n,则交换两数。可以缺省*//*求余*//*窜位，准备下次求余*//*返回最大公约数*/(2)求最小公倍数(两数之积除以最大公约数所得的值即为最小公倍数)intlcd(intm,intn){intt,r,p;p=m*n;/*保留两数乘积*/while(n)/*求最大公约数*/{r=m%n;m=n;n=r;}returnp/m;/*返回最小公倍数*/)如果在同一个程序中，可以直接调用最大公约数的函数：returnm*n/gcd(m,n);.整数拆分与拼接(1)拆整数求一个整数的位数及将各位数字存放在数组中，返回整数的位数。intcdigit(longn,inta[]){inti=0,k;while(n){a[i++]=n%10;/*将余数放入数组a中，数组下标增1*/n=n/10;/*取整，去掉余数后的数*/)return(i);)下面的函数是求整数n的各位数字之和。intsum(intn){ints=0;while(n){s=s+n%10;n=n/10;}return(s);)若求各位数字之积，只要将s的初值“0”改为“1”，“加”改成“乘”即可。(2)拼整数①将键盘输入的正整数数字组成一个整数，先输入的数字为最高位。main(){longnum=0;intn;scanf("%d",&n);while(n>=0){num=num*10+n;scanf("%d",&n);)printf("%ld",num);)②将数组a中的数拼成整数。longpdigit(inta[],intn){longnum=0;inti;for(i=0;i<n;i++)num=num*10+a[i];return(num);)main(){inta[5]={3,2,7,6,7};printf("\nnum=%ld\n”,pdigit(a,5));).求反序数和回文数(1)求反序数将一个数的数字排列顺序完全颠倒过来，就变成另一个数，这个数就是该数的反序数，如123

的反序数为321。求反序数的方法是先将一个数从个位开始用取余数拆分开来，再将拆开的数字拼成整数。即将拆整数和拼整数两个函数结合起来即可，边拆边拼。longinte(longn){longnum=0;while(n){num=num*10+n%10;n=n/10;return(num);(2)求回文数一个数与它的反序数相等，这样的数称为回文数。如12321,6336等就是回文数。①判断m是否是回文数判断一个数是否是回文数，先求出它的反序数，再判断两者是否相等。longpalin(longm){longs=0,n;/*将m/*将m存入n中*//*求反序数*//*求反序数*/elsereturn(0);)②求指定范围内的回文数求指定范围内(ml〜m2之间)的回文数，保存到指定的数组中，返回回文数的个数。intpalin(longm1,longm2,longx口){longi,n,s;intk=0;intpalin(longm1,longm2,longx口){longi,n,s;intk=0;for(i=m1;i<=m2;i++){n=i;s=0;while(n){s=s*10+n%10;n=n/10;if(i==s){x[k]=i;k++;})returnk;)/*s是i的回文数*//*k为回文数个数，数组下标*//*求反序数*//*若是回文数，放入数组a中*//*返回回文数的个数*/函数调用时，数组a定义为长整型，输入输出格式为“％ld”，常量后面要加字母“l”，例如，求1000000〜200000之间的回文数的调用形式为：n=palin(100000l,120000l,a);其中，n为函数返回的回文数的个数。.因子、完全数、互满数对(1)求a的因子并存放在数组中因子是指能被a整除的数，包含1和该数本身，真因子包含1不包含本身。例如，6的因子为1,2,3,6,真因子为1,2,3。intfun(inta,intx口){inti,j=0;/*求/*求a的因子，若求真因子将i<=a改为i<a*//*i是a的因子，存入数组x中，下标增1*//*返回因子的个数*/if(a%i==0)x[j++]=i;returnj;(2)找指定范围内的完全数完全数是指一个正整数的所有真因子之和等于本身的数，真因子包含1但不包含本身，例如，6=1+2+3,28=1+2+4+7+14，所以6和28是完全数。intfun(inta[N],intm,intn){inti,j,s;intk=0;for(i=m;i<=n;i++){s=0;/*对指定范围内的每个数i都要求其因子之和s*/for(j=1;j<i;j++)if(i%j==0)s=s+j;if(i==s)a[k++]=i;/*是完全数，存入数组中*/)returnk;/*返回完全数的个数*/)(3)互满数对(亲密数对)互满数对是指两个数中，其中的一个数的真因子之和都等于另一个数。即a的真因子之和为b，b的真因子之和为a。例如，220与184，1184与1210就是互满数对。intfun(ints[][2],intm1,intm2)/*求m1〜m2的互满数对*/{ints1,s2,count,a,i,j;count=0;for(a=m1;a<=m2;a++){s1=1;s2=1;/*1也是真因子*/for(i=2;i<a;i++)if(a%i==0)s1=s1+i;/*a的真因子之和为s1*/for(j=2;j<s1;j++)if(s1%j==0)s2=s2+j;/*s1的真因子之和为s2*/if((s2==a)&&(a<s1))/*互为真因子之和，存入二维数组s中*/{s[count][0]=a;s[count][1]=s1;count++;))returncount;/*返回数对个数*/).求满足条件的数或数对求满足条件的数或数对经常采用穷举法。穷举法的基本思想是：一一列举各种可能的情况，并判断哪一种是符合要求的解。这是一种在“没有其他办法情况下的方法”是一种最“笨”的方法,然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。穷举法一般包含两类，一是找出符合特定条件的一组数(一组解)，二是验证定理或猜想。(1)同构数同构数是其值等于其右边数字平方数的整数。如25,36都是同构数(25=52,36=62)。下面的程序是求1〜99的所有同构数。main(){inti,k;for(i=1;i<100;i++){k=i%10;/*求未位数*/

/*输出满足要求的数*//*输出满足要求的数*/))(2)Armstrong数(水仙花数)一个n位的正整数，其各位数的n次方之和等于这个数，称这个数为Armstrong数。例如，153=13+53+33。1634=14+64+34+44。下面的程序求所有三3位和4位的Armstrong数。main(){inti,j,k,m,t,s,a[5],b[5];for(m=100;m<10000;m++)/*k为临时变量，j/*k为临时变量，j为位数*//*a中存放各位数字*//*几位数就循环多少次*//*b中存放各位数字之乘积*//*s为各位数字乘积之和*//*输出满足条件的数*/while(k){a[j++]=k%10;k=k/10;}for(i=0;i<j;i++){b[i]=1;for(t=0;t<j;t++)b[i]=b[i]*a[i];)for(s=0,t=0;t<j;t++)s=s+b[t];if(s==m)printf("%d”,m);(3)求满足条件的数或数对【例题1】找出所有满足下列条件的正整数对a,b：(1)a+b=99;(2)a<b;(3)a与b的最小公倍数是3的倍数。编写函数intfind(intm,intn),其功能是找出两个正整数的最小公倍数并返回。编写main函数，找出所有满足条件的正整数对。【分析】正整数对要求满足a+b=99,表示a和b都在1〜98的范围内，循环变量的变化从1〜98就可以了。第二个条件是a<b,只要让b从a开始就可以。第三个条件，先写一个求最小公倍数的函数，再用if语句调用并判断最小公倍数是否是3的倍数。#include<stdio.h>main()#include<stdio.h>main(){inta,b;for(a=1;a<99;a++)for(b=a;b<99;b++)if(a+b==99)if(find(a,b)%3==0)printf("%d+%d=99,/*b从a开始，确保a<b*//*第一个条件a+b=99*//*a,b的最小公倍数是3的倍数*/mingps:%d\n”,a,b,find(a,b));)/*求两个整数的最小公倍数*//*求两个整数的最小公倍数*/{intp,r;p=m*n;while(n){r=m%n;m=n;n=r;}return(p/m);).字符串问题|字符串最大的特点是有一个字符串结束标志'\0'，在进行字符串的有关操作时，判断一个字符串是否结束就是根据该标志，操作完后记得在字符串最后加上结束标志。(1)复制字符串voidstrcopy(charfrom口，charto口)/*将from中的字符复制到to中*/{inti;for(i=0;to[i]!='\0';i++)to[i]=from[i];to[i]='\0';/*字符串末尾添加结束标志*/)若用指针实现：voidstrcopy(char*from,char*to){for(;*from!='\0';from++,to++)*to=*from;*to='\0';)(2)连接两个字符串voidstrconnect(chars1口，chars2口)/*将s2字符串连接在s1的后面*/{inti,j;for(i=0;s1[i];i++);/球第一个字符串的长度*/for(j=0;s2[j];j++)s1[i++]=s2[j];/*将第二个字符串连接到第一个字符串后面*/s1[i]='\0';/*字符串末尾添加结束标志*/)(3)比较两个字符串intstrcompare(char*s1,char*s2){while((*s1)&&(*s2)&&(*s1==*s2))/喏是相同的字符，指针下移*/{s1++;s2++;}return(*s1-*s2);/*返回第一个不同字符的ASCII码值的差*/)(4)求字符串长度intlength(char*s){intn=0;while(*s){n++;s++;}return(n);)voidmain(){charstr[20];scanf("%s”,str);printf("Thelengthofstringis%d.\n”,length(str));)(5)回文字符串判断一个给定字符串是否是回文，是函数返回1，否则返回0。例如，字符串“aba”、“agbga”是回文字符串，字符串abcdefg不是回文字符串。intstjug(char*s){char*f,*t;/*f指向字符串头，t指向字符串尾*/for(f=s,t=s+strlen(s)-1;f<t;f++,t--)if(*f!=*t)return0;/*比较f指向的字符与t指向的字符，不等返回0*/return1;

）（6）字符串排序字符串排序的算法与数的排序是相同的，不同的是字符串不能直接赋值及比较大小，而要用字符串复制函数和字符串比较函数。voidBubbleSort(chara[][10],intn)/*字符串冒泡排序*/{inti,j;chartmp[10];for(i=0;i<n-1;i++)for(j=0;j<n-1-i;j++)if(strcmp(a[j],a[j+1])>0){strcpy(tmp,a[j1);strcpy(a[j],a[j+1]);strcpy(a[j+1],tmp);}.数字字符串与整数的相互转换（1）数字字符串转换成整数数字字符在计算机中是以ASCII码的形式存放的，整数是以补码的形式存放的。将数字字符转换成数字，要减去字符'0'的ASCII码值。然后再将一个个数字拼成整数。longstr_to_int(chara口){inti;longs=0;/*字符转换成数字并拼成整数*//*字符转换成数字并拼成整数*/return(s);)main(){chara[10];gets(a);printf("%ld”,str_to_int(a));)（2）整数转换成字符串将整数转换成数字字符串，先将整数分离成一个个数字，再将数字加上字符0'的ASCII值转换成数字字符。最后在末尾加上字符串结束标志'\0'。因为最先得到的最低位为数组的第一个元素，所以还要将字符串逆序，才能得到与整数顺序相同的数字字符串。voidint_to_str(longn,chars口){inti=0,k;chart;while(n)/*将整数分离并转换成字符放入数组s/*将整数分离并转换成字符放入数组s中*//*加上字符串结束标志'\0'*//*k为字符串实际长度*/n=n/10;)s[i]='\0';k=i;for(i=0;i<k/2;i++){t=s[i];s[i]=s[k-i-1];s[k-i-1]=t;}/*字符串逆序*/)main(){longn;inti=0;chars[10];scanf("%ld",&n);

int_to_str(n,s);puts(s);若考虑有符号，则在循环前加上if语句判断，并从下一个字符开始转换。.数制转换问题(1)r进制转换为十进制将r进制字符串转换为十进制数，与将十进制字符串转换成整数类似，先减去字符'0'的ASCII码值，然后再将一个个数拼成整数。十六进制因为有字符A〜F或a〜f而有所不同，要将这些字符转换成对应的10〜15,转换方法为减去字符A的ASCII码值再加上10。以下函数是将r进制字符串转换成十进制整数。intdectr(chara口，intr){intn=0,i=0;while(a[i]){if(a[i]>='A'&&a[i]<='F')n=n*r+a[i]-'A'+10;/*将字母转换成对应的数并拼成整数*/elseif(a[i]>='a'&&a[i]<='f')n=n*r+a[i]-'a'+10;elsen=n*r+a[i]-'0';/*数字字符转换成