搜索
C语言算法总结2.牛顿迭代求a的平方根【思想汇总】迭代公式为xn+1=0.5(xn+a/xn),要求前后两次求出的x的差的绝对值小于10-5。【算法语句】floata,x0,x1;scanf(“%f”,&a);x0=a/2;/*先定义两个变量，利用公式求出第一组数*/x1=(x0+a/x0)/2;do{x0=x1;x1=(x0+a/x0)/2;/*循环N次当满足x0与x1的差小于10-5输出答案}while(fabs(x1-x0)=1e-5);*/x1即为所求。【思想推广】牛顿迭代法求平方根是一种逼近的数学思想，用途十分广泛，如上机指导实验六第三题，arcsh(x)函数。3.求最大公约数，最小公倍数【思想汇总】求此数有三种思想，一是定义法求解，二是相减求等法，三是辗转相除法。具体算法如下。【算法语句】gys(intm,intn){inti,x;x=mn?m:n;for(i=x;i=1;i--)if(m%i==0&&n%i==0)break;/*此为定义法，先找一个相对最小的数x，returni;再定义一个变量从x到1递减，判断是否能同时被两个数整除*/}gys(intm,intn){while(m!=n)if(mn)m=m-n;/*此为相减求等法，大减小，这样逐步相减，当它相等时，elsen=n-m;即为答案*/returnm;}gys(intm,intn){intr;while((r=m%n)!=0){m=n;n=r;}/*辗转相除法是最简单的方法，但要好好理解*/returnn;}【思想推广】求公约数和公倍数在最近的考试中不常出现，只需理解其原理即可。其思想即是熟练掌握公式。4.数的分解【思想汇总】其思想较为简单，即除以其权重，把数一个个剥离出来，但其实现方式多样，如硬性分解，循环分解，递归分解等。【算法语句】1.硬性分解，所为硬性分解即是已知此数的位数进行的分解，如已知一个5位数的数x，将其分解为ge,shi,bai,qian,wanwan=x/10000;qian=x%10000/1000;bai=x%1000/100;shi=x%100/10;ge=x%10;2.循环分解，循环分解其优点是无需知道数的位数。while(n0){a[i]=n%10;/*注意：在用此方法是要将数组位数的足够大，并且i要至n=n/10;零*/i++;}3.递归法利用函数的递归也可快速的进行数的分解，其优点是为数不限，比循环分解还要优越，且代码短小精悍，执行时间短。printz(longn){if(n0){printz(n/10);/*先返回除最高位的数，所以最后输出是是按照正向输出的printf(“%ld”,n%10);*/}}printd(longn){if(n0){printf(“%ld”,n%10);/*先输出个位，再返回除高位，因此这是逆向输出*/printd(n/10);}}【思想推广】数的分解形式多样，看个人喜好，可以采取多种方式，最经典的程序莫过于水仙花数，个人比较推荐用递归，代码简单，效率高。5数的合并（乘权求和）【思想汇总】数的合并绝大多数都是一种乘权求和的思想，其思想精髓在于每一位xi乘以其权重Ni在对其求和，公式如下∑xi*Ni【算法语句】1.将一个base进制的字符串转化为一个十进制的数main(){char*p,s[6];intn=0;gets(s);for(p=s+strlen(s)-1;p=s;p--){if(*p='a'&&*p='z')n=n+(*p-'a'+10)*t;elseif(*p='A'&&*p='Z')N=N+(*p-'A'+10)*t;elsen=n+(*p-'0')*t;t=t*base;/*base为要转换的进制*/}}2.十进制转R进制c10_16(char*p,intb){intj;while(b0){j=b%R;if(i10)*p=j+48;/*此处是说将每位上的数加上48转换成数字字符*/else*p=j+55;/*若数大于10则转化为字母字符*/b=b/16;p++;}*p=’\0’;}/*此红字部分可以忽略红字部分的算法他是把结果数组中的元素当成字符串用%c输出地不要那部分我们把数组元素以%d格式逐个输出*/【思想推广】乘权求和一般用于进制的转换，字符串与整形的转换，补充一个知识点，若遇到字符和数字的转化可用这样几个头文件里包括的函数intatoi(string)（将字符串转化为整形）doubleatof(string)（将字符串转化为浮点型）stringitoa(int)（将整形转化为字符串），在用这些函数时要写#includestdlib.h7.一维数组基本操作（逆置，合并，查找，插入&删除）【思想汇总】一维数组操作十分简单，灵活多变，可以用一般的数组形式表示，也可以用指针，在这里不妨让我总结一下数组与指针表达形式inta[100],*p;p=a;第i个元素值*(a+i)*(p+i)a[i]p[i]第i个元素地址a+ip+i&a[i]&p[i]这个表格要牢牢掌握，不能犯错！！！！【算法语句】1.倒置这里只介绍指针法。voidreverse(int*d,intn){int*p1,*p2,t;p1=d;p2=d+n-1;while(p1p2){t=*p1;*p1=*p2;*p2=t;p1++;p2--;}}2.合并合并有单纯的两数组合并，也有按照某个规则合并，不管怎样都很简单，这里就不一一写了。3.查找查找有顺序查找也有折半查找顺序查找是指关键字与数组中每一个进行比较验证，此方法比较浪费时间，但代码简单易掌握inti;for(i=0;in;i++)if(a[i]==m)returnireturn(-1)还有一种折半查找，此方法速度较快，但须事先将数组排序，代码繁琐，就不介绍了。4插入&删除对于这类操作首先要进行定位，一般用指针来移动定位，在进行插入或删除操做【思想推广】一维数组操作时十分简单的，在二级考试中一般只做为填空或选择，在大题目中一般不出现。一维数组的熟练掌握对后面的二维数组有很大的帮助8.二维数组的操作【思想汇总】二维数组操作是一个很重要的内容，其变化方式也是多种多样，但万变不离其宗，只要你能熟练使用（二维）指针就能轻松应对各种难题。先列出一个重要的表格给大家a[i][j]的地址&a[i][j]a[i]+j*(a+i)+ja[i][j]的值a[i][j]*(a[i]+j)*(*(a+i)+j)(*(a+i))[j]若int*p=a[0]p+i*m+j既是a[i][j]的地址（m既是二维数组的列数）上面这张表十分重要，几乎历年的改错题都和二维数组有关，并且都会有一两个错误出自此处【算法语句】1.二维数组转置(上下三角操作)voidturn(inta[4][4]){inti,j,k;for(i=0;i4;i++)for(j=0;j4;j++)if(ij){t=a[i][j];a[i][j]=a[j][i];a[j][i]=t;}}上下三角元素交换voidturn（inta[4][4]）{inti,j,t;for(i=0;i4;i++)for(j=0;ji;j++)/*此行还可改为for(j=i+1;j4;j++)*/{t=a[i][j];a[i][j]=a[j][i];a[j][i]=t;}}2.列（行）互换若要求第A行与第B行互换则voidexchange(inta[4][4]){inti,k;for(i=0;i4;i++){k=a[A][i];a[A][i]=a[B][i];a[B][i]=k}/*行互换时，列从0到N变换，再用三}段交换法*/同理可得列互换3.二维函数求和（对角线求和，周边元素求和）对角线求和fsum(inta[N][N],intn){inti,sum=0;for(i=0;in;i++)sum+=a[i][i]+a[i][N-i-1];returnsum;}周边元素求和，有两种思维，一是求全体和减去其内部元素之和，二是扫描全体元素，若元素在周边，则累加。我就写一个第二种思维的程序inti,j,sum=0;for(i=0;iN;i++)for(j=0;jN;j++)if(i==0||j==0||i=N-1||j==N-1)/*这是一个判断是否在周边的语句，在写此类语句是sum+=a[i][j];一定要注意“与”和“或”要弄清楚*/【思想推广】二维数组的操作还远不止这些，但都与此类似，在做这类题目时一定要注意定位准确，操作符合规则，若出现比较繁琐的操作，可考虑化简，或是逆向思考，可以迎刃而解。前面的八个类型是最基本最重要的，一定要超熟练的掌握，后面补充一些比较难的算法，供大家发挥。10.结构体共用体【思想汇总】结构体共用体属于C语言当中较难的一块，在C语言上机考试中一般不会出现，但经常会在选择填空题中出现，一定要注意其格式正确，调用正确，操作正确这三点。【算法语句】针对这三点，我来做个总结。1.定义结构体structstudent{intnum;charname[20];charsex;结构体名intage;floatscore;charaddr[30];}；分号不能丢。新定义的类型（int、float...)一样，可用来定义变量。Structstudentstudent1,student2;当然也可以紧贴着定义结构体的后面定义变量。2.结构体调用结构体调用有两种方式，一变量调用，二指针调用。如调用上面这个我们已经定义好的结构体，student1.age既是调用了student1的年龄。指针调用首先要指针指向structstudent*p;p=&student1;p-age和student1.age等价。注意p-n++和++p-n的不同。上面讲的是结构体变量的调用，若用指针还可以指向结构体数组structstudentstu[4];structstudentp;p=stu;此时就定义了一指针来指向这个结构体数组要想调用每个元素，需要使用以下循环for(;pstu+5;p++)这样p指针就可以指向各个不同的结构数组了。3.结构体的操作，一般操作我就不一一介绍了，在前八个经典算法中都有。最难的链表操作放最后讲。【思想推广】结构体其实没什么难的，但和别的联系起来就难了，在做结构体的题目时尽量写画张图，理清顺序再做。11.文件使用【思想汇总】文件使用很简单，在每次上机考试中都会出现，但操作都一样，无非是打开、使用、关闭。这里就把这三种介绍一下就好了。【算法语句】1.文件的打开FILE*fp;首先要定义一个文件指针。if((fp=fopen(“d:\\myf2.out”,”w”))==NULL){printf(“Thefilecannotopen!”);exit(0);}先判断，再输入，这句话必写！！！2.文件使用一般文件使用仅限于文件输出，输出格式如下fprintf(fp,”max=%d\n”,max);和printf()类似3文件关闭fclose(fp);即可【思想推广】没啥可推广的12.函数【思想汇总】函数是组成一个完整程序的基础，它变化多端，我也不好一一介绍，就说几点较难的东西，大家都知道函数中定义的变量都是auto型，也就是说出函数后定义的空间就自动释放了。作为函数只能返回一个变量，要想让其“返回”多个值就需要使用到指针。我是这样理解函数的，所谓函数就是你给其值，进行一系列规定运算，再给你一个答案。和数学中映射的概念相似。这里我就介绍一下指针与函数的关系。【算法语句】1.指向函数的指针（函数指针）main(){intmax(),(*p)();inta,b,c;p=max;/*先定义一个指针指向某个函数*/scanf(“%d,%d”,&a,&b);c=(*p)(a,b);/*在使用函数指针是无需再写函名*/printf(“a=%d,b=%d,max=%d”,a,b,c);}max(intx,inty){intzif(xy)z=x;elsez=y;return(z);}2.返