重庆普通高校专升本计算机算法整理

1、一、 递推算法（常用级数、数列求和、二分法、梯形积分法、穷举法等）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

2、 ，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

3、*(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); /

4、* 输入 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必定落在

5、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 th

6、e 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 (fi

7、nd=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; fo

8、r(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() i

9、nt 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 个数

10、外，其余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(

11、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; prin

12、tf("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)

13、;三、 查找算法（顺序查找、折半查找）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

14、"); 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、 折半查找四、 有序数列的插入、删

15、除操作把一个整数按大小顺序插入已排好序的数组中。 为了把一个数按大小插入已排好序的数组中， 应首先确定排序是从大到小还是从小到大进行的。设排序是从大到小进序的， 则可把欲插入的数与数组中各数逐个比较， 当找到第一个比插入数小的元素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;

16、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&

17、lt;=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("ninpu

18、t 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&q

19、uot;); 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);五、 初

20、等数论问题求解的有关算法（最大数、最小数、最大公约数、最小公倍数、素数等）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&quo

21、t;); 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; f

22、or ( 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"

23、;, 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(&

24、quot;该数是素数"); 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 ")

25、; 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(&quo

26、t;%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("%4

27、d",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("

28、;%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矩

29、阵: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、 阶乘模块化机制及函数（过程）设计与使用如子程序、函数、过程、类