C语言基本算法简单级别.doc

一、根本 1交换两量交换借助第三者例1、任意读入两个整数，将二者的值交换后输出。 main()int a,b,t; scanf("%d%d",&a,&b); printf("%d,%dn",a,b);t=a; a=b; b=t; printf("%d,%dn",a,b);【解析】程序中加粗局部为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。其中t为中间变量，起到"空杯子的作用。注意：三句赋值语句赋值号左右的各量之间的关系！【应用】例2、任意读入三个整数，然后按从小到大的顺序输出。main()int a,b,c,t; scanf("%d%d%d",&a,&b,&c); /*以下两个if语句使得a中存放的数最小*/ if(a>b)t=a;a=b;b=t; if(a>c)t=a;a=c;c=t; /*以下if语句使得b中存放的数次小*/ if(b>c) t=b;b=c;c=t; printf("%d,%d,%dn",a,b,c);2累加累加算法的要领是形如"s=s+A的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。"A通常是有规律变化的表达式，s在进入循环前必须获得适宜的初值，通常为0。例1、求1+2+3+100的和。main()int i,s;s=0; i=1; while(i<=100) s=s+i; /*累加式*/i=i+1; /*特殊的累加式*/ printf("1+2+3+.+100=%dn",s);【解析】程序中加粗局部为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中"i = i + 1为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。3累乘累乘算法的要领是形如"s=s*A的累乘式，此式必须出现在循环中才能被反复执行，从而实现累乘功能。"A通常是有规律变化的表达式，s在进入循环前必须获得适宜的初值，通常为1。例1、求10！分析10！=1×2×3××10main()int i; long c; c=1; i=1; while(i<=10) c=c*i; /*累乘式*/ i=i+1; printf("1*2*3*.*10=%ldn",c);二、非数值计算经典算法1穷举也称为"枚举法，即将可能出现的每一种情况一一测试，判断是否满足条件，一般采用循环来实现。例1、用穷举法输出所有的水仙花数即这样的三位正整数：其每位数位上的数字的立方和与该数相等，比方：13+53+33=153。法一main()int *,g,s,b; for(*=100;*<=999;*+) g=*%10;s=*/10%10;b=*/100; if(b*b*b+s*s*s+g*g*g=*)printf("%dn",*);【解析】此方法是将100到999所有的三位正整数一一考察，即将每一个三位正整数的个位数、十位数、百位数一一求出各数位上的数字的提取算法见下面的"数字处理，算出三者的立方和，一旦与原数相等就输出。共考虑了900个三位正整数。法二main()int g,s,b; for(b=1;b<=9;b+) for(s=0;s<=9;s+) for(g=0;g<=9;g+) if(b*b*b+s*s*s+g*g*g=b*100+s*10+g) printf("%dn",b*100+s*10+g);【解析】此方法是用1到9做百位数字、0到9做十位和个位数字，将组成的三位正整数与每一组的三个数的立方和进展比较，一旦相等就输出。共考虑了900个组合外循环单独执行的次数为9，两个循环单独执行的次数分别为10次，故if语句被执行的次数为9×10×10=900，即900个三位正整数。与法一判断的次数一样。2排序1冒泡排序起泡排序假设要对含有n个数的序列进展升序排列，冒泡排序算法步骤是：从存放序列的数组中的第一个元素开场到最后一个元素，依次对相邻两数进展比较，假设前者大后者小，则交换两数的位置；第趟完毕后，最大数就存放到数组的最后一个元素里了，然后从第一个元素开场到倒数第二个元素，依次对相邻两数进展比较，假设前者大后者小，则交换两数的位置；重复步骤n-1趟，每趟比前一趟少比较一次，即可完成所求。例1、任意读入10个整数，将其用冒泡法按升序排列后输出。*define n 10 main()int an,i,j,t; for(i=0;i<n;i+) scanf("%d",&ai); for(j=1;j<=n-1;j+) /*n个数处理n-1趟*/ for(i=0;i<=n-1-j;i+) /*每趟比前一趟少比较一次*/ if(ai>ai+1)t=ai;ai=ai+1;ai+1=t; for(i=0;i<n;i+)printf("%dn",ai);2选择法排序选择法排序是相对好理解的排序算法。假设要对含有n个数的序列进展升序排列，算法步骤是：从数组存放的n个数中找出最小数的下标算法见下面的"求最值，然后将最小数与第1个数交换位置；除第1个数以外，再从其余n-1个数中找出最小数即n个数中的次小数的下标，将此数与第2个数交换位置；重复步骤n-1趟，即可完成所求。例1、任意读入10个整数，将其用选择法按升序排列后输出。*define n 10 main()int an,i,j,k,t; for(i=0;i<n;i+) scanf("%d",&ai); for(i=0;i<n-1;i+) /*处理n-1趟*/ k = i; /*总是假设此趟处理的第一个即全部数的第i个数最小，k记录其下标*/ for(j=i+1;j<n;j+) if(aj < ak) k = j; if (k != i)t = ai; ai = ak; ak = t; for(i=0;i<n;i+) printf("%dn",ai);3插入法排序要想很好地掌握此算法，先请了解"有序序列的插入算法，就是将*数据插入到一个有序序列后，该序列仍然有序。插入算法参见下面的"数组元素的插入。例1、将任意读入的整数*插入一升序数列后，数列仍按升序排列。*define n 10main() int an=-1,3,6,9,13,22,27,32,49,*,j,k; /*注意留一个空间给待插数*/ scanf("%d",&*); if(*>an-2) an-1=* ; /*比最后一个数还大就往最后一个元素中存放*/ else /*查找待插位置*/ j=0; while( j<=n-2 && *>aj) j+; /*从最后一个数开场直到待插位置上的数依次后移一位*/ for(k=n-2; k>=j; k- -) ak+1=ak; aj=*; /*插入待插数*/ for(j=0;j<=n-1;j+) printf("%d ",aj);插入法排序的要领就是每读入一个数立即插入到最终存放的数组中，每次插入都使得该数组有序。例2、任意读入10个整数，将其用插入法按降序排列后输出。*define n 10 main()int an,i,j,k,*; scanf("%d",&a0); /*读入第一个数，直接存到a0中*/ for(j=1;j<n;j+) /*将第2至第10个数一一有序插入到数组a中*/ scanf("%d",&*); if(*<aj-1) aj=*; /*比原数列最后一个数还小就往最后一个元素之后存放新读的数*/ else /*以下查找待插位置*/ i=0; while(*<ai&&i<=j-1) i+; /*以下for循环从原最后一个数开场直到待插位置上的数依次后移一位*/ for(k=j-1;k>=i;k-) ak+1=ak; ai=*; /*插入待插数*/ for(i=0;i<n;i+)printf("%dn",ai);4归并排序 即将两个都升序或降序排列的数据序列合并成一个仍按原序排列的序列。例1、有一个含有6个数据的升序序列和一个含有4个数据的升序序列，将二者合并成一个含有10个数据的升序序列。*define m 6*define n 4main()int am=-3,6,19,26,68,100 ,bn=8,10,12,22; int i,j,k,cm+n; i=j=k=0; while(i<m && j<n) /*将a、b数组中的较小数依次存放到c数组中*/ if(ai<bj)ck=ai; i+; else ck=bj; j+; k+; while(i>=m && j<n) /*假设a中数据全部存放完毕，将b中余下的数全部存放到c中*/ ck=bj; k+; j+; while(j>=n && i<m) /*假设b中数据全部存放完毕，将a中余下的数全部存放到c中*/ ck=ai; k+; i+; for(i=0;i<m+n;i+) printf("%d ",ci);3查找1顺序查找即线性查找顺序查找的思路是：将待查找的量与数组中的每一个元素进展比较，假设有一个元素与之相等则找到；假设没有一个元素与之相等则找不到。例1、任意读入10个数存放到数组a中，然后读入待查找数值，存放到*中，判断a中有无与*等值的数。*define N 10main()int aN,i,*; for(i=0;i<N;i+) scanf("%d",&ai); /*以下读入待查找数值*/ scanf("%d",&*); for(i=0;i<N;i+) if(ai=*)break ; /*一旦找到就跳出循环*/ if(i<N) printf("Found!n"); else printf("Not found!n");2折半查找即二分法顺序查找的效率较低，当数据很多时，用二分法查找可以提高效率。使用二分法查找的前提是数列必须有序。二分法查找的思路是：要查找的关键值同数组的中间一个元素比较，假设一样则查找成功，完毕；否则判别关键值落在数组的哪半局部，就在这半局部中按上述方法继续比较，直到找到或数组中没有这样的元素值为止。例1、任意读入一个整数*，在升序数组a中查找是否有与*等值的元素。*define n 10main()int an=2,4,7,9,12,25,36,50,77,90; int *,high,low,mid;/*为关键值*/ scanf("%d",&*); high=n-1;low=0; mid=(high+low)/2; while(amid!=*&&low<high) if(*<amid) high=mid-1; /*修改区间上界*/ else low=mid+1; /*修改区间下界*/ mid=(high+low)/2; if(*=amid) printf("Found %d,%dn",*,mid); else printf("Not foundn");三、数值计算常用经典算法：1级数计算级数计算的关键是"描述出通项，而通项的描述法有两种：一为直接法、二为间接法又称递推法。直接法的要领是：利用项次直接写出通项式；递推法的要领是：利用前一个或多个通项写出后一个通项。可以用直接法描述通项的级数计算例子有：11+2+3+4+5+21+1/2+1/3+1/4+1/5+等等。可以用间接法描述通项的级数计算例子有：11+1/2+2/3+3/5+5/8+8/13+21+1/2!+1/3!+1/4! +1/5!+等等。1直接法求通项例1、求1+1/2+1/3+1/4+1/5+1/100的和。main()float s; int i; s=0.0; for(i=1;i<=100;i+)s=s+1.0/i; printf("1+1/2+1/3+.+1/100=%fn",s);【解析】程序中加粗局部就是利用项次i的倒数直接描述出每一项，并进展累加。注意：因为i是整数，故分子必须写成1.0的形式！2间接法求通项即递推法例2、计算以下式子前20项的和：1+1/2+2/3+3/5+5/8+8/13+。分析此题后项的分子是前项的分母，后项的分母是前项分子分母之和。main()float s,fz,fm,t,fz1; int i; s=1; /*先将第一项的值赋给累加器s*/ fz=1;fm=2; t=fz/fm; /*将待加的第二项存入t中*/ for(i=2;i<=20;i+) s=s+t; /*以下求下一项的分子分母*/ fz1=fz; /*将前项分子值保存到fz1中*/ fz=fm; /*后项分子等于前项分母*/ fm=fz1+fm; /*后项分母等于前项分子、分母之和*/ t=fz/fm; printf("1+1/2+2/3+.=%fn",s);下面举一个通项的一局部用直接法描述，另一局部用递推法描述的级数计算的例子：例3、计算级数的值，当通项的绝对值小于eps时计算停顿。*include <math.h>float g(float *,float eps);main()float *,eps; scanf("%f%f",&*,&eps); printf("n%f,%fn",*,g(*,eps);float g(float *,float eps)int n=1;float s,t; s=1;t=1; do t=t*/(2*n); s=s+(n*n+1)*t; /*加波浪线的局部为直接法描述局部，t为递推法描述局部*/n+; while(fabs(t)>eps); return s;四、其他常见算法1迭代法其根本思想是把一个复杂的计算过程转化为简单过程的屡次重复。每次重复都从旧值的根底上递推出新值，并由新值代替旧值。例如，猴子吃桃问题。猴子第一天摘下假设干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，就只剩一个桃子了。编程求第一天共摘多少桃子。main()int day,peach; peach=1; for(day=9;day>=1;day-) peach=(peach+1)*2; printf("The first day:%dn",peach);2进制转换1十进制数转换为其他进制数一个十进制正整数m转换成r进制数的思路是，将m不断除以r取余数，直到商为0时止，以反序输出余数序列即得到结果。注意，转换得到的不是数值，而是数字字符串或数字串。例如，任意读入一个十进制正整数，将其转换成二至十六任意进制的字符串。void tran(int m,int r,char str,int *n)char sb="0123456789ABCDEF" int i=0,g; dog=m%r; stri=sbg; m=m/r; i+;while(m!=0); *n=i;main()int *,r0; /*r0为进制基数*/ int i,n; /*n中存放生成序列的元素个数*/ char a50; scanf("%d%d",&*,&r0); if(*>0&&r0>=2&&r0<=16) tran(*,r0,a,&n);for(i=n-1;i>=0;i-)printf("%c",ai);printf("n"); else e*it(0);2其他进制数转换为十进制数其他进制整数转换为十进制整数的要领是："按权展开，例如，有二进制数101011，则其十进制形式为1×25+0×24+1×23+0×22+1×21+1×20=43。假设r进制数ana2a1n位数转换成十进制数，方法是an×r n-1+a2×r1+a1×r0。注意：其他进制数只能以字符串形式输入。例1、任意读入一个二至十六进制数字符串，转换成十进制数后输出。*include "string.h"*include "ctype.h"main()char *20;int r,d; gets(*); /*输入一个r进制整数序列*/ scanf("%d",&r); /*输入待处理的进制基数2-16*/ d=Tran(*,r); printf("%s=%dn",*,d);int Tran(char *p,int r)int d,i,cr;char fh,c; d=0; fh=*p; if(fh='-')p+; for(i=0;i<strlen(p);i+) c=*(p+i); if(toupper(c)>='A')cr=toupper(c)-'A'+10; elsecr=c-'0' d=d*r+cr; if(fh='-')d=-d; return(d);4字符处理1字符统计：对字符串中各种字符出现的次数的统计。典型例题：任意读入一个只含小写字母的字符串，统计其中每个字母的个数。*include "stdio.h "main()char a100;int n26=0;int i; /*定义26个计数器并置初值0*/gets(a); for(i=0;ai!= '0' ;i+) /*n0中存放a的个数，n1 中存放b的个数*/nai-'a'+; /*各字符的ASCII码值减去a的ASCII码值，正好得到对应计数器下标*/for(i=0;i<26;i+)if(ni!=0)printf("%c:%dn ",i+'a',ni);2字符加密例如、对任意一个只含有英文字母的字符串，将每一个字母用其后的第三个字母替代后输出字母*后的第三个字母为A，字母Y后的第三个字母为B，字母Z后的第三个字母为C。*include "stdio.h"*include "string.h"main()char a80= "China"int i;for(i=0;i<strlen(a);i+) if(ai>='*'&&ai<='z'|ai>='*'&&ai<='Z')ai=ai-26+3;else ai= ai+3;puts(a);5整数各数位上数字的获取算法核心是利用"任何正整数整除10的余数即得该数个位上的数字的特点，用循环从低位到高位依次取出整数的每一数位上的数字。例1、任意读入一个5位整数，输出其符号位及从高位到低位上的数字。main()long *; int w,q,b,s,g; scanf("%ld",&*); if(*<0) printf("-,"); *=-*; w=*/10000; /*求万位上的数字*/ q=*/1000%10; /*求千位上的数字*/ b=*/100%10; /*求百位上的数字*/ s=*/10%10; /*求十位上的数字*/ g=*%10; /*求个位上的数字*/ printf("%d,%d,%d,%d,%dn",w,q,b,s,g);例2、任意读入一个整数，依次输出其符号位及从低位到高位上的数字。分析此题读入的整数不知道是几位数，但可以用以下例如的方法完成此题：例如读入的整数为3796，存放在*中，执行*%10后得余数为6并输出；将*/10得379后赋值给*。再执行*%10后得余数为9并输出；将*/10得37后赋值给*直到商*为0时终止。main()long *; scanf("%ld",&*); if(*<0) printf("- "); *=-*; do /*为了能正确处理0，要用do_while循环*/ printf("%d ",*%10); *=*/10; while(*!=0); printf("n");例3、任意读入一个整数，依次输出其符号位及从高位到低位上的数字。分析此题必须借助数组将依次求得的低位到高位的数字保存后，再逆序输出。main()long *; int a20,i,j; scanf("%ld",&*); if(*<0) printf("- "); *=-*; i=0; do ai=*%10; *=*/10; i+; while(*!=0); for(j=i-1;j>=0;j-) printf("%d ",aj); printf("n");6辗转相除法求两个正整数的最大公约数该算法的要领是：假设两个正整数为a和b，先求出前者除以后者的余数，存放到变量r中，假设r不为0，则将b的值得赋给a，将r的值得赋给b；再求出a除以b的余数，仍然存放到变量r中如此反复，直至r为0时终止，此时b中存放的即为原来两数的最大公约数。例1、任意读入两个正整数，求出它们的最大公约数。法一：用while循环时，最大公约数存放于b中main()int a,b,r; doscanf("%d%d",&a,&b); while(a<=0|b<=0); /*确保a和b为正整数*/ r=a%b; while(r!=0) a=b;b=r;r=a%b; printf("%dn",b);法二：用dowhile循环时，最大公约数存放于a中main()int a,b,r; doscanf("%d%d",&a,&b); while(a<=0|b<=0); /*确保a和b为正整数*/ do r=a%b;a=b;b=r;while(r!=0); printf("%dn",a);【引申】可以利用最大公约数求最小公倍数。提示：两个正整数a和b的最小公倍数=a×b/最大公约数。例2、任意读入两个正整数，求出它们的最小公倍数。法一：利用最大公约数求最小公倍数main()int a,b,r,*,y; doscanf("%d%d",&a,&b); while(a<=0|b<=0); /*确保a和b为正整数*/ *=a; y=b; /*保存a、b原来的值*/ r=a%b; while(r!=0) a=b;b=r;r=a%b; printf("%dn",*y/b); 法二：假设其中一数的最小倍数也是另一数的倍数，该最小倍数即为所求main()int a,b,r,i; do scanf("%d%d",&a,&b); while(a<=0|b<=0); /*确保a和b为正整数*/ i=1; while(a*i%b!=0) i+; printf("%dn",i*a);7求最值 即求假设干数据中的最大值或最小值。算法要领是：首先将假设干数据存放于数组中，通常假设第一个元素即为最大值或最小值，赋值给最终存放最大值或最小值的ma*或min变量中，然后将该量ma*或min的值与数组其余每一个元素进展比较，一旦比该量还大或小，则将此元素的值赋给ma*或min所有数如此比较完毕，即可求得最大值或最小值。例1、任意读入10个数，输出其中的最大值与最小值。*define N 10main()int aN,i,ma*,min; for(i=0;i<N;i+)scanf("%d",&ai); ma*=min=a0; for(i=1;i<N;i+) if(ai>ma*) ma*=ai; elseif(ai<min) min=ai; printf("ma*=%d,min=%dn",ma*,min);8判断素数素数又称质数，即"只能被1和自身整除的大于1的自然数。判断素数的算法要领就是依据数学定义，即假设该大于1的正整数不能被2至自身减1整除，就是素数。例1、任意读入一个正整数，判断其是否为素数。main()int *,k; do scanf("%d",&*); while(*<=1); /*确保读入大于1的正整数*/ for(k=2;k<=*-1;k+) if(*%k=0)break; /*一旦能被2自身-1整除，就不可能是素数*/ if(k=*)printf("%d is sushun",*); elseprintf("%d is not sushun",*);以上例题可以用以下两种变形来解决需要使用辅助判断的逻辑变量：【变形一】将"2自身-1的围缩小至"2自身的一半main()int *,k,flag; doscanf("%d",&*);while(*<=1); flag=1; /*先假设*就是素数*/ for(k=2;k<=*/2;k+) if(*%k=0)flag=0; break;/*一旦不可能是素数，即置flag为0*/ if(flag=1) printf("%d is sushun",*); else printf("%d is not sushun",*);【变形二】将"2自身-1的围缩小至"2自身的平方根*include "math.h"main()int *,k,flag; do scanf("%d",&*);while(*<=1); flag=1; /*先假设*就是素数*/ for(k=2;k<=(int)sqrt(*);k+) if(*%k=0)flag=0; break;/*一旦不可能是素数，即置flag为0*/ if(flag=1) printf("%d is sushun",*); elseprintf("%d is not sushun",*);例2、用筛选法求得100以的所有素数。算法为：1定义一维数组a，其初值为：2，3，100； 2假设ak不为0，则将该元素以后的所有ak的倍数的数组元素置为0；3a中不为0的元素，均为素数。 *include <math.h> *include <stdio.h> main( ) int k,j,a101;clrscr(); /*清屏函数*/for(k=2;k<101;k+)ak=k;for(k=2;k<sqrt(101);k+) for(j=k+1;j<101;j+)if(ak!=0&&aj!=0) if(aj%ak=0)aj=0;for(k=2;k<101;k+) if(ak!=0)printf("%5d",ak);9数组元素的插入、删除1数组元素的插入此算法一般是在已经有序的数组中再插入一个数据，使数组中的数列依然有序。算法要领是：假设待插数据为*，数组a中数据为升序序列。先将*与a数组当前最后一个元素进展比较，假设比最后一个元素还大，就将*放入其后一个元素中；否则进展以下步骤；先查找到待插位置。从数组a的第1个元素开场找到不比*小的第一个元素，设其下标为i ；将数组a中原最后一个元素至第i个元素依次一一后移一位，让出待插数据的位置，即下标为i的位置；将*存放到a(i)中。例题参见前面"排序中插入法排序的例1。2数组元素的删除此算法的要领是：首先要找到也可能找不到待删除元素在数组中的位置即下标，然后将待删元素后的每一个元素向前移动一位，最后将数组元素的个数减1。例1、数组a中有假设干不同考试分数，任意读入一个分数，假设与数组a中*一元素值相等，就将该元素删除。*define N 6main()int fsN=69,90,85,56,44,80,*; int i,j,n; n=N; scanf("%d",&*); /*任意读入一个分数值*/ /*以下查找待删分数的位置，即元素下标*/ for(i=0;i<n;i+) if(fsi=*)break; if(i=n) printf("Not found!n"); else /*将待删位置之后的所有元素一一前移*/ for(j=i+1;j<n;j+) fsj-1=fsj; n=n-1; /*元素个数减1*/ for(i=0;i<n;i+)printf("%d ",fsi);