C复习讲稿程序设计部分.pptVIP

【例5】用递归函数法求下列表达式的值。 　　Px(x,n)=x-x2+x3-x4+…(-1)n-1xn (n0) 　　　　=x*(1-Px(x,n-1)) 　　函数的递归模型如下： 　　　Px(x,n)=x 当n=1 　　　Px(x,n)=x*(1-Px(x,n-1)) 当n1 【例6】已知计算组合的公式如下： 函数的递归模型如下： 【例7】以下函数P的功能是用递方法计算x的n阶勒 让德多项式的值。 函数递归公式如下： Px(x)=1 当n=0 Px(x)=x 当n=1 Px(x)=((2n-1)*x*Pn-1(x)-(n-1)*Pn-2(x))/n 当n1 【例8】用递归法将一个整数n转换成字符串，例如 输入483,应输出字符串“483”,n的位数不确定，可 以是任意位数的整数。 　　重点理解：穷举法也称为枚举法，它是算法 设计中最常用的方法之一，其基本思想是：不重 复、不遗漏地穷举所有的可能情况，以便从中寻 找满足条件的结果。 【专题五】关于穷举法的问题 穷举法编程方法： 　　在用穷举法编程时，主要是使用循环语句和选 择语句，循环语句用于穷举所有可能的情况，而选 择语句则用于判定当前的条件是否为所求的解，其 基本格式如下： for(循环变量x取所有可能的值) { if(x满足指定的条件) 输出x; } 【例1】一个数如果恰好等于它的因子之和（不包 括本身），这个数就称为“完数”。编程找出1000 以内的所有“完数”，并输出出来。 【例2】如果一个正整数等其各个数字的立方和， 则该数称为阿姆斯特朗数。试编程求出1000以 内的所有阿姆斯特朗数。 【例3】如果一数只能被1和它本身整除，那么该 称为素数，试编程求出1000以内的所有素数。 【例4】试编程序，找出1到99之间的全部同构数。 同构数是这样一组数；它出现在平方数的右边。例： 5是25右边的数，25是625右边的数，5和25都是 同构数。 * * 【附 言】 关于程序编写题，总共统计起来有以下8个大类： 　　 1、数组排序问题 　　２、数据查找问题 　　３、矩阵问题 　　４、函数递归调用 　　５、穷举法应用 　　６、数值拆分法解题 　　７、字符及字符串相关处理问题 　　８、关于结构体的应用：链表与二叉树的问题 　　所谓排序是指将一个无序的数据序列按照某种 排列顺序重新排列起来。在Ｃ语言程序设计中，常 用的排序有冒泡排序和选择排序两种方法，也是要 求大家必须掌握并且能够熟练运用的。 【专题一】关于排序问题 　　冒泡排序的基本思想：设想被排序的数 组R[0..n]（表示从R[0]到R[n-1]之间的所有元 素不同）垂直竖立，将每个元素R[i]看作是重 量为R[i]的气泡。根据轻气泡不能在重气泡之 下的原则，从下往上扫描数组R，凡扫描到违 反本原则的气泡，就使其向上“飘浮”，如此反 复，直到任何两个气泡都是轻者在上，重者在 下为止。 １、冒泡排序 main() { int a[10]={2,1,5,3,4,6,7,9,8,10},i,j,temp; for(i=0;i9; i++) for(j=0; j9-i; j++) if(a[j]a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } for(i=0; i10; i++) printf(“%d ”,a[i]); } 说明：双重循环中，外循环控制循环的趟数， 　内循环控制每趟中相邻两个数据元素 　　　比较的次数。 　　直接选择排序的基本思想：第i趟排序开始时， 当前的有序区和无序区分别为R[0..i-1]和R[i..n-1] （1≤i≤n-2），该趟排序则是从当前无序区中选出 最小的元素R[k]，将它与无序区的第1个元素R[i]交 换，使R[0..i]和R[i+1..n-1]分别变为新的有序区和 新的无序区。因为每趟排序均使有序区中增加了一个 元素，且有序区中的元素均不大于无序区中的元素， 即第i趟排序之后，R[0..i]≤R[i+1..n-1]，所以进行 n-1趟排序之后有R[0..n-2]≤R[n-1]，也就是说， 经过n-1趟排序之后，整个数组递增有序。 ２、直接选择排序 main() {　int a[10]={2,1,5,3,4,6,7,9,8,10},i,j,k,temp; for(i=0;i9; i++) {