1、C程序设计技术复习要点 一基本概念部分一基本概念部分 C语言的基本概念（数据类型，常量，变量，语言的基本概念（数据类型，常量，变量，表达式的书写方法等）表达式的书写方法等）当两个整数相除时，得到的结果仍然是整数。既取整运算。例如：7/5结果为1，-7/5结果为-1，3/5结果为0.求模运算就是求余数，参加求模运算的两个对象必须都是整型对象，运算结果的符号与第一个运算对象相同。例如：7%5结果为2，-7%5结果为-2，7%（-5）=2。优先级高()函数 +、-*、/、%+、-优先级低 典型运算符的使用（典型运算符的使用（+，-，复合赋值等），复合赋值等）复合赋值符：凡是双目运算符都可以与赋值运算
2、符一起组成复合赋值符，其结合性为右结合性。这些复合赋值符共有10个，它们是：+=、-=、*=、/=、%=、=、&=、=、|=+i、-i。自增、自减运算符的前缀形式对变量实施的运算是“先增/减值后引用”。i+、i-。自增、自减运算符的后缀形式对变量实施的运算是”先引用后增/减值”。例1-9 自增、自减运算符使用示例。例1-14 表达式混合运算中的 自动数据类型转换示例。例1-15 表达式混合运算中的强制数据类型转换示例。高 double floatlongunsigned 低 int short,char图1.4 系统自动数据类型转换规则 关系运算和逻辑运算关系运算和逻辑运算在在C C程序设计语
3、言中没有逻辑数据类型，所以在进行关系运算时程序设计语言中没有逻辑数据类型，所以在进行关系运算时:用数值用数值“1 1”表示逻辑概念上的表示逻辑概念上的“真真”，用数值用数值“0 0”表示逻辑概念上表示逻辑概念上的的“假假”;例如：例如：5=55=5/*结果为结果为1 1*/10=10 10=10/*结果为结果为1 1*/5 5！=5=5/*结果为结果为0 0*/53 53/*结果为结果为1 1*/35 35/*结果为结果为0 0*/例例2-12-1 关系运算示例。关系运算示例。该程序运行执行语句该程序运行执行语句c=5-1=a+2=a+2=a+2=a+2=和和=结合，即先计算表达式结合，即先计
4、算表达式5-1=a+25-1=a+2得到结果得到结果0 0，然后计算表达式然后计算表达式0=b-210=b-21的结果也为的结果也为0 0，最后将该，最后将该0 0值赋值给变量值赋值给变量c c。所以，该程序运行的输出结果为：所以，该程序运行的输出结果为：c=0c=0 对逻辑表达式从左到右扫描求解；对逻辑表达式从左到右扫描求解；在逻辑表达式的求解过程中，在逻辑表达式的求解过程中，任何时候只要逻辑任何时候只要逻辑 表达式的值已经可以确定表达式的值已经可以确定，则求解过程不再进行。，则求解过程不再进行。例如有定义：例如有定义：intint a=1,b=2,c=0;a=1,b=2,c=0;，则逻辑表
5、达式，则逻辑表达式a+|b+&ca+|b+&c+的的计算过程得到结论为：计算过程得到结论为：逻辑表达式的值为逻辑表达式的值为1 1、变量、变量a a的值为的值为2 2、变量、变量b b的值为的值为2 2（原值）、变量（原值）、变量c c的值为的值为0 0（原值）。（原值）。例例2-32-3 关系表达式运算和逻辑表达式运算示例关系表达式运算和逻辑表达式运算示例 。例例2-22-2 逻辑表达式运算示例逻辑表达式运算示例 。基本控制结构（基本控制结构（特别注意特别注意+，-运算符进入运算符进入条件表达式条件表达式）流程控制语句 条件语句ifelse循环语句 for语句、while语句、dowhile
6、语句提前结束本次循环语句continue循环或多分支终止语句break无条件转移语句goto返回语句return 复合表达式语句 C语言允许把一组语句括在花括号之中构成一个语句块，称之为复合语句。例如 char ch;ch=getchar();putchar(ch);要特别注意各控制结构的流程要特别注意各控制结构的流程2.2.6 switch2.2.6 switch语句与程序的多分支结构语句与程序的多分支结构switch（expession）case constand1:sentences1;break;case constand2:sentences2;break;case constand
7、N:sentencesN;break;default：sentencesN+12 2）执行过程：）执行过程：首先，首先，对作为条件的表达式（对作为条件的表达式（expressionexpression）求值；）求值；然后，然后，在语句结构的花括号内在语句结构的花括号内从上至下从上至下查找所有的查找所有的casecase分支，当找到与条件表分支，当找到与条件表达式值相匹配的达式值相匹配的casecase时，将其作为控制流程执行的入口，并时，将其作为控制流程执行的入口，并从此处开始执行相从此处开始执行相应的语句段，直到遇到应的语句段，直到遇到breakbreak语句或者是语句或者是switchsw
8、itch语句结构的右花括号语句结构的右花括号“”为止。为止。switch(number)case 1:statement1;case 2：statement2;case 3:statement3;default:statement4;statement5;?2 习题：P84页，一、6.For(i=1;i+4;);后，循环控制变量i的值是？要特别注意该题，分析该题；理解该题的考要特别注意该题，分析该题；理解该题的考点！点！特别注意特别注意+，-运算符进入条件表达式！运算符进入条件表达式！数组的定义和数组元素的访问数组的定义和数组元素的访问 例3-3 用数组存放一组统计数据，然后用“*”表示的条形
9、图输出这组数据。程序输出效果如下所示：Element Value Striation 1 11 *2 3 *3 7 *4 10 *5 20 *例3-4 打印如下所示的杨辉三角形的前10行（要求使用一维数组处理）例3-5 在二维数组a34中依次选出各行最大元素值存入一维数组b3对应元素中。程序运行结果：array a:3 16 87 65 4 32 11 108 10 25 12 27 array b:87 108 273.3.2 常用排序方法3.3.3 常用查找方法 例3-9 编程序实现冒泡排序算法，对随机生成的20个整数按升序进行排序并输出。上面程序中用变量flag作为标志，每一趟排序开始时
10、将其设置为0，当本趟排序过程中有数据交换时将flag设置为1，表示数据还没有排序完成；当本趟排序过程中没有一次数据交换时，flag保持为0值，表示被排序的数据已经完全满足排序的要求，没有必要再继续进行以后的排序过程，程序中用break语句退出排序循环。程序的一次执行结果为：Before sorting.293 31 365 849 867 166 487 826 487 775 331 630 294 5 242 136 953 123 849 65 After sorting.5 31 65 123 136 166 242 293 294 331 365 487 487 630 775 82
11、6 849 849 867 953 例3-10 编程序实现选择排序算法，对随机生成的20个整数按升序进行排序并输出。程序的一次运行结果为：Before sorting.341 74 545 498 809 626 913 433 567 560 130 479 505 95 96 143 851 634 830 665 After sorting.74 95 96 130 143 341 433 479 498 505 545 560 567 626 634 665 809 830 851 913 1顺序查找（Linear search）顺序查找又称为线性查找。其基本过程是：从待查表中的第一个
12、记录开始，将给定的关键字值与表中每一个记录的关键字值逐个进行比较。如果找到相符合的记录时，查找成功，如果查找到标得末端都未找到相符合的记录时，查找失败。顺序查找法适应于被查找集合无序的场合。例3-11 编程序实现顺序查找算法，在随机生成的20个整数中查找指定值，要求程序能够显示出查找进行比较的次数以及本次查找成功与否。程序的一次运行结果为：请输入被查找的整数值:43 被查找数据集合如下.15 5 70 43 64 17 10 4 58 96 39 51 5 51 67 0 49 56 12 12 查找43成功，共进行了4次比较。例3-12 编程序实现折半查找算法，在随机生成的20个整数中查找指
13、定值，要求程序能够显示出查找进行比较的次数以及本次查找成功与否。程序中首先输出随机产生、未经排序的查找数据集合，执行结果中用数组元素形式显示出来的是排序后与查找关键字key值相同的元素。程序的一次执行结果如下所示：下面是未排序的查找数据集合.41 28 91 83 86 62 96 93 41 57 79 47 12 94 36 34 56 36 2 97 请输入被查找的关键字值:91 查找a15成功，共进行了4次比较。函数的定义，声明和调用函数的定义，声明和调用 C程序的一般结构 C程序源文件1源文件i源文件n函数1预处理语句函数m说明/定义部分执行语句部分图4.1 C程序的一般结构宏代换（
14、不带参，带参）宏代换（不带参，带参）宏定义分为代参数的宏定义和不代参数的宏定义两种。1不代参数的宏定义 不代参数的宏定义编译预处理语句的一般形式是：#define 宏标识符 字符串 宏调用的格式为：宏标识符 宏调用的作用是：在宏定义的作用范围之内，将所有的宏标识符用指定的字符串替换。式中，宏标识符也称为宏名或常量标识符，习惯上使用大写字母书写。在C程序的设计中，正确地理解宏定义的关键在于理解宏调用仅仅就是一个替换而不会进行任何的合并、计算等等操作。在阅读理解包含宏调用问题的C程序时一定要做到先将宏替换完成、然后操作宏替换完成后的表达式 例4.25 宏调用替换问题的理解示例。/*Name:ex0
15、4-25.cpp*/#include#define N 2#define M N+2#define MN 2*M void main()int x=MN;printf(x=%dn,x);错误的理解方式是：错误的理解方式是：N2N2、M4M4（2+22+2）、）、MN8MN8（2 2*4 4），从），从而认为上面程序的而认为上面程序的输出结果是输出结果是x=8x=8。正确理解的方式应正确理解的方式应为：为：MN2MN2*N+2N+2、MN2MN2*2+22+2，因而程，因而程序执行的正确结果：序执行的正确结果：x=6x=6。带参数的宏定义 在C程序设计过程中如果有需要，也可以使用带参数的宏定义。
16、定义代参数的宏定义的一般形式如下：#define 宏标识符(形参表)表达式样式字符串宏调用的格式为：宏标识符（实参表）宏调用的作用是：在宏定义的作用范围之内，将所有的宏标识符用指定的表达式样式字符串替换，然后用宏调用中的实际参数代替通过替换形成的表达式中的形式参数。在程序设计中使用带参数宏定义时，为了避免当实际参数本身是表达式时引起的宏调用错误，在定义代参数的宏定义时最好将宏定义中表达式的形式参数用括号括起来，下面的例4.26展示了这方面的问题。例4.26 代参数宏定义使用示例（不能正确处理表达式样式实际参数）。/*Name:ex04-26.cpp*/#include#define PI 3.
17、145926#define S(r)PI*r*rvoid main()double a,b,area1,area2;a=3.3;b=3.2;area1=S(a);area2=S(a+b);printf(area1=%fnarea2=%fn,area1,area2);例4.27 宏调用替换问题的理解示例。/*Name:ex04-27.cpp*/#include#define Min(x,y)(x)=1n%=0fp=f1fp=f2使用(*fp)调用函数结束输入n值输出结果值输出数据错误信息结合结合”关于指针的复习关于指针的复习PPT”复习复习求解高阶方程的根在对高阶方程的讨论中知道，高阶方程都是类
18、似的，其形式可以用f(x)=0来表示，也就是说被求根的函数用C语言都可表示成为如下所示结构C函数：double f(double x)因而指向被求根函数的指针变量的一般形式为：double (*fp)(double x);对于使用牛顿迭代法的通用求根函数而言，在函数的参数表中应该包含三个形式参数：一个是求根时指定的根的初始值，另外两个是用于接受外界传递进来的函数实参以及导函数实参的指向函数的指针变量。例5-2 二分法求高阶方程根的通用函数。例5-3 利用已有的通用函数按给定条件求下面高阶方程的根。指向函数的指针与函数型参数的实现 被积函数的形式均为有一个实型自变量且所积结果是实型数据，所以在求
19、定积分的通用函数的返回值数据类型应为double，通用函数的参数有下面四个：与被积函数对应的指向函数的指针：double(*p)(float x)积分区间的下限：float a 积分区间的上限：float b 按精度所需的积分区间等分数：int n 函数与指针 返回指针值的函数例例5-65-6#include long*fac(long nvoid main()long n,i,sum=0,*pi;printf(Input n:);for(i=1;i=n;i+)sum+=*fac(i);scanf(%ld,&n);for(i=1;i=n;i+)pi=fac(isum=sum+*pi;print
20、f(Sun=%ldn,sum long*fac(long n)/函数的定义static long p=1;p*=n;return&p;用指针引用数组元素的方式用指针引用数组元素的方式结合结合“关于指针复习关于指针复习.ppt”复习！复习！二重点知识点二重点知识点 整型数据的拆分以及特定数码的统计整型数据的拆分以及特定数码的统计注意模运算及如何提取一个注意模运算及如何提取一个整型数据的每一位整型数据的每一位 字符串的常见操作（字符串的常见操作（在字符串中删除指定在字符串中删除指定字符，统计字符串中的特定字符功能的实字符，统计字符串中的特定字符功能的实现现）在字符串中删除指定的字符在字符串中删除指
21、定的字符 在字符串中删除指定字符操作的基本思想是：首先在字符串中查找在字符串中删除指定字符操作的基本思想是：首先在字符串中查找指定字符的位置，若找到则将字符串中自该位置以后所有字符依次向指定字符的位置，若找到则将字符串中自该位置以后所有字符依次向前移动一个字符位置即可。前移动一个字符位置即可。例例7-187-18 函数原型为：函数原型为：void void deletechr(chardeletechr(char s,char c);s,char c);，其功能是，其功能是在字符串中删除指定字符，若指定字符不存在则显示相应提示信息。在字符串中删除指定字符，若指定字符不存在则显示相应提示信息。请
22、编制该函数并用相应主函数进行测试。请编制该函数并用相应主函数进行测试。字符串中字符的查找 所谓字符串中字符的查找就是按照指定的方向寻找指定字符第一次在字符串中出现的位置。在字符串中查找指定的字符从查找方向上可以分为正向查找（从串首部至串尾）和反向查找（从串尾部至串首），从获取被查找字符位置信息上可以分为返回下标序号方式和返回字符存放地址方式。统计字符串中的特定字符的个数时，需要先查找到特定字符，然统计字符串中的特定字符的个数时，需要先查找到特定字符，然后计数后计数 字符串中正向查找指定字符 在字符串中正向查找指定字符第一次出现位置的基本思想是：从被操作字符串的第一个字符开始循环依次取出被操作字
23、符串当前位置的字符与指定的字符相比较，若比较相符合则返回该字符的位置；否则进行下一轮比较直到被处理的字符串中所有字符取完为止。例7-13 编制函数实现功能：在字符串中正向查找指定的字符，若被查找字符存在则返回字符在字符串中的下标序号；若指定的字符在被查找的字符串中不存在，则返回-1；并用相应主函数进行测试。例7-14 编程序实现功能：利用上面设计的字符查找函数求两个字符串中共同具有的字符并将这些字符组成第三个字符串，注意相同字符只能取一次。例7-15 重写例7.14程序，要求使用标准库函数strchr在字符串中查找指定字符。字符串中反向查找指定字符 在字符串中反向查找指定字符第一次出现位置的基
24、本思想是：从被操作字符串的最后一个字符开始循环依次取出被操作字符串当前位置的字符与指定的字符相比较，若比较相符合则返回该字符的位置；否则进行下一轮比较直到被处理的字符串中所有字符取完为止。例7-16 编制函数实现功能：在字符串中反向查找指定的字符，若被查找字符存在则返回字符在字符串中的下标序号；若指定的字符在被查找的字符串中不存在，则返回-1；并用相应主函数进行测试。函数的指针参数（利用指针参数返回多个函数的指针参数（利用指针参数返回多个值）值）结合结合”关于指针复习关于指针复习.ppt”复习复习 数组的定义，初始化，数组元素的引用；数组的定义，初始化，数组元素的引用；数组做函数的参数使用方法
25、数组做函数的参数使用方法 在C程序设计中，既可以用数组的元素作为函数的参数，也可以将数组看成一个整体作为函数的参数。使用数组元素作为参数传递，其用法都与普通变量用法一样，实现的是函数间的传值调用。/*Name:ex04-07.cpp*/#include#include#include#define N 5void main()void myprint(int x);int aN,bNN,i,j;srand(time(NULL);printf(下面是数组下面是数组a的数的数据据.n);for(i=0;iN;i+)ai=rand()%100;myprint(ai);将数组看成一个整体作为函数参数时
26、，用将数组看成一个整体作为函数参数时，用数组名作为函数的形式参数或实际参数，实数组名作为函数的形式参数或实际参数，实现的是函数间的传地址值调用，下面分别讨现的是函数间的传地址值调用，下面分别讨论一维数组和二维数组作为函数参数的问题。论一维数组和二维数组作为函数参数的问题。数组参数传递函数调用 1一维数组名作为函数参数实现的是“传地址值调用”，其本质是将它的全部存储区域或者部分存储区域提供给形式参数数组共享，即形参数组与实参数组是同一存储区域或者形参数组是实参数组存储区域的一部分。存储关系如下图：实参数组a形参数组b注：形参数组b本质上是指针变量图4.6 数组存储区域全部共享时形参数组与实参数组
27、的关系 需要把实参数组中从某个元素值后的部分传递给被调函数中的形参数组，则使用实参数组某个元素的地址（参见4.7）。实参数组&a2形参数组b注：形参数组b本质上是指针变量图4.7 数组存储区域部分共享时形参数组与实参数组的关系例4.8 编制求和函数并通过该函数求数组的元素值和。例4.9 编制求和函数并通过该函数求数组自某一元素后的所有元素值和，起始点元素序号从键盘上输入。/*Name:ex04-09.cpp*/#include#define N 10void main()int sum(int v,int n);int aN=1,2,3,4,5,6,7,8,9,10,total,pos;pri
28、ntf(请输入求和起始元素序号:);scanf(%d,&pos);total=sum(&apos,N-pos);printf(total=%ldn,total);int sum(int v,int n)int i,s=0;for(i=0;in;i+)s+=vi;return s;比较例4.8和例4.9的程序，可以发现函数sum没有任何改变，程序中有所改变的是主调函数中的调用表达式：sum(&apos,N-pos)，其中，参数&apos表示将数组a自apos元素以后的元素全部提供给形参数组共享，N-pos是传递到函数add中共享的数组元素个数。2二维数组作函数的参数数组a的起始地址数组的起始地址
29、表示方法a 表示平面的起始地址（二级地址）&a00 表示线性的起始地址（一级地址）a0 表示线性的起始地址（一级地址）*a 表示线性的起始地址（一级地址）图4.8 二维数组起始地址的表示方法示意 二维数组在存储时也是有序地占用一片连续的内存区二维数组在存储时也是有序地占用一片连续的内存区域，数组的名字表示这段存储区域的首地址。需要特别注域，数组的名字表示这段存储区域的首地址。需要特别注意的是，二维数组起始地址有多种表示方法，而且这些表意的是，二维数组起始地址有多种表示方法，而且这些表示方法在物理含义上还有表示平面起始地址和表示线性起示方法在物理含义上还有表示平面起始地址和表示线性起始地址之分，
30、所以在使用二维数组的起始地址使必须注意始地址之分，所以在使用二维数组的起始地址使必须注意区分需要用哪一种起始地址。区分需要用哪一种起始地址。例4.10编制求二维矩阵最大元素的函数（假定矩阵为3行4列），用相应主函数进行测试。/*Name:ex04-10.cpp*/#include#define M 3#define N 4void main()int max(int vN);int aMN=38,23,56,9,56,2,789,45,76,7,45,34;printf(Max value is:%dn,max(a);intint max(intmax(int vNvN)/注意数组注意数组参数
31、只能省略最高为的长度指定参数只能省略最高为的长度指定 intint i,j,maxvi,j,maxv;maxvmaxv=v00;=v00;for(ifor(i=0;i=0;iM;iM;i+)+)for(jfor(j=0;j=0;jmaxvmaxv)maxvmaxv=vijvij;return return maxvmaxv;（1）用二维数组名字作为实际参数 实参用a，形参用b5图4.9 实际参数为二维数组名字，用二维数组名作为函数参数实现的是“传地址值调用”，其本质仍然是在函数调用期间实际参数数组将它的全部存储区域提供给形式参数数组共享，即形参数组与实参数组是同一存储区域。实参用a形参用b5图
32、4.9 实际参数为二维数组名字 例4.10程序的函数max中使用了二维数组样式的形式参数接收从主调函数中传递过来的二维数组首地址，使得形参数组v共享实参数组a的存储区域；然后通过对形参数组v的操作达到操作是参数a的目的，即在形参数数组v中寻找最大值实质上是在实参数组a中寻找最大值，程序执行的结果为：Max value is:789。（2）用二维数组起始地址的一级地址形式作为实际参数 在实际计算机应用的程序设计中有时需要能够处理任意行列大小的二维数组的函数（例如要求上例中的函数max能够查找任意二维数组中的最大元素），此时直接用二维数组作为形式参数的设计形式就不太适合。为了编制较通用的函数，可以
33、借助一维数组作为形式参数时可以不指定长度的特点，使用一维数组样式的形式参数接收二维数组实参，数组存储区域全部共享或部分共享时形参数组与实参数组的关系如图4.10所示。实参数组a形参数组b注：形参数组b本质上是指针变量图4.6 数组存储区域全部共享时形参数组与实参数组的关系 在实现这种参数传递时还须注意以下两点：函数调用时的实际参数必须是一级地址形式（参见图4.8中列出的3种以及地址方式），同时将二维数组的行数和列数传递到被调函数中。由于在被调函数中只知道被处理得二维数组的起始地址，所以在处理过程中二维数组每一行的长度由程序员根据参数表中传递过来信息自己控制。例4.11 重新编制例4.10中的函
34、数max，使其能够处理任意行列的二维数组。/*Name:ex04-11.cpp*/#include#define M 3#define N 4void main()int max(int v,int m,int n);int aMN=38,23,56,9,56,2,789,45,76,7,45,34;printf(Max value is:%dn,max(a0,M,N);intint max(intmax(int v,intv,int m,intm,int n)n)intint i,j,maxvi,j,maxv;maxvmaxv=v0;=v0;for(ifor(i=0;i=0;im;im;i+
35、)+)for(jfor(j=0;j=0;jmaxvmaxv)maxvmaxv=vivi*n+jn+j;return return maxvmaxv;程序中函数max用一维数组样式的形式参数v来接收从主调函数中传递过来的二维数组首地址，注意到二维数组的名字表示的是二级地址，所以被传递的二维数组的首地址不能直接用二维数组名表示而应该使用3种一级地址形式，本示例中使用的是a0，还可以使用&a00和*a形式。在被调函数中将传递过来的二维数组当作一维数组处理，其元素对应关系应该是：aijvi*n+j。程序执行的结果为：Max value is:789。基本控制结构的使用（字符图形的输出，基本控制结构的使
36、用（字符图形的输出，最大公约数最小公倍数，素数，穷举法，最大公约数最小公倍数，素数，穷举法，迭代法的简单实用）迭代法的简单实用）例例2-202-20 编程序输出如下所示由字符构成的图形。编程序输出如下所示由字符构成的图形。例例2-212-21 编程序在屏幕上打印出如下所示的乘法九九表。编程序在屏幕上打印出如下所示的乘法九九表。*1 2 3 4 5 6 7 8 9 1 1 2 2 4 3 3 6 9 4 4 8 12 16 5 5 10 15 20 25 6 6 12 18 24 30 36 7 7 14 21 28 35 42 49 8 8 16 24 32 40 48 56 64 9 9 1
37、8 27 36 45 54 63 72 81复习这些例题复习这些例题例例2-252-25 求两个正整数的最大公约数和最小公倍数。求两个正整数的最大公约数和最小公倍数。2.5.2 2.5.2 穷举思想及程序实现穷举思想及程序实现 穷举方法的实现主要依赖于以下两个基本要点：穷举方法的实现主要依赖于以下两个基本要点：搜寻可能值的范围如何确定。搜寻可能值的范围如何确定。被搜寻可能值的判定方法。被搜寻可能值的判定方法。对于被搜索的可能值，一般都是问题中所要查找对于被搜索的可能值，一般都是问题中所要查找的对象或者是要查找对象应该满足的条件，因而在问的对象或者是要查找对象应该满足的条件，因而在问题中都会有清
38、晰的描述。但对于搜寻范围，在有些问题中都会有清晰的描述。但对于搜寻范围，在有些问题是比较确定的，而在另外一些问题则是不确定的。题是比较确定的，而在另外一些问题则是不确定的。例例2-262-26 编程序找出所有的编程序找出所有的“水仙花数水仙花数”。“水仙花数水仙花数”是指一个是指一个3 3位数，位数，其各位上数字的立方之和等于这个数本身。例如其各位上数字的立方之和等于这个数本身。例如153=13+53+33153=13+53+33，所以，所以153153是是“水仙花数水仙花数”。例例2-222-22 编制程序实现功能：从键盘输入两个正整数编制程序实现功能：从键盘输入两个正整数a(aa(a2)2
39、)和和b b，求，求a a与与b b之间的全部素数。之间的全部素数。例例2-272-27 搬砖问题：搬砖问题：3636块砖，块砖，3636人搬，男搬人搬，男搬4 4，女搬，女搬3 3，两个小孩抬，两个小孩抬1 1砖。要求将所有的砖一次搬完，问需要男、女、小孩各多少？砖。要求将所有的砖一次搬完，问需要男、女、小孩各多少？例例2-282-28 爱因斯坦阶梯问题。设有一阶梯，每步跨爱因斯坦阶梯问题。设有一阶梯，每步跨2 2阶，最后余阶，最后余1 1阶；阶；每步跨每步跨3 3阶，最后余阶，最后余2 2阶；每步跨阶；每步跨5 5阶，最后余阶，最后余4 4阶；每步跨阶；每步跨6 6阶，最阶，最后余后余5
40、5阶；只有每步跨阶；只有每步跨7 7阶时，正好到阶梯顶。问共有多少步阶梯？阶时，正好到阶梯顶。问共有多少步阶梯？2.5.3 2.5.3 迭代思想及程序实现迭代思想及程序实现 迭代就是一个不断地由变量的旧值按照一定的规律推迭代就是一个不断地由变量的旧值按照一定的规律推出变量的新值的过程，迭代亦称为递推。出变量的新值的过程，迭代亦称为递推。迭代一般与三个因素有关，它们是：迭代一般与三个因素有关，它们是：初始值，初始值，迭迭代公式，代公式，迭代结束条件（迭代次数）。迭代结束条件（迭代次数）。例例2-292-29 裴波那契（裴波那契（FibonacciFibonacci）数列问题。裴波那契数列的前两）
41、数列问题。裴波那契数列的前两个数据项都是个数据项都是1 1，从第，从第3 3个数据项开始，其后的每一个数据项都是个数据项开始，其后的每一个数据项都是其前面的两个数据项之和。其前面的两个数据项之和。例题分析：设例题分析：设f1f1、f2f2和和f3f3表示相邻的表示相邻的3 3个裴波那个裴波那契数据项，据题意有契数据项，据题意有f1f1、f2f2的初始值为的初始值为1 1，即迭代的，即迭代的初始条件初始条件为：为：f1=f2=1f1=f2=1；迭代的公式迭代的公式为：为：f3=f1+f2f3=f1+f2。有初始条件和迭代公式只能描述前有初始条件和迭代公式只能描述前3 3项之间的关项之间的关系，为
42、了反复使用迭代公式，可以在每一个数据项系，为了反复使用迭代公式，可以在每一个数据项求出后将求出后将f1f1、f2f2和和f3f3顺次向后移动一个数据项，即顺次向后移动一个数据项，即将将f2f2的值赋给的值赋给f1f1，f3f3的值赋给的值赋给f2f2，从而构成如下的，从而构成如下的迭代语句序列：迭代语句序列：f3=f1+f2;f3=f1+f2;、f1=f2;f1=f2;、f2=f3;f2=f3;，反复，反复使用该语句序列就能够求出所要求的裴波那契数列。使用该语句序列就能够求出所要求的裴波那契数列。例例2-302-30 用牛顿迭代法求方程用牛顿迭代法求方程x x4 4-4x-4x3 3+6x+6
43、x2 2-8x-8=0-8x-8=0在在0 0附近的根。附近的根。例例2-312-31 用二分迭代法求方程用二分迭代法求方程2x2x3 3-4x-4x2 2+3x-6=0+3x-6=0在在(-10,10)(-10,10)之间的根。之间的根。例例2-322-32 用割线法求方程用割线法求方程2x2x3 3-4x-4x2 2+3x-6=0+3x-6=0在在(-10,10)(-10,10)之间的之间的根。根。函数的递归调用函数的递归调用 一个函数直接地或间接地自己调用自己，称为一个函数直接地或间接地自己调用自己，称为函数的递归调用。函数的递归调用可以看成是一函数的递归调用。函数的递归调用可以看成是一
44、种特殊的函数嵌套调用，它与一般的嵌套调用相种特殊的函数嵌套调用，它与一般的嵌套调用相比较有几个不同的特点：比较有几个不同的特点：（1）递归调用中每次嵌套调用的函数都是该函数）递归调用中每次嵌套调用的函数都是该函数本身；本身；（2）递归调用不会无限制进行下去，即这种特殊）递归调用不会无限制进行下去，即这种特殊的自己对自己的嵌套调用总会在某种条件下结束。的自己对自己的嵌套调用总会在某种条件下结束。例4.14 编程序使用递归方式求n!。/*Name:ex04-14.cpp*/#include void main()long fac(long n);long n,result;printf(Input
45、 the n:);scanf(%ld,&n);result=fac(n);printf(%ld!=%ldn,n,result);long fac(long n)if(n=1)return 1;elsereturn fac(n-1)*n;fac(5)等于120 fac(5)5*fac(4)fac(4)4*fac(3)fac(3)3*fac(2)fac(2)2*fac(1)fac(1)1递归压栈方向fac(2)2*fac(1)2*1 2fac(3)3*fac(2)3*2 6fac(4)4*fac(3)4*6 24fac(5)5*fac(4)5*24 120递归回溯方向图4.12 函数递归调用过程示
46、意图执行如下：递归是程序设计中一种非常重要的技术，与程序设计中其它控制方法策略相比较，递归程序设计的难度在于递归在人类社会的现实生活中没有直接对应的概念存在，而必须通过推理分析才能理解递归思想进而实现递归程序设计。在实际设计递归函数程序时，我们可以将重点放在分析递推公式和递归终止条件上，可以忽略系统的具体执行过程，只要算法和递推公式正确，结论一定是正确的。递归的实质是一种简化复杂问题求解的方法，递归的实质是一种简化复杂问题求解的方法，它将问题逐步简化直至趋于已知条件。在简它将问题逐步简化直至趋于已知条件。在简化的过程中必须保证问题的性质不发生变化，化的过程中必须保证问题的性质不发生变化，即在简
47、化的过程中必须保证两点：一是问题即在简化的过程中必须保证两点：一是问题简化后具有同样的形式；二是问题简化后必简化后具有同样的形式；二是问题简化后必须趋于比原问题简单一些。具体使用递归技须趋于比原问题简单一些。具体使用递归技术时，必须能够将问题简化分解为递归方程术时，必须能够将问题简化分解为递归方程（即问题的形式）和递归结束条件（即最简（即问题的形式）和递归结束条件（即最简单的解）两个部分。如例单的解）两个部分。如例4.14求求n的阶乘的阶乘,可以可以分解得到递归方程：分解得到递归方程：n*(n-1)！和递归结束条！和递归结束条件：件：n=1 时阶乘为时阶乘为1。例4.16 编程序用递归方法求两
48、个正整数的最大公约数。可以分析得出如下递归关系：0)%(),(0)%(),(nmrrnGcdnmrnnmGcdr=m%n=0gcd(n)retuan nreturn gcd(n,r)TF图4.14 最大公约数的递归算法/*Name:ex04-16.cpp*/#include void main()int Gcd(int m,int n);int num1,num2;printf(请输入两个正整数:);scanf(%d,%d,&num1,&num2);if(num1num2)num1=num1+num2,num2=num1-num2,num1=num1-num2;printf(%d与%d的最大公
49、约数是:%dn,num1,num2,Gcd(num1,num2);int Gcd(int m,int n)int r;if(r=m%n)=0)return n;elsereturn Gcd(n,r);通过上面两个示例的分析，递归方式的实现也是基于语言的条件控制结构。递归函数设计的基本框架是相对固定的，其一般形式可以描述如下：if 递归结束条件成立 Return 已知结果 else 将问题转化为同性质的较简单子问题；以递归方式求解子问题（递归方程）；例4.15 求菲波拉契数列。已知一对小兔出生一个月后变成一对成兔，两个月后这对成兔就会生出一对小兔，三个月后这对成兔将生出第二对小兔，而第一对小兔又
50、长大变成一对成兔，即一月成熟，二月生育，如此类推。请用计算机求解一对小兔经n月后将繁衍成多少对兔子？可以分析出如下递归关系:按照上面分析得到的递归方程和结束条件，求菲波拉契数列的递归算法可以设计为如图4.13所示。1)2()1(101)(nnfnfnnfn=0或者n=1fib(n)retuan 1return fib(n-1)+fib(n-2)TF图4.13 菲波拉契数列的递归算法/*Name:ex04-15.cpp*/#include void main()int m;float fib(int n);printf(请输入月份数);scanf(%d,&m);printf(经过%d个月后，兔子
