计算机程序设计常用算法归纳.pdf

1 《计算机程序设计》中常用算法复习 一、常用算法有 8 个方面： 1、递推算法（级数、数列求和、二分法、梯形法、穷举法 等） 2、排序算法（选择法排序、冒泡法） 3、查找算法（顺序查找 、折半查找、统计、求和、计数） 4、有序数列的插入、删除操作 5、求解算法（最大数、最小数、素数、最大公约数、最小 公倍数） 6、矩阵的处理（生成矩阵、交换和基本运算） 7、递归算法（求阶乘、最大公约数） 8、字符串处理（插入、删除、连接和比较） 二、常用算法的应用举例：（有 21 个程序） 1、计算 S=1+2+…+100 的值。（求和、统计） 2、找出 100~999 之间的所有"水仙花数"（穷举法、统计） 3、从键盘输入 10 个数，然后找出其中的最大值和最小值。 （找最大数、最小数） 4、任意输入 n 个数，按由小到大的顺序排列并显示输出。 （排序算法--选择法排序） 5、（对字符串排序处理）有 5 个英文单词，分别为：Word， Excel，Powerpoint，Type，Angle，要求设计出如下程序： 2 （1）在键盘上输入数 N（本例输入 5），把英文单词放 入名为 X 大小为 N 的数组中 （2）显示出 X 数组中的英文单词 （3）对数组中的英文单词从小到大排序 （4）显示出排序后 X 数组中英文单词 6、求 5 的阶乘值（5!=？） 7、计算 t=1!+2!+……+10! （即求阶乘之和）。 计算 t=1!+2!+……+10! 即求阶乘之和（双循环）。 8、多项式 S=1+2+22+23+……+232，请设计一个程序，求 S 的 值。 9、除了 1 和它本身之外不能被任何一个整数所整除的自然 数叫质数，除去 2 之外，其它质数都是奇数，又称为素数。 请设计一个程序，在屏幕上输出 3——150 之间的所有素数。 10、设计 1 个程序，要求是：（查找算法、统计、求和、找 素数或质数） (1)在键盘上输入 1 个不小于 3 的自然数 N （例输入 10） ， 求出其不到第 N 个自然数中奇数之和，并输出结果 (2)输出 1 到第 N 自然数中所有质数的个数 11、穷举法，整钱找零.prg 程序如下： *（1）穷举法整钱找零.prg"、 *整钱找零：100=x1*10+x2*5+x3*1 3 *x1,x2,x3>=1,x1+x2+x3=20 for x1=1 to 10 for x2=1 to 20 x3=20-x1-x2 if 100=x1*10+x2*5+x3*1 and x3>0 then ?x1,x2,x3 endif next x2 next x1 12、求级数.prg 程序如下： *求级数 1.prg" *s=1+1/2-1/3+1/4+.... s=1 d=1 clear input "输入 N："to n for i=2 to n s=s+d*1/i d=-d ?S 4 next i ?"s=",s 13、求数列.prg 程序如下： *求数列 2.prg" fibnocsi 数列 f1=1 f2=1 ??f1,f2 for i=1 to 20 f2=f2+f1 f1=f2-f1 ??f2 next i 14、生成矩阵.prg 程序如下： *（4）生成矩阵.prg" clear dime a(5,5) for i=1 to 5 for j=1 to 5 do case 5 case i<j a(i,j)=2 case i=j a(i,j)=1 otherwise a(i,j)=3 endcase next j next i for i=1 to 5 for j=1 to 5 ?? a(i,j) next j ? next i 15、查找算法（顺序查找.prg） 程序如下： *（1）顺序查找.prg" clear dime a(10) for i=1 to 10 a(i)=int(rand()*100) 6 ??a(i) next i input "输入要查找的数：" to x for i=1 to 10 if a(i)=x ?"找到：",x,i return endif next i ?"没有找到！" 16、查找算法（折半查找.prg"） 程序如下： *（2） 折半查找.prg"（先排序，后查找） clear dime a(10) n=10 for i=1 to 10 a(i)=int(rand()*100) ??a(i) next *排序 for k=1 to n-1 7 for j=k+1 to n if a(k)>a(j) t=a(k) a(k)=a(j) a(j)=t endif endfor ? a(k) endfor ?a(n) return *折半查找 input "输入要查找的数："to x l=1