《2009年重庆普通高校专升本计算机算法整理》由会员分享，可在线阅读，更多相关《2009年重庆普通高校专升本计算机算法整理（15页珍藏版）》请在金锄头文库上搜索。
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 ，short int%u 无符
2、号短整形，一般占两个字节，范围：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+; p
3、rintf(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累乘
4、到t，体现阶乘运算 */printf(%d!=%ldn,n,t);2、 二分法/折半法（只能对有序数列进行查找）基本思想：设n个有序数（从小到大）存放在数组a1-an中，要查找的数为x。用变量min、max、mid 分别表示查找数据范围的底部（数组下界）、顶部（数组的上界）和中间，mid=(max+min)/2，折半查找的算法如下： （1）x=a(mid)，则已找到退出循环，否则进行下面的判断； （2）xa(mid)，x必定落在mid+1和max的范围之内，即min =mid+1； （4）在确定了新的查找范围后，重复进行以上比较，直到找到或者min = max。将上面的算法写成如下程序：voi
5、d main() int a10,mid,min,max,x,i,find; printf(please input the array:n); for(i=0;i10;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=
6、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、 梯形积分法(这个你应该能看懂什么意思，我看不明白。呵呵呵！)#includemath.hmain() int i,n=1000; float a,b,h,t1,t2,s,x; printf(请输入积分限a,b:); scanf(%f,%f,&a,&b); h=(b-a)
7、/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 (0x50, 10y100)基本思想是用两个for循环void main() int x,y,find; find=0; for(
8、x=0; x50; x+ ) for( y=10; y100; 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次后，这个数列已按升序排列。程序代码如下：/* 输入1
9、0个整数，升序排列输出*/main() int i,j,imin,s,a10; printf(input 10 numbers:n); for(i=0;i10;i+) scanf(%d,&ai); for(i=0;i9;i+) imin=i; for(j=i+1;jaj) /* if(aiminaj) 降序排列*/ imin=j; if(i!=imin) s=ai; ai=aimin; aimin=s; printf(%dn,ai); 2、 冒泡法排序（升序）基本思想：(将相邻两个数比较，小的调到前头) 1）有n个数（存放在数组an中），第一趟将每相邻两个数比较，小的调到前头，经n-1次两两相
10、邻比较后，最大的数已“沉底”，放在最后一个位置，小数上升“浮起”； 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;i10;i+) scanf(%d,&ai); /* 降序 if(aiai+1) */ printf(n); for(j=0;j9;j+) for(i=0;iai+1) t=ai; ai=ai+1; ai+1=t; pri
11、ntf(the sorted numbers:n); for(i=0;i10;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;in;i+) scanf(%d,&ai); printf(input x:n); scanf(%d,&x); bi_search(a,n,x);void
