全国计算机二级C常考算法编程指导.doc

/*排序趟次/*从前往严从小到人，升全国计算机二级C常考算法编程指导1. 变量交换void swap(int *x, int *y){ int temp;temp=*x; *x=*y; *y=temp;}2. 累加用C语言实现l+2+3+4+5+...+n的累加方法1】while循环实现int add(int n){ int i,sum;sum=0; i=l;while(i<=n){ sum=sum+i; i=i+l; }return sum;}main(){ int s,n;printf(H\nInput n:\nn);scanf(n%dn,n);s=add(n); /* 函数调用 */printf(nl+2+...+%d=%d\nn,n,s);}【方法2】for•循环实现(main函数同上) int add(int n){ int i,sum=0;for(i=l;i<=n;i++) sum=sum+i;return sum;}do-while循环也可以实现累加，谙读者自己 完成3. 累乘用 C 语言求 n 的阶乘:n!= 1234...n(nNl) int product (int n){ int i,p=l;fbr(i=2;i<=n;i++) p=p*i;return p;}如果n的值比较大，函数返回值和存放乘积 的变量p应定义为long或者double型。

4排序(1) 冒泡排序(主函数main参考教材181-182 页)void BubbleSort(int a[],int n){ intijtmp;for(i=0;iaU+l])序3V{tmp=a[j]; a[j]=a[j+l]; a[j+l]=tmp;}/*交 换a[j]与a[j+l],大数后移*/（2）选择排序void SelectSort(int a[],int n){ int i,j,min,tmp;for(i=0; i=0 && a[j]>tmp; j-） aLj+l]=a[j]; /* 大于 tmp 的数向后移位*/a[j+l]=tmp; /* tmp 归位 */}}5. 归并（合并）将两个有序数组A、B合并成另一个有序的 数组C （升序或降序）。

升序合并步骤如下:%1 先在A、B数组中各取第一个元索进行 比较，将小的元素放入C中1 取小的元素所在数组的下一个元素与另 一个数组中上次比较后较大的元索进行比 较1 重复上述比较过程，肓到某个数组被先 排完1 将另一个数组剩余元素抄入C中，合并 排序完成void merge(int a[],int m,int b[n],int njnt c[]){ int ia=0,ib=0,ic=0;while(iakey)o(2) 折半法查找(二分法查找)#define N 10int find(int a[N],int key){ int m,p,q;p=0;q=N-l; /*p为笫1个元素的下标，q为最后一个元素的下标*/while(p<=q){ m=(p+q)/2; /*m为中间元索的下标*/if (a[m]==key) { return (m); break;}else if(keyq) return (-1);}7. 级数计算(递推法)递推法是利用问题木身所具有的一种递推 关系求问题解的一种方法。

简单地说，就是 后一项的值利用前面已求得的项的值得到， 典型的递推算法如Fibonacci数列(斐波那 契数列)，后一项为前两项的和基本操作 中的累加与累乘都可以看作递推法递推公式包括两部分：开始项的值，以及从 前面一、两项得到下一项的计算方法用递 推式比通项公式算得要快，因为计算每一项 都充分利用了前一项的计算结果例如，有一分数序列： 2/1,3/2,5/3,8/5,13/8,21/13,…求出这个数列的 前20项之和求最大、最小值(1) 查找一维数组a[]中的最大值，n为数 组的人小int funmax (int a[], int n){ int i,max=a[0];for(i=l;ia[i]) max=a[i];return max;}(2) 查找二维数组a中的最小值有一个3x4的矩阵，求所有元素的最小值及 该元索的行号列号因为函数只能返回一•个 值，要想得到最小元素的行号和列号，需要 用指针作函数的参数int funmin(int a[][4], int *min_i,int *min_j){ int i,j,min;min=a[0][0];for(i=0;i<3;i++)for(j=0;j<4;j4-+)if(a[i][j]

9. 求和及平均值求数纽的平均值，先用循坏将数组的所有元 素相加，最后返回所得的和除以数组元素的 个数float avcragc(int a[],int n){ int i; float avg;avg=0;fbr(i=0;i

程序段如下： for(j=N-l;j>i;j-) a[j+l]=a[j]; /* 移位 */ a[i+l]=x; /* 插入 x */(2) 在己排序的数组中插入一个数 有一个已经排好序的数组，现有一个数X, 要求按原来的规律将它插入数组中首先判断此数是否人于最后一个数，然后再 考虑插入中间的情况，找插入点，先将插入 点之后的数依次后移一个位置define N 10void insert(int a[N],int num){ int i j;if (num>a[N-2]) a[N-l]=num; /*插在最后 */elsetor(i=0; inum) /*找插入点，插在a[i]位置*/{ for(j=N-2;j>=i;j-)a[j+l]=aU]； /*将a[i]以后的元素 从最后一个元索开始后移*/a[i]=num; /*将 num 放在 a[i] 处*/break;}}(3) 删除数组中的一个元素a[i]删除数组中的元素a[i],就是将a[i]以后的 元素往前移一个位置void del (int a[],int n,int i){ intj；for(j=i;j

例如，将一维数组下标为i的元素移到 笫j的位置实际上先将该元素删除，然后 再将其插到指定位置，元素在删除而先存放 在临时变量中void move (int a[],int n,int i,int j ){ int k ,t;t=a[i]；for(k=i;k=j;k-) a[k+1 ]=a[k];/*a[j]后的 元素都要往后移位*/a[j]=t; /* 插入*/}上而函数中的两个for■可以合并为一个。