二级C期末考试重点算法讲解.doc

二级C语言算法（201206）1.变量交换void swap1(int *x, int *y) int temp; temp=*x; *x=*y; *y=temp;void swap2(int *x, int *y) int *temp; *temp=*x; *x=*y; *y=*temp;void swap3(int x, int y) int temp; temp=x; x=y; y=temp;2.累加用C语言实现1+2+3+4+5+n的累加。【方法1】while循环实现int add(int n) int i,sum; sum=0; i=1; while(i=n) sum=sum+i; i=i+1; return sum;main() int s,n; printf(nInput n:n); scanf(%d,n); s=add(n); /*函数调用*/ printf(1+2+.+%d=%dn,n,s);【方法2】for循环实现（main函数同上）int add(int n) int i,sum=0; for(i=1;i=n;i+) sum=sum+i; return sum;do-while循环也可以实现累加，请读者自己完成。3.累乘用C语言求n的阶乘：n! = 1234n (n1)int product (int n) int i,p=1; for(i=2;i=n;i+) p=p*i; return p; 如果n的值比较大，函数返回值和存放乘积的变量p应定义为long或者double型。4.排序 （主函数参考教材181-182页）（1）冒泡排序 （主函数main参考教材181-182页）void BubbleSort(int a,int n) int i,j, tmp; for(i=0;in-1;i+) /*排序趟次*/ for(j=0; jaj+1) /*从小到大，升序*/ tmp=aj; aj=aj+1; aj+1=tmp;/*交换aj与aj+1，大数后移*/ （2）选择排序 void SelectSort(int a,int n) int i,j,min,tmp; for(i=0; in-1; i+) min=i; /*假设第一个数最小，记录其下标*/ for(j=i+1; jn; j+) if(ajamin) min=j;/*找最小的数，将最小数的下标记录下来*/ if(i!=min) tmp=ai; ai=amin; amin=tmp; /*将最小的数与第一个数进行交换*/ （3）插入排序 void InsertSort(int a,int n) int i,j,tmp; for(i=1; i=0 & ajtmp; j-) aj+1=aj; /* 大于tmp的数向后移位 */ aj+1=tmp; /* tmp归位 */ 5.归并（合并）将两个有序数组A、B合并成另一个有序的数组C（升序或降序）。升序合并步骤如下： 先在A、B数组中各取第一个元素进行比较，将小的元素放入C中。 取小的元素所在数组的下一个元素与另一个数组中上次比较后较大的元素进行比较。 重复上述比较过程，直到某个数组被先排完。 将另一个数组剩余元素抄入C中，合并排序完成。void merge(int a,int m,int bn,int n,int c) int ia=0,ib=0,ic=0; while(iam & ibn) if (aiabib) /*小的元素放入C中*/ cic=aia;ia+; else cic=bib;ib+; ic+; while(iam) cic=aia;ia+;ic+; /*a中剩余元素抄入c中*/while(ibn) cic=bib;ib+;ic+; /*b中剩余元素抄入c中*/6.查找（1）线性法查找线性法查找也叫顺序查找，对于没有排序的数组，只能采用线性法查找。将x与数组中的各个元素从头到尾进行比较，找到后返回数组下标，若找不到，返回-1。#define N 10int find(int aN,int key) int i; for(i=0; iN; i+) if(ai=key) return (i); break; /*返回数组元素下标*/ if(i=N) return (-1); 如果对一个升序数组进行线性法查找，循环结束条件改为“iN & aikey)。（2）折半法查找（二分法查找）#define N 10int find(int aN,int key) int m,p,q; p=0;q=N-1; /*p为第1个元素的下标，q为最后一个元素的下标*/ while(p=q) m=(p+q)/2; /*m为中间元素的下标*/ if (am=key) return (m); break; else if(keyq) return (-1);7.级数计算（递推法）递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。简单地说，就是后一项的值利用前面已求得的项的值得到，典型的递推算法如Fibonacci数列（斐波那契数列），后一项为前两项的和。基本操作中的累加与累乘都可以看作递推法。递推公式包括两部分：开始项的值，以及从前面一、两项得到下一项的计算方法。用递推式比通项公式算得要快，因为计算每一项都充分利用了前一项的计算结果。例如，有一分数序列：求出这个数列的前20项之和。（见教材）8.求最大、最小值（1）查找一维数组a 中的最大值，n为数组的大小int funmax (int a, int n) int i,max=a0; for(i=1;iai) max=ai; return max; （2）查找二维数组a中的最小值有一个34的矩阵，求所有元素的最小值及该元素的行号列号。因为函数只能返回一个值，要想得到最小元素的行号和列号，需要用指针作函数的参数。int funmin(int a4, int *min_i,int *min_j) int i,j,min; min=a00; for(i=0;i3;i+) for(j=0;j4;j+) if(aijmin) min=aij; *min_i=i; *min_j=j; return min;main() int i,j,min,min_i,min_j,a34=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=%dn,min,min_i,min_j);运行结果为：min=2,min_i=1,mim_j=0二维数组作函数的参数，第一维的长度可以缺省，第二维的长度不能缺省。9.求和及平均值求数组的平均值，先用循环将数组的所有元素相加，最后返回所得的和除以数组元素的个数。float average(int a,int n) int i; float avg; avg=0; for(i=0;in;i+) avg=avg+ai; /*若avg的初值为a0,则i从1开始*/ return avg/n; /*若求数组的和，则返回avg，最好将avg变量用sum表示*/若所求的数组的平均值不是从第一个元素开始的，不管从哪个元素开始，只要将开始元素的地址作为实际参数即可。例如，数组a共有20个元素，求最后5个元素的平均值的调用方式为：average(&a15, 5);最后5个元素的第一个元素为a15。10.计数求满足要求的数的个数。一般在循环中对每一个元素都用if语句进行判断，满足条件时，计数的变量增1。例如，对数组中的n 个学生成绩，求不及格人数的个数。int count(int a,int n) int c=0,i; for(i=0;in;i+) if(ai60) c+; return c;11.数组元素逆序void inv(int a, int n) int i, j,t; for(i=0,j=n-1;ii; j-) aj+1=aj; /*移位*/ai+1=x; /* 插入x */（2）在已排序的数组中插入一个数有一个已经排好序的数组，现有一个数x，要求按原来的规律将它插入数组中。首先判断此数是否大于最后一个数，然后再考虑插入中间的情况，找插入点，先将插入点之后的数依次后移一个位置。#define N 10void insert(int aN,int num) int i,j; if (numaN-2) aN-1=num; /*插在最后*/ else for(i=0; inum) /*找插入点，插在ai位置*/ for(j=N-2; j=i;j-) aj+1=aj; /*将ai以后的元素从最后一个元素开始后移*/ ai=num; /*将num放在ai处*/ break; （3）删除数组中的一个元素ai 删除数组中的元素ai，就是将ai以后的元素往前移一个位置。void del (int a,int n,int i ) int j ; for(j=i; jn-1; j+) aj=aj+1;（4）数组元素移位将数组中的一个元素ai移动到指定的位置上。例如，将一维数组下标为i的元素移到第j的位置。实际上先将该元素删除，然后再将其插到指定位置，元素在删除前先存放在临时变量中。void move (int a,int n,int i,int j ) int k ,t; t=ai; for(k=i;k=j;k-) ak+1=ak;/*aj后的元素都要往后移位*/ aj=t; /* 插入*/上面函数中的两个for可以合并为一个for，就是将ai与aj之间的元素往前移一位：for(k=i;kj;k+) ak=ak+1;若需要移动多个元素，则定义一个数组，用来临时存放需移动的元素，移动时在前面加上循环。例如，移动字符串中的内容。移动的规则如下：把第1到第m个字符平移到字符串的最后，把第m+1到最后的字符串移到字符串的前部。若字符串中原有的内容为：ABCDEFGHIJK，m的值为3，则移动后，字符串中的内容应该是DEFGHIJKABC。void fun(char a , int m)char t80; int i,j, n;n=strlen(a);for(i=0;im;i+) ti=ai; /*移走*/for(i=m,j=0;in;i+,j+) aj=ai; /*移位*/for(i=0;im;i+) an-m+i=ti; /*移入*/main( )char a80=ABCDEFGHIJK;int m=3;fun(a,m);printf(%s,a);13.素数问题（1）判断m是否是素数的函数#include /*用sqrt函数必须包含数学库函数math.h */int prime(int m) int i,k; k=sqrt(m); /* k是不大于m平方根的最大整数*/ for (i=2;i=k;i+) if(m%i=0) return 0; /*不是素数，返回0*/ return 1; /*素数返回1*/（2）把mn范围内的素数依次存入数组a中，返回素数个数#include int prime(int aN,int m,int n) int i,k,j; j=0; /*j为数组a的下标，最终结果为素数的个数*/ for(i=m;i=n;i+) for(k=2;ksqrt(i) aj+=i; /*i是素数，存入数组a，下标增1*/ return j; /*返回素数个数*/14.求最大公约数和最小公倍数（1）求最大公约数（欧几里得算法 ）int gcd( int m, int n) int t,r; if(mn) t=m; m=n; n=t; /*若m=0) num=num*10+n; scanf(%d,&n); printf(%ld,num); 将数组a中的数拼成整数。long pdigit(int a,int n) long num=0;int i; for(i=0;in;i+) num=num*10+ai; return(num);main() int a5=3,2,7,6,7; printf(nnum=%ldn,pdigit(a,5);16.求反序数和回文数（1）求反序数将一个数的数字排列顺序完全颠倒过来，就变成另一个数，这个数就是该数的反序数，如123的反序数为321。求反序数的方法是先将一个数从个位开始用取余数拆分开来，再将拆开的数字拼成整数。即将拆整数和拼整数两个函数结合起来即可，边拆边拼。long inte(long n) long num=0; while(n) num=num*10+n%10; n=n/10; return(num);（2）求回文数 一个数与它的反序数相等，这样的数称为回文数。如12321，6336等就是回文数。 判断m是否是回文数判断一个数是否是回文数，先求出它的反序数，再判断两者是否相等。long palin(long m) long s=0,n; n=m; /*将m存入n中*/ while(n) s=s*10+n%10; n=n/10; /*求反序数*/ if(s=m) return （1); else return (0); 求指定范围内的回文数求指定范围内（m1m2之间）的回文数，保存到指定的数组中，返回回文数的个数。int palin(long m1,long m2,long x) long i,n,s; /*s是i的回文数*/ int k=0; /*k为回文数个数，数组下标*/ for(i=m1;i=m2;i+) n=i;s=0; while(n) s=s*10+n%10; n=n/10; /*求反序数*/ if(i=s) xk=i; k+; /*若是回文数，放入数组a中*/ return k; /*返回回文数的个数*/函数调用时，数组a定义为长整型，输入输出格式为“%ld”，常量后面要加字母“l”，例如，求1000000200000之间的回文数的调用形式为：n=palin（100000l,120000l,a）;其中，n为函数返回的回文数的个数。17.因子、完全数、互满数对（1）求a的因子并存放在数组中因子是指能被a整除的数，包含1和该数本身，真因子包含1不包含本身。例如，6的因子为1，2，3，6，真因子为1，2，3。int fun(int a, int x) int i,j=0; for(i=1;i=a;i+) /*求a的因子，若求真因子将i=a改为ia*/ if (a%i=0) xj+=i; /*i是a的因子，存入数组x中，下标增1*/ return j; /*返回因子的个数*/（2）找指定范围内的完全数完全数是指一个正整数的所有真因子之和等于本身的数，真因子包含1但不包含本身，例如，6=1+2+3，28=1+2+4+7+14，所以6和28是完全数。int fun(int aN,int m,int n) int i,j,s; int k=0; for(i=m;i=n;i+) s=0; /*对指定范围内的每个数i都要求其因子之和s*/ for(j=1;ji;j+) if (i%j=0) s=s+j; if(i=s) ak+=i;/*是完全数，存入数组中*/ return k; /*返回完全数的个数*/（3）互满数对（亲密数对）互满数对是指两个数中，其中的一个数的真因子之和都等于另一个数。即a的真因子之和为b，b的真因子之和为a。例如，220与184，1184与1210就是互满数对。int fun(int s2,int m1,int m2) /*求m1m2的互满数对*/ int s1,s2,count,a,i,j; count=0; for(a=m1;a=m2;a+) s1=1;s2=1; /*1也是真因子*/ for(i=2;ia;i+) if(a%i=0) s1=s1+i; /*a的真因子之和为s1*/ for(j=2;js1;j+) if(s1%j=0) s2=s2+j; /*s1的真因子之和为s2*/ if(s2=a) & (as1) /*互为真因子之和，存入二维数组s中*/ scount0=a; scount1=s1; count+; return count; /*返回数对个数*/ 18.求满足条件的数或数对求满足条件的数或数对经常采用穷举法。穷举法的基本思想是：一一列举各种可能的情况，并判断哪一种是符合要求的解。这是一种在“没有其他办法情况下的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。穷举法一般包含两类，一是找出符合特定条件的一组数（一组解），二是验证定理或猜想。（1）同构数同构数是其值等于其右边数字平方数的整数。如25, 36都是同构数（25=52, 36=62）。下面的程序是求199的所有同构数。main() int i,k; for(i=1; i100; i+) k=i%10; /*求未位数*/ if(k*k=i) printf(%d, ,i); /*输出满足要求的数*/ （2）Armstrong数（水仙花数）一个位的正整数，其各位数的次方之和等于这个数，称这个数为Armstrong数。例如，153=13+53+33。1634=14+64+34+44。下面的程序求所有三3位和4位的Armstrong数。main() int i,j,k,m,t,s,a5,b5; for(m=100;m10000;m+) k=m;j=0; /*k为临时变量，j为位数*/ while(k) aj+=k%10;k=k/10; /*a中存放各位数字*/ for(i=0;ij;i+) /*几位数就循环多少次*/ bi=1; /*b中存放各位数字之乘积*/ for(t=0;tj;t+) bi=bi*ai; for(s=0,t=0;tj;t+) s=s+bt; /*s为各位数字乘积之和*/ if(s=m) printf( %d,m); /*输出满足条件的数*/ （3）求满足条件的数或数对【例题1】找出所有满足下列条件的正整数对a，b：（1）a+b=99; （2）ab; （3）a与b的最小公倍数是3的倍数。编写函数int find(int m, int n)，其功能是找出两个正整数的最小公倍数并返回。编写main函数，找出所有满足条件的正整数对。【分析】正整数对要求满足a+b=99，表示a和b都在198的范围内，循环变量的变化从198就可以了。第二个条件是ab，只要让b从a开始就可以。第三个条件，先写一个求最小公倍数的函数，再用if语句调用并判断最小公倍数是否是3的倍数。#include main() int a,b; for(a=1;a99;a+) for(b=a;b99;b+) /*b从a开始，确保ab*/ if(a+b=99) /*第一个条件a+b=99*/ if(find(a,b)%3=0) /* a,b的最小公倍数是3的倍数*/ printf(%d+%d=99, mingps:%dn,a,b,find(a,b); int find(int m,int n) /*求两个整数的最小公倍数*/ int p,r; p=m*n; while(n) r=m%n;m=n;n=r; return(p/m);19.字符串问题字符串最大的特点是有一个字符串结束标志0，在进行字符串的有关操作时，判断一个字符串是否结束就是根据该标志，操作完后记得在字符串最后加上结束标志。（1）复制字符串 void strcopy(char from,char to) /*将from中的字符复制到to中*/ int i; for(i=0; toi!=0; i+) toi=fromi; toi=0; /*字符串末尾添加结束标志*/ 若用指针实现：void strcopy(char *from,char *to) for(;*from!=0;from+,to+) *to=*from; *to=0; （2）连接两个字符串 void strconnect(char s1,char s2) /*将s2字符串连接在s1的后面*/ int i,j; for(i=0; s1i; i+) ; /*求第一个字符串的长度*/ for(j=0; s2j; j+) s1i+=s2j; /*将第二个字符串连接到第一个字符串后面*/ s1i=0; /*字符串末尾添加结束标志*/（3）比较两个字符串int strcompare(char *s1,char *s2) while(*s1) & (*s2) & (*s1=*s2) /*若是相同的字符，指针下移 */ s1+ ; s2+ ; return(*s1-*s2); /*返回第一个不同字符的ASCII码值的差*/（4）求字符串长度int length(char *s) int n=0; while(*s) n+ ; s+ ; return (n) ;void main() char str20; scanf(%s,str) ; printf(The length of string is %d.n,length(str);（5）回文字符串判断一个给定字符串是否是回文，是函数返回1，否则返回0。例如，字符串“aba”、“agbga”是回文字符串，字符串abcdefg不是回文字符串。int stjug(char *s) char *f, *t; /* f指向字符串头，t指向字符串尾*/ for(f=s,t=s+strlen(s)-1; ft; f+,t-) if(*f!=*t) return 0; /* 比较f指向的字符与t指向的字符，不等返回0*/ return 1; （6）字符串排序字符串排序的算法与数的排序是相同的，不同的是字符串不能直接赋值及比较大小，而要用字符串复制函数和字符串比较函数。void BubbleSort(char a10,int n) /*字符串冒泡排序*/ int i,j; char tmp10; for(i=0; in-1; i+) for(j=0; j0) strcpy(tmp,aj); strcpy(aj,aj+1); strcpy(aj+1,tmp); 20.数字字符串与整数的相互转换（1）数字字符串转换成整数数字字符在计算机中是以ASCII码的形式存放的，整数是以补码的形式存放的。将数字字符转换成数字，要减去字符0的ASCII码值。然后再将一个个数字拼成整数。long str_to_int(char a) int i; long s=0; for(i=0;ai!=0; i+) s=s*10+ai-0; /*字符转换成数字并拼成整数*/ return (s);main() char a10; gets(a); printf(%ld,str_to_int(a);（2）整数转换成字符串将整数转换成数字字符串，先将整数分离成一个个数字，再将数字加上字符0的ASCII值转换成数字字符。最后在末尾加上字符串结束标志0。因为最先得到的最低位为数组的第一个元素，