计算机程序设计常用算法归纳.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 计算机程序设计中，算法是解决问题的关键，而这些算法在日常编程任务中经常被用到。以下是对描述中提到的常用算法的详细解释： 1. **递推算法**：递推算法通常涉及通过先前的值来计算当前值。例如，级数求和、数列求和（如等差数列或等比数列）、二分法、梯形法（用于数值积分）和穷举法（用于遍历所有可能情况）。例如，计算1到100的和可以用递推公式S = S + n进行。 2. **排序算法**：包括选择法排序（例如，找出最小元素并放到正确位置，重复此过程）和冒泡法（相邻元素比较，交换位置直到序列稳定）。描述中的示例要求将输入的n个数字按照升序排列。 3. **查找算法**：有顺序查找（线性遍历数组直至找到目标元素）和折半查找（先对数组排序，然后每次比较中间元素，根据比较结果缩小查找范围）。例如，输入一个数x，查找它在已排序数组中的位置。 4. **有序数列的插入和删除**：在已排序的数列中插入新元素或删除特定元素，通常需要维护数列的排序顺序。 5. **求解算法**：这类算法用于解决特定问题，如找出最大数、最小数、素数、最大公约数（GCD）和最小公倍数（LCM）。例如，找出100到999之间的所有“水仙花数”（每个位上的数字的立方和等于原数的三位数）。 6. **矩阵处理**：包括生成矩阵、矩阵的交换以及基本运算（如加减乘）。例如，生成5x5的矩阵，并执行特定条件的赋值。 7. **递归算法**：函数调用自身的方式。在描述中，用于求阶乘和最大公约数。例如，5的阶乘可以通过5 * 4!计算，4!再通过4 * 3!计算，以此类推，直到递归到1为止。 8. **字符串处理**：包括字符串的插入、删除、连接和比较。比如，对一组英文单词进行排序。 以上算法在实际编程中有着广泛的应用，例如，递推算法可以用于计算复杂数列，排序算法用于数据组织，查找算法在数据库查询中至关重要，矩阵处理在科学计算中常见，而递归算法则在解决复杂结构问题时非常有用。通过掌握这些算法，程序员能够更有效地解决问题并优化代码性能。