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

全国计算机二级C常考算法编程指导.doc/*排序趟次/*从前往严从小到人,升全国计算机二级C常考算法编程指导变量交换voidswap(int*x,int*y){inttemp;temp=*x;*x=*y;*y=temp;}累加用C语言实现l+2+3+4+5+...+n的累加。【方法1】while循环实现intadd(intn){inti,sum;sum=0;i=l;while(i<=n){sum=sum+i;i=i+l;}returnsum;}main(){ints,n;printf(H\nInputn:\nn);scanf(n%dn,n);s=add(n); /*函数调用*/printf(nl+2+...+%d=%d\nn,n,s);}【方法2】for•循环实现(main函数同上)intadd(intn){inti,sum=0;for(i=l;i<=n;i++)sum=sum+i;returnsum;}do-while循环也可以实现累加,谙读者自己完成。累乘用C语言求n的阶乘:n!=123'4'...'n(nNl)intproduct(intn){inti,p=l;fbr(i=2;i<=n;i++)p=p*i;returnp;}如果n的值比较大,函数返回值和存放乘积的变量p应定义为long或者double型。4排序冒泡排序(主函数main参考教材181-182页)voidBubbleSort(inta[],intn){intijtmp;for(i=0;i<n-l;i++)*/{for(j=0;j<n-l-i;j++)后比*/if(a[j]>aU+l])序3V{tmp=a[j];a[j]=a[j+l];a[j+l]=tmp;}/*交换a[j]与a[j+l],大数后移*/(2)选择排序voidSelectSort(inta[],intn){inti,j,min,tmp;for(i=0;i<n-l;i++){min=i; /*假设第一个数最小,记录其下标引for(j=i+l;j<n;j++)if(a[j]<a[min])min=j;/*找最小的数,将最小数的下标记录下来*/if(i!=min){tmp=a[i];a[i]=a[min];a[min]=tmp;}/*将最小的数与笫一个数进行交换勺插入排序voidInscrtSort(inta[],intn){inti,j,tmp;fdr(i=l;i<n;i++){tmp=a[i]; /*空出a[i]单元*/for(j=i-l;j>=0&&a[j]>tmp;j-)aLj+l]=a[j]; /*大于tmp的数向后移位*/a[j+l]=tmp; /*tmp归位*/}}归并(合并)将两个有序数组A、B合并成另一个有序的数组C(升序或降序)。升序合并步骤如下:先在A、B数组中各取第一个元索进行比较,将小的元素放入C中。取小的元素所在数组的下一个元素与另一个数组屮上次比较后较大的元索进行比较。重复上述比较过程,肓到某个数组被先排完。将另一个数组剩余元素抄入C中,合并排序完成。voidmerge(inta[],intm,intb[n],intnjntc[]){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中*/whilc(ib<n){c[ic]=b[ib];ib卄;ic++;} /*b中剩余元素抄入c中*/}查找线性法查找线性法查找也叫顺序查找,对于没有排序的数组,只能采用线性法查找。将x与数组中的各个元素从头到尾进行比较,找到后返冋数组下标,若找不到,返冋-U//defineN10intfind(inta[N],intkey){inti;for(i=0;i<N;i++)if(a[i]=key){return;break;} /*返回数组元素下标*/if(i==N)return(-1);}如果对一•个升序数组进行线性法查找,循环结束条件改为“i<N&&a[i]<=kc/\返回・1的条件为(i==N||a[i]>key)o折半法查找(二分法查找)#defineN10intfind(inta[N],intkey){intm,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;}elseif(key<a[m])q=m-1;elsep=m+l;}if(p>q)return(-1);}级数计算(递推法)递推法是利用问题木身