专升本 2012计算机算法整理.doc

一、 递推算法（常用级数、数列求和、二分法、梯形积分法、穷举法等）1、 常用级数、数列求和例 累加和程序1：应用for循环设计/* for循环求s=1*2+2*3+99*100 */main() long i,s; s=0; for(i=1;i<=99;i+) /* 设置循环i=1,2,99 */ s+=i*(i+1); /* 把通项i*(i+1)累加到s中 */printf("1*2+2*3+.+99*100=%ldn",s); /*此处结果 s 为long，故用 %ld 输出*/输出格式符含义：%d 短整形,一般占两个字节，范围：-3276832767，用于int ，short int%u 无符号短整形，一般占两个字节，范围：065535，用于unsigned int%ld 长整形,一般占四个字节，范围：-21474836482147483647，用于long，long int%c 字符型，用于char%s 字符串，用于char a%f 单精度浮点型，用于float%lf 双精度浮点型，用于double程序2： 应用while循环设计 /* while循环求s=1*2+2*3+99*100 */main() long i,s; i=1;s=0; while(i<=99) /* 设置循环i=1,2,99 */ s+=i*(i+1); /* 把通项i*(i+1)累加到s中 */ i+; printf("1*2+2*3+99*100=%ldn",s);例 代数和/* 求s=1-1/2+1/3-1/4+-1/100 */main() int k,n;float s=0; for(k=1;k<=100;k+) if(k%2=1) s+=1.0/k; /* 应用分支实现符号一正一负 */ else s-=1.0/k; printf("s=%9.6f",s);例 阶乘计算/* 循环累乘求阶乘n! */main()int i,n;long t;scanf("%d",&n); /* 输入 n 的值 */t=1; /* 积变量t赋初值1 */for(i=1;i<=n;i+) t=t*i; /* 循环变量i累乘到t，体现阶乘运算 */printf("%d!=%ldn",n,t);2、 二分法/折半法（只能对有序数列进行查找）基本思想：设n个有序数（从小到大）存放在数组a1-an中，要查找的数为x。用变量min、max、mid 分别表示查找数据范围的底部（数组下界）、顶部（数组的上界）和中间，mid=(max+min)/2，折半查找的算法如下： （1）x=a(mid)，则已找到退出循环，否则进行下面的判断； （2）x<a(mid)，x必定落在min和mid-1的范围之内，即max =mid-1； （3）x>a(mid)，x必定落在mid+1和max的范围之内，即min =mid+1； （4）在确定了新的查找范围后，重复进行以上比较，直到找到或者min <= max。将上面的算法写成如下程序：void main() int a10,mid,min,max,x,i,find; printf("please input the array:n"); for(i=0;i<10;i+) scanf("%d",&ai); printf("please input the number you want find:n"); scanf("%d",&x); printf("n"); min=0; max=9; find=0; /* find用于标记是否找到x */ while(min<=max&&find=0) mid=(max+min)/2; /* 计算中间 */ if(x=amid) find=1; /* 找到 find=1 */ break; /* 跳出循环 */ else if( x < amid ) max=mid-1; else min=mid+1; if (find=1) printf("the number is found the no %dn",mid); else printf("the number is not foundn");3、 梯形积分法(这个你应该能看懂什么意思，我看不明白。呵呵呵！)#include"math.h"main() int i,n=1000; float a,b,h,t1,t2,s,x; printf("请输入积分限a,b:"); scanf("%f,%f",&a,&b); h=(b-a)/n; for(s=0,i=1;i<=n;i+) x=a+(i-1)*h; t1=exp(-x*x/2); t2=exp(-(x+h)*(x+h)/2); s+=(t1+t2)*h/2; /* 梯形面积累加 */ printf("梯形法算得积分值:%f.n",s);其实也不用这么麻烦，比较08年真题，他给出了近似公式，这样就只相当于求级数了。4、 穷举法穷举法是最简单也是最低率的，它是指试用所有可能的情况，如下题解方程：8y+4x+y*y=41 x*x+7y+10=2 (0<x<50, 10<y<100)基本思想是用两个for循环void main() int x,y,find; find=0; for( x=0; x<50; x+ ) for( y=10; y<100; y+ ) if( 8*y + 4*x + y*y = 41&&x*x + 7*y + 10 = 2 ) find=1; printf("x=%dty=%dn",x,y); if(find=0) printf("x,y not exist");二、 排序算法（选择法、冒泡法）1、 选择法排序（升序）基本思想： 1）对有n个数的序列（存放在数组a(n)中），从中选出最小的数，与第1个数交换位置； 2）除第1 个数外，其余n-1个数中选最小的数，与第2个数交换位置； 3）依次类推，选择了n-1次后，这个数列已按升序排列。程序代码如下：/* 输入10个整数，升序排列输出*/main() int i,j,imin,s,a10; printf("input 10 numbers:n"); for(i=0;i<10;i+) scanf("%d",&ai); for(i=0;i<9;i+) imin=i; for(j=i+1;j<10;j+) if(aimin>aj) /* if(aimin<aj) 降序排列*/ imin=j; if(i!=imin) s=ai; ai=aimin; aimin=s; printf("%dn",ai); 2、 冒泡法排序（升序）基本思想：(将相邻两个数比较，小的调到前头) 1）有n个数（存放在数组an中），第一趟将每相邻两个数比较，小的调到前头，经n-1次两两相邻比较后，最大的数已“沉底”，放在最后一个位置，小数上升“浮起”； 2）第二趟对余下的n-1个数（最大的数已“沉底”）按上法比较，经n-2次两两相邻比较后得次大的数； 3）依次类推，n个数共进行n-1趟比较，在第j趟中要进行n-j次两两比较。程序段如下：main() int a10; int i,j,t; printf("input 10 numbers:n"); for(i=0;i<10;i+) scanf("%d",&ai); /* 降序 if(ai<ai+1) */ printf("n"); for(j=0;j<9;j+) for(i=0;i<9-j;i+) if(ai>ai+1) t=ai; ai=ai+1; ai+1=t; printf("the sorted numbers:n"); for(i=0;i<10;i+) printf("%dn",ai);三、 查找算法（顺序查找、折半查找）1、 顺序查找查找是在程序设计中最常用到的算法之一，假定要从n个整数中查找x的值是否存在，最原始的办法是从头到尾逐个查找，这种查找的方法称为顺序查找。程序如下：main() void bi_search(int a,int n,int x); /* 被调函数在main函数之后，需说明被调函数*/ int a100,x,i,n=15; printf("input the numbers:n"); for(i=0;i<n;i+) scanf("%d",&ai); printf("input x:n"); scanf("%d",&x); bi_search(a,n,x);void bi_search(int a,int n,int x) int i=0,find=0; while(i<n) if(x=ai) printf("find:%d,it is a%d",x,i); printf("n"); find=1; i+; if(!find) printf("%d not been found.",x); printf("n");2、 折半查找四、 有序数列的插入、删除操作把一个整数按大小顺序插入已排好序的数组中。 为了把一个数按大小插入已排好序的数组中， 应首先确定排序是从大到小还是从小到大进行的。设排序是从大到小进序的， 则可把欲插入的数与数组中各数逐个比较， 当找到第一个比插入数小的元素i时，该元素之前即为插入位置。然后从数组最后一个元素开始到该元素为止，逐个后移一个单元。最后把插入数赋予元素i即可。如果被插入数比所有的元素值都小则插入最后位置。插入操作程序代码如下：main() int i,j,p,q,s,n,a11=127,3,6,28,54,68,87,105,162,18;/* 先用选择排序法 排列数组 */ for(i=0;i<10;i+) p=i; q=ai; for(j=i+1;j<10;j+) if(q<aj) p=j; q=aj; if(p!=i) s=ai; ai=ap; ap=s; printf("%d ",ai); printf("ninput number:n"); scanf("%d",&n); for(i=0;i<10;i+) if(n>ai) for(s=9;s>=i;s-) as+1=as; /* 移动 ai之后所有元素 */ break; ai=n; /* 插入n 到 ai */ for(i=0;i<=10;i+) printf("%d ",ai); printf("n");删除操作程序代码如下：main() int i,j,p,q,s,n,a11=127,3,6,28,54,68,87,105,162,18; /* 先用选择排序法 排列数组 */ for(i=0;i<10;i+) p=i; q=ai; for(j=i+1;j<10;j+) if(q<aj) p=j; q=aj; if(p!=i) s=ai; ai=ap; ap=s; printf("%d ",ai); printf("ninput number:n"); scanf("%d",&n); for(i=0;i<10;i+) if(n=ai) for(s=i;s<=9;s+) as=as+1; break; for(i=0;i<=9;i+) printf("%d ",ai); printf("n");在一个有序的数列中找到一个数并且删除它main() int a7=0,1,2,3,5,6,i,k,j; for (k=0;k<6;k+) printf("%d ",ak); printf("n"); printf("Please input the number to delete: "); scanf("%d",&i); for (k=0;k<6;k+) if (i=ak) for (j=k;j<5;j+) aj=aj+1; break; if (k=6) printf("The number not found"); printf("The sorted is :n"); for (k=0;k<5;k+) printf("%d ",ak);五、 初等数论问题求解的有关算法（最大数、最小数、最大公约数、最小公倍数、素数等）1、 最大公约数、最小公倍数(递归算法)分析：求最大公约数的算法思想：(最小公倍数=两个整数之积/最大公约数) (1) 对于已知两数m，n，使得m>n； (2) m除以n得余数r； (3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； (4) mn，nr，再重复执行(2)。 例如: 求 m=14 ,n=6 的最大公约数. m n r 14 6 2 6 2 0 void main() int nm,r,n,m,t; printf("please input two numbers:n"); scanf("%d,%d",&m,&n); nm=n*m; if (m<n) t=n; n=m; m=t; r=m%n; while (r!=0) m=n; n=r; r=m%n; printf("最大公约数:%dn",n); printf("最小公倍数:%dn",nm);2、 最大数/* 输入一个数组，输出数组中最大数 */main() int i,a10,max; for ( i=0; i<10; i+ ) scanf ("%d",&ai); max = a0; for ( i=0; i<10; i+ ) if ( max < ai ) max = ai; printf ("output max %d.n", max );3、 最小数/* 输入一个数组，输出数组中最小数 */main() int i,a10,min; for ( i=0; i<10; i+ ) scanf ("%d",&ai); min = a0; for ( i=0; i<10; i+ ) if ( min > ai ) min = ai; printf ("output max %d.n", min );4、 素数只能被1或本身整除的数称为素数基本思想：把m作为被除数，将2 m的平方根 作为除数，如果都除不尽，m就是素数，否则就不是。（可用以下程序段实现）#include "math.h" /*引入数学函数库*/void main() int m,i,k; printf("please input a number:n"); scanf("%d",&m); k=sqrt(m); /*m 开平方*/ for(i=2;i<k;i+) if(m%i=0) break; if(i>=k) printf("该数是素数"); else printf("该数不是素数");掌握判断素数的基本方后，打印出1到X间的素数，1到X间有多少个素数，这样的题也该会做六、 矩阵的处理（生成、交换及基本运算）1、 矩阵的和与转置main() int i,j,m,n,x,y,a45,b45; printf("输入a矩阵:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) scanf("%d",&aij); /* 输入a矩阵的元素 */ printf("输入b矩阵:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) scanf("%d",&bij); /* 输入b矩阵的元素 */ printf("a矩阵:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) printf("%3d",aij); /* 打印a矩阵 */ printf("n"); printf("b矩阵:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) printf("%3d",bij); /* 打印b矩阵 */ printf("n"); printf("a,b矩阵之和:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) printf("%4d",aij+bij); /* 计算并打印a+b的元素 */ printf("n"); printf("a矩阵的转置:n "); for(j=1;j<=4;j+) /* 打印a矩阵的转置 */ for(i=1;i<=3;i+) printf("%4d",aij); printf("n"); 小知识：%md; m为指定的输出字段的宽度。如果数据的位数小于m,则左端补以空格，若大于m，则按实际位数输出。例如a=123,b=12345,printf("%4d,%4d",a,b);结果是：_123，12345 _代表空格。2、 矩阵的积求a,b矩阵的积前提是我们要在数学上会矩阵的积main() int i,j,k,d,a45,b53; printf("输入a矩阵:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) scanf("%d",&aij); /* 输入a矩阵的元素 */ printf("输入b矩阵:n "); for(i=1;i<=4;i+) for(j=1;j<=2;j+) scanf("%d",&bij); /* 输入b矩阵的元素 */ printf("a矩阵:n "); for(i=1;i<=3;i+) for(j=1;j<=4;j+) printf("%3d",aij); /* 打印a矩阵 */ printf("n"); printf("b矩阵:n "); for(i=1;i<=4;i+) for(j=1;j<=2;j+) printf("%3d",bij); /* 打印b矩阵 */ printf("n"); printf("a,b矩阵之积:n "); for(i=1;i<=3;i+) for(j=1;j<=2;j+) d=0; for(k=1;k<=4;k+) d+=aik*bkj; /* 求和计算积矩阵元素d(i,j) */ printf("%6d",d); /* 打印a,b积矩阵元素d */ printf("n"); 七、 递归算法（阶乘、最大公约数等）1、 阶乘模块化机制及函数（过程）设计与使用如子程序、函数、过程、类等用子程序的方式可以做复杂些的关于阶乘级数和的程序。/* 用递归求阶乘n! */main()float fac(); /* 申明函数 */int n;long y;printf("input n:");scanf("%d",&n);y=fac(n);printf("%d!=%ldn",n,y);float fac(n)int n; /* 说明参数类型 */long f;if(n=0)f=1; /* 初始条件，退出递归 */elsef=n*fac(n-1); /* 递归关系 */return (f);C语言中又规定在以下几种情况时可以省去主调函数中对被调函数的函数说明。1) 如果被调函数的返回值是整型或字符型时，可以不对被调函数作说明，而直接调用。这时系统将自动对被调函数返回值按整型处理。2) 当被调函数的函数定义出现在主调函数之前时，在主调函数中也可以不对被调函数再作说明而直接调用。3) 如在所有函数定义之前，在函数外预先说明了各个函数的类型，则在以后的各主调函数中，可不再对被调函数作说明。例如： float f(float b); main() . float f(float a) 其中第一行对f函数预先作了说明。因此在以后各函数中无须对f函数再作说明就可直接调用。4) 对库函数的调用不需要再作说明，但必须把该函数的头文件用include命令包含在源文件前部。2、 最大公约数int divisor(int n,int m) if(n%m=0) return(m); else return(divisor(m,n%m);void main() int n,m,t; printf("please input n:n");scanf("%d",&n); printf("please input m:n");scanf("%d",&m); if (m<n) t=n; n=m; m=t; printf("最大公约数:%dn ",divisor(n,m);八、 字符串处理（插入、删除、连接和比较等）1、 插入2、 删除3、 连接4、 比较15