程序设计基础:第6章

程序设计基础_13521005.pdf

本页整理 **第 6 章《函数、递推与递归》全章(书上 P76~P99)+ 第 7 章的章首页(P100)**,对应 **PDF 物理页 98~122**(该 PDF 前 22 页为无页码页,故"物理页 = 书上页码 + 22")。按你的要求,上机环境统一为 **Linux 下的 C++(g++)**:教材里 VC 6.0 的"新建工程 → 按运行键"一律替换为 `g++ -o 程序名 源文件.cpp` 与 `./程序名`;教材中的 VC 专有写法(`#include <iostream.h>`、`void main()`、`Press any key to continue`)都已改写为标准 C++,凡与教材版本有差异之处都单独做了 **Linux 提示**。

教学目标

  • 函数的概念、定义、调用和返回
  • 带自定义函数的程序设计
  • 递推算法
  • 递归思想及算法实现

内容要点

  • 函数的定义,实际参数与形式参数,调用和返回值
  • 递推算法的思路
  • 递归的概念和思路
  • 用与或节点图描述递归算法
  • 递归算法举例与程序实现

【任务 6.1】二年级有 5 个班,每班人数分别为 45、43、42、45、44。春季运动会的拔河比赛,每个班限报一个队,每队 10 人。根据经验,体重总和大的队获胜的概率大。请编程输出哪个班可能胜出。

解题思路

  • (1)输入每个班每个人的体重;
  • (2)对班里的每个人按体重从大到小排序:weight1, weight2, …, weightn,将前 10 人挑出来作为班队去参赛;
  • (3)对每个班队计算 10 人的体重总和:zongzh = weight1 + weight2 + … + weight10;
  • (4)按体重总和从大到小对 5 个班队排序,作为能否胜出的估计结果。

像这样一个比较复杂的问题,如果程序指令全部放在主函数中,会造成代码重复书写、程序脉络不清晰、调试困难等问题。教材的比喻非常好:把主函数当作“组装车间”,把各个函数当作“生产零部件的车间”——函数可以不止一个,但都受主函数的控制和调用。

照这种思路,我们把任务 6.1 拆成 4 个函数(P77):

input(n);        // 输入 n 个人体重的函数
sort(m);         // 对 m 个数从大到小进行排序的函数
add(10);         // 10 个数求和的函数
output();        // 输出

主函数把 4 个函数“组装”起来(框架,教材 P77):

int main()                              // 主函数
{
    for (int i = 1; i <= 5; i = i + 1)  // 从第 1 班到第 5 班,一个一个班地处理
    {
        cout << "输入第 i 班的学生人数"; // 提示信息
        cin >> n;                       // 输入第 i 班的学生人数
        input(n);                       // 记录 n 个人的体重
        sort(weight[i][n]);             // 对第 i 班 n 个人的体重排序
        sum[i] = add(weight[i][n]);     // 求第 i 班前 10 人的体重总和
    }
    sort(sum[i]);                       // 对 5 个班的体重总和排序
    output();                           // 输出排序结果
    return 0;
}

通过这个例子可以看出:4 个生产“零部件”的车间规模小、质量容易控制、编程和调试相对简单;到了“组装车间”,就像搭积木一样,拿来就用,方便而有效。这就是模块化的思想在编程中的体现。

库函数是 C 语言环境提供给用户的一些常用函数(“零部件”),用户查到这些函数的功能,编程需要时将其调来“组装”即可。例如求 45°角的正弦函数值 sin(π/4),如果没有现成的库函数,自己编程计算会很麻烦;下面来看调用库中的正弦函数求值,真是轻而易举。

教材程序 6-1.cpp(求正弦函数的值)——已改写为在 Linux 下可直接编译的版本:

// 程序名:6_1.cpp
// 主要功能:求正弦函数的值
#include <iostream>
#include <cmath>                     // 加入 C 语言的数学函数库(教材写作 <math.h>)
using namespace std;                 // 使用标准命名空间
 
int main()
{
    double x;                        // 定义角度变量为双精度实数
    cout << "请输入角度值" << endl;    // 提示信息
    cin >> x;                        // 键盘输入角度值
    x = x * 3.14159 / 180;            // 将角度值化为弧度值
    cout << sin(x) << endl;           // 输出 x 的正弦函数值
    return 0;
}

编译与运行:

$ g++ -o 6_1 6_1.cpp
$ ./6_1
请输入角度值
45
0.707107

对程序的说明

  • (1)调用 C 语言的数学函数,要加入相应的头文件:教材写作 #include <cmath.h>/<math.h>,在 g++ 下推荐写 #include <cmath>(标准 C++ 头文件)。
  • (2)sin(x) 属于带参数的库函数,sin 是专用的函数名,x 是形式参数。函数原型为 double sin(double x):sin 前面的 double 定义函数值为双精度实数,括号中的 double x 用来定义自变量 x 是双精度实数,x 的值以弧度为单位。因此程序中第 15 行赋值号右边的 x 是由键盘输入的角度值,把角度值化为弧度用 x = x * 3.14159 / 180。
  • (3)第 16 行输出语句中写 sin(x),表示主函数调用库中的 sin(x) 函数;这时的 x 是由主函数通过输入、转换后的实实在在的 x 值,称为“实参“,譬如 45 * 3.14159 / 180。调用过程就是求 sin(45 * 3.14159 / 180) 的值。

1.常用库函数简介:C 语言的库函数主要有 5 大类——(1) 数学函数;(2) 字符函数与字符串函数;(3) 输入与输出函数;(4) 随机函数;(5) 动态分配函数。附录 D 列出了这些函数,使用前要先了解其功能、学会如何正确调用。

2.常用的数学函数:C 语言提供了几百个数学函数,教材介绍了最常用的 10 个(P78~P79):

函数 原型 说明与例
abs(x) int abs(int x) 求绝对值,自变量与函数值都是整数:abs(-6)=6
labs(x) long labs(long x) 求长整数的绝对值:labs(-3276700)=3276700
fabs(x) double fabs(double x) 求双精度实数的绝对值:fabs(-2.71828)=2.71828
sin(x) double sin(double x) 正弦:sin(3.1415926535/2)=1
cos(x) double cos(double x) 余弦:cos(3.1415926535/2)=4.48966e-011(十分接近 0)
tan(x) double tan(double x) 正切:tan(3.1415926535/4)=1
exp(x) double exp(double x) 求 e 的 x 次幂:exp(1)=2.71828,exp(2.302585093)=10
log(x) double log(double x) 求以 e 为底的对数 ln x:log(2.71828)=0.999999
log10(x) double log10(double x) 求以 10 为底的对数 lg x:log10(10.0)=1.0
pow(x,y) double pow(double x,double y) 求 x 的 y 次幂:pow(2.0,3.0)=8.0
floor(x) double floor(double x) 求不大于 x 的最大整数:floor(2.8)=2,floor(-2.8)=-3
sqrt(x) double sqrt(double x) 求 x 的平方根:sqrt(42.25)=6.5

教师总结的基本准则:尽量使用库中已有的函数,实在没有现成可用的,再自己编。

【练习 6.1】已知直角三角形的两条直角边,求第三边。

编写程序实现:输入两个非 0 的正实数 x 和 y(两个直角边),输出直角三角形的斜边 z(z = sqrt(x * x + y * y))。

教材程序 6-2.cpp:

// 程序名:6_2.cpp
// 主要功能:求 sqrt(x*x+y*y)
#include <iostream>
#include <cmath>                     // 加入 C 语言的数学函数
using namespace std;
 
int main()
{
    double x, y, z;                  // 定义三个 double 类型变量
    cout << "输入两个非 0 的实数" << endl;   // 提示信息
    cin >> x >> y;                   // 键盘输入两个实数
    z = sqrt(x * x + y * y);         // 计算 x 的平方加 y 的平方的平方根
    cout << "斜边为 z=" << z << endl; // 输出 z
    return 0;
}

运行结果:

$ g++ -o 6_2 6_2.cpp && ./6_2
输入两个非 0 的实数
3 4
斜边为 z=5

程序说明:计算平方根函数的自变量定义为 double 类型,函数值也是 double 类型,因此在定义 x、y、z 时使用 double 类型;第 15 行中出现的 sqrt(x * x + y * y),表示以 x² + y² 的值作为实参去调用求平方根的函数,之后再将算出的平方根值赋给 z。

【练习 6.2】编写程序计算 z = (ln5 × (ln3) − ln2) / sin(3.14159/3)。

教材程序 6-3.cpp:

// 程序名:6_3.cpp
// 主要功能:计算 z=(log(5.0)*log(3.0)-log(2.0))/sin(3.14159/3.0)
#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    double z;                        // 定义 double 类型变量 z
    z = (log(5.0) * log(3.0) - log(2.0)) / sin(3.14159 / 3.0);  // 调用数学函数计算 z
    cout << "z=" << z << endl;       // 输出 z
    return 0;
}

运行结果(Linux,g++):

$ g++ -o 6_3 6_3.cpp && ./6_3
z=1.24149
  • 注意 log(x) 是以 e 为底的自然对数(ln),log10(x) 才是以 10 为底的对数(lg),用混了结果就完全不同
  • Linux 提示:数学函数库(libm)在 g++ 下默认已链接;如果你的环境较老,出现 undefined reference to sin 一类的链接错误,在编译命令末尾加上 -lm 即可(g++ -o 6-1 6-1.cpp -lm)

【类似练习】用库函数解决下面两个小问题(做法与前面两个例子完全相同):

  • 输入球的半径 r,输出球的体积 V = 4/3·π·r³(用 pow(r,3.0),π 取 3.14159);
  • 输入一个正实数 a,输出 ⌊√a⌋ 与 √a 的小数部分(提示:用 sqrt() 和 floor(),两者相减即小数部分)。

编程时尽量使用库中给出的函数,省时省力;但有时库中找不到所需的函数,就得自己动手编。看下面一个例子。

【任务 6.2】一个人事总监为公司招募壮劳力 10 人,应试者有 20 人,每次叫两人进来面试,留下体重大的人。这样他要比较 10 次,招收 10 个人,并计算、记录 10 个人的总重量。

我们可以设计两个子函数 comp(a,b) 和 add(x,y)。

comp(a,b) 的功能是:比较两人的体重 a 和 b,当 a ≥ b 时留 a,否则留 b。按题意比较体重需要实数类型的数据,因此定义如下:

float comp (float a, float b) {
    if (a >= b) return a;            // 如果 a 体重大,返回 a
    else return b;                   // 否则返回 b
}

add(x,y) 的功能是实现 x + y,定义如下:

float add (float x, float y) {
    return x + y;                    // 返回 x+y 的值
}

有了上述两个自定义函数,就像有了两个零部件,”总装车间”就可以将它们组装成产品了。

教材程序 6-4.cpp:

// 程序名:6_4.cpp
// 主要功能:自定义函数举例
#include <iostream>
using namespace std;
 
float comp (float a, float b);       // 先声明有自定义函数 comp(a,b)
float add  (float x, float y);       // 先声明有自定义函数 add(x,y)
 
int main()
{
    float x1, x2, x;                 // 定义 float 类型变量
    float sum = 0;                   // 定义 float 类型变量,初始化为零
    for (int i = 1; i <= 10; i = i + 1)   // 循环,做 10 次
    {
        cout << "请输入两个人的重量 x1 和 x2" << endl;   // 提示信息
        cin >> x1 >> x2;             // 输入两个实数
        x = comp(x1, x2);            // x1 与 x2 比较,取大者赋给 x
        sum = add(sum, x);           // sum 与 x 相加后赋给 sum
    }
    cout << "10 位录用者的总重量为" << sum << endl;   // 输出
    return 0;
}
 
float comp (float a, float b) {      // 定义函数 comp
    if (a >= b) return a;            // 如果 a 值大,返回 a 的值
    else return b;                   // 否则返回 b
}
 
float add (float p, float q) {       // 定义函数 add
    return p + q;                    // 返回 p+q
}

运行结果(节选):

$ g++ -o 6_4 6_4.cpp && ./6_4
请输入两个人的重量 x1 和 x2
60 65
请输入两个人的重量 x1 和 x2
70 68
...
10 位录用者的总重量为 685

程序说明

  • (1)在主程序之前先声明有自定义函数:第 9、10 行告诉系统主程序中会用到两个名为 comp 和 add 的自定义函数(这叫函数声明/函数原型)。
  • (2)在主程序之后要定义这两个函数:第 25~28 行是 comp 函数,第 29~31 行是 add 函数。
  • (3)主程序中的 for 循环完成 10 次对 20 位应试者的挑选和累加被选中者的体重。
  • (4)第 19 行 x = comp(x1, x2); 是主函数调用 comp 子函数:对于赋值号右边的 comp(x1, x2),是把实际参数 x1 与 x2 作为自变量去调用 comp 函数,这时程序转到 comp 函数去执行,先按顺序将 x1 赋给 a、x2 赋给 b,再通过 if…else 语句比较,取大者作为函数的返回值,子函数运行结束后回到第 19 行,把返回值赋给 x。
  • (5)第 20 行 sum = add(sum, x); 同理:把实参 sum 赋给 p、x 赋给 q,p+q 作为函数返回值,回到第 20 行赋给 sum。
  • (6)循环结束后,选定了 10 人,并将 10 人的体重总量累加到 sum 中。
  • Linux 提示:注意 add 函数的形参也叫 x,与全局变量 x 同名——在 add 函数体内起作用的是局部形参 x,全局 x 被“屏蔽”,这正是 6.1.8 小节要讲的规则;而主函数里的 x 是全局变量。g++ 用 -Wall 编译时会提示相关警告,可以忽略。另外 float 只有 7 位有效数字,求总重量用 double 更稳妥。

【类似练习】按同样的“两个零部件 + 总装”思路,编写程序输入任意 3 个实数,输出其中的最大值与它们的平均值。提示:最大值依次调用两次 comp,平均值用 add 求和后除以 3。

函数定义的格式为:

函数返回值的类型名 函数名(类型名 形式参数 1, 类型名 形式参数 2, …)
{                       // 函数体
    说明部分
    执行部分
}

例如任务 6.2 中的一个子函数名是 comp,以英文字母命名;形式参数有两个,分别为 a 和 b,定义成 float 实数类型;函数返回值类型也是 float;用大括号括起的部分是函数体。

同主函数一样,函数体也有两大部分:先是说明部分,后是执行部分。执行部分包含 return 语句(函数的返回语句见 6.1.5 小节)。

  • (1)形式参数是在定义函数时放在函数名称之后的括号中的参数。在函数未被调用时,系统不对形式参数分配内存单元;在函数被调用时,系统会给形式参数分配内存单元,调用结束后再释放形式参数所占有的内存单元。因此,形式参数属于局部变量,其作用域限定在它所在的函数体内。分配内存大小涉及数据类型,这就不难理解为什么在定义函数时要指定形参变量的数据类型了。
  • (2)实际参数是一个具有确定值的表达式。函数在调用时,要将实际参数赋给形参变量。例如任务 6.2 的主函数用 x = comp(x1, x2) 调用子函数 comp,这时 x1 和 x2 为实际参数,a 和 b 是形式参数;在函数被调用时,系统为 a 和 b 分配内存单元,之后实际参数 x1 的值赋给了形式参数 a,实际参数 x2 的值赋给了形式参数 b(如图 6.1 所示:主函数中的 x1=3、x2=6,子函数中的 a=3、b=6)。
  • (3)实际参数的个数及类型应与形式参数一致,赋值时多个参数之间的前后对应关系不变。
  • (4)在传值调用时为单向传递,即实参只能向形参传递,而不能反向(由形参向实参)传递。

函数一般是由主函数调用的(当然也有函数调用函数的情况),调用函数的目的一般是让它计算某一个函数值,这个值通过 return 语句返回给调用它的函数。格式是:

return 表达式;         // 或写作 return (表达式);

表达式的值就是函数的取值,其数据类型要与定义函数时的说明相一致。

有时被调用的函数只是一些操作,而不需返回数值,这时返回语句的格式为:

return;                // 只结束函数的执行,不返回值

教材特别强调:有调用就要有返回,程序中一定要有 return 出现,注意养成这个好习惯。

主函数通过实参去调用子函数,将实参赋给子函数中的形参;子函数运算之后,又将结果返回给主函数一个值。例如 6-4.cpp 中第 19 行 comp 函数的唯一返回值赋给 x。

函数一经定义,以其名为标识的一片内存地址就被该函数所占有。在这片地址中存储着相关的一系列程序指令,但没有具体值。因此,程序中一出现该函数名,就意味着程序转到了这一片内存地址,去执行相关的一系列程序指令(这里讲地址是为以后讲指针做些铺垫)。

函数的调用方式有以下两种

  • (1)对于有返回值的函数,可将其视作表达式放在任何可放的地方。例如程序 6_4.cpp 中的 x = comp(x1, x2),因为 comp 函数的返回值是 float 型,与赋值符号左边的 x 变量的数据类型要求一致。此外,函数的返回值还可以参与到表达式运算中。
  • (2)对于没有返回值的函数,一般会实现一系列操作,这时函数会在程序中作为独立的语句出现,不以表达式形式出现。

教材用了一个很形象的比喻帮助理解:一个葡萄酒制造厂,如果只有人员和设备,没有订单和原材料,是不可能开工的。酒业公司给葡萄酒制造厂派发具体的订单,并将大量原材料运抵酒厂,令其开工生产,按时保质保量完成任务。事例中的酒业公司好比主函数,葡萄酒制造厂好比一个子函数,人员、设备和工艺流程等为子函数中的一系列程序指令,订单和原材料好比子函数的两个形式参数,成品葡萄酒为子函数的返回值。某公司给葡萄酒制造厂发订单和原材料,相当于主函数开始调用子函数;通过具体订单和大量原材料作为实际参数传递给子函数的形式参数,工厂开始工作相当于子函数开始运行;最终将成品葡萄酒运到酒业公司,相当于将子函数的返回值传给主函数。

【任务 6.3】用键盘输入一个正整数 a,判断 a 是否为素数(质数)。

解题思路:首先计划设计一个函数 checkprime() 来负责检查 a 是否为素数,如果是,该函数返回 1;否则返回 0。定义为 int checkprime(int a)。教材程序 6-5.cpp:

// 程序名:6_5.cpp
// 主要功能:判断素数
#include <iostream>
#include <cmath>                     // 用到 sqrt(),教材写作 <math.h>
using namespace std;
 
int checkprime (int);                // 声明有子函数
int main()                           // 主函数
{
    int a = 0, b = 0;                // 定义整型变量,初始化为 0
    cout << "请输入一个整数: a=";    // 提示信息
    cin >> a;                        // 从键盘输入一个整数
    b = checkprime(a);
    // 调用 checkprime() 函数通过实际参数 a 做值传递,函数返回值赋给 b
    if (b)                           // b 作为 if 语句的分支条件
    {
        cout << "a 是素数" << endl;   // b 为 1,输出 a 是素数
    }
    else
    {
        cout << "a 不是素数" << endl; // b 为 0,输出 a 不是素数
    }
    return 0;
}                                    // 主函数结束
 
// 以下为检验整数是否为素数的自定义函数
int checkprime (int af)              // 函数返回值为整型,af 为整数类型的形式参数
{                                    // 子函数开始
    int k = 0;                       // 定义整型变量 k,并初始化
    for (k = 2; k <= sqrt(af); k = k + 1)   // 循环
    {
        if (af % k == 0)             // 如果 af 能够被 k 整除
        {
            return 0;                // 则判定 af 不是素数,返回 0
        }
    }
    return 1;                        // af 不能被 k 整除,则返回 1
}                                    // 子函数结束

运行结果:

$ g++ -o 6_5 6_5.cpp && ./6_5
请输入一个整数: a=17
a 是素数
$ ./6_5
请输入一个整数: a=91
a 不是素数

主函数调用子函数的过程(教材图 6.2 的文字版)

  • (1)主函数中先是由键盘输入一个正整数(比如 17),赋给 a;
  • (2)执行 b = checkprime(a),注意这时的 a 已有具体的数值,这个数就是实际参数。这条语句将程序转至 checkprime() 函数所占的地址去执行子函数,先是为形式参数 af 分配内存单元,之后将 a 的值 17 赋给 af;
  • (3)接着执行 checkprime(af) 所定义的运算:这里是 for 循环结构,让 k = 2, 3, …, √af,用一条 if 语句判断 af 能否被 k 所整除。如能,则判定 af 不是素数,将 0 返回;如不能被 k 整除,则将 1 返回,最终将返回值赋给 b;
  • (4)主函数通过分支语句 if (b) 判断 b 是 0 还是 1,来输出 a 是否为素数的信息。

对子函数而言“有调用就会有返回”:主函数调用子函数时,程序会从主函数所在的内存地址区转移到子函数所在的内存地址区执行子函数的指令序列;当子函数的程序执行完毕,程序还会返回到主函数所在区。

教材的思考题:能否去掉第 15 行 b = checkprime(a);,同时将第 16 行改为 if (checkprime(a)),其他程序不动,看能否完成同样的功能?

  • 可以。函数调用一旦出现在表达式中,其返回值直接参与判断,就不再需要 b 这个中转变量。Linux 提示:这样改写后 b 变量就不再用到,g++ 加 -Wall 编译时会提示 unused variable 'b。

【类似练习】把“判断素数”改造成“求两个正整数的最大公约数”:写一个 int gcd(int m, int n) 函数,用辗转相除法(欧几里得算法),主函数输入两个数并输出结果。参考实现:

// 程序名:gcd.cpp
// 主要功能:自定义函数求最大公约数
#include <iostream>
using namespace std;
 
int gcd (int m, int n)               // 函数返回值为整型
{
    int r;
    while (n != 0)                   // 辗转相除
    {
        r = m % n;
        m = n;
        n = r;
    }
    return m;                        // 余数为 0 时,m 就是最大公约数
}
 
int main()
{
    int a, b;
    cout << "请输入两个正整数:";
    cin >> a >> b;
    cout << a << " 和 " << b << " 的最大公约数是 " << gcd(a, b) << endl;
    return 0;
}

运行结果:

$ g++ -o gcd gcd.cpp && ./gcd
请输入两个正整数:24 36
24 和 36 的最大公约数是 12

在函数内部定义的变量是局部变量,局部变量只能在函数内使用,具有局限性;在所有函数的外部定义的变量是全局变量,全局变量可以在程序的任何地方使用。

教材程序 6-6.cpp(说明全局变量和局部变量):

// 程序名:6_6.cpp
// 主要功能:说明全局变量和局部变量
#include <iostream>
using namespace std;
 
float x1, x2, x;                     // 定义 float 类型的全局变量
float sum = 0;                       // 定义 float 类型的全局变量,并初始化为零
 
float comp (float a, float b) {      // 定义函数 comp
    if (a >= b) return a;            // a 和 b 是局部变量,只在 comp 函数内部使用
    else return b;
}                                    // 函数 comp 结束
 
float add (float x, float y) {       // 定义函数 add
    return x + y;                    // x 和 y 是局部变量,只在 add 函数中使用
}                                    // 函数 add 结束
 
int main()
{
    int k;                           // 在主函数中定义的局部变量 k
    for (k = 1; k <= 10; k = k + 1)  // 循环,做 10 次
    {
        cout << "请输入两个人的重量 x1 和 x2" << endl;   // 提示信息
        cin >> x1 >> x2;             // 输入两个实数,x1 和 x2 是全局变量
        x = comp(x1, x2);            // 取大者赋给全局变量 x
        sum = add(sum, x);           // 累加,赋给全局变量 sum
    }
    cout << "10 位录用者的总重量为" << sum << endl;   // 输出
    cout << a;                       // a 是局部变量,在主函数中不能用 ← 这一行是错的!
    return 0;
}

程序说明

  • (1)上面的程序中,变量 x1、x2、x、sum 为全局变量。全局变量的有效范围是从定义变量的位置开始到本源文件结束。定义全局变量的语句一般放在主函数以前。确切地说,它是在所有函数之外进行声明,对整个程序都是可见的,在程序执行期间都拥有值,可被任何代码使用。变量 a 和 b 是在函数 comp 中使用的局部变量,a 和 b 只是在进入子程序块时才被创建,退出该块时被销毁,这与全局变量不同。这个程序的第 29 行 cout << a; 是错误的,编译时通不过,因为 a 是局部变量,不能在主函数中使用。教材给出的出错信息是: <code>error C2065: 'a': undeclared identifier</code> 在 Linux 的 g++ 下,对应的报错信息是: <code> error: 'a' was not declared in this scope </code>
  • (2)如果局部变量与全局变量同名,则在该局部变量的作用范围内,全局变量不起作用。
  • (3)利用全局变量可以实现各函数之间的数据传递。
  • (4)除非十分必要,一般不提倡使用全局变量。原因是:① 全局变量可以被程序中的所有函数使用,全局变量自始至终都需要占用存储空间,即使实际执行的函数根本不需要这些全局变量,它们也要占用存储空间;② 在子函数中使用全局变量后,要求在所有调用该子函数的调用函数中都要使用这些全局变量,降低了函数的通用性;③ 在子函数中使用全局变量之后,使各函数模块之间的相互影响比较大,从而使函数模块的“内聚性”差;④ 在子函数中使用全局变量,会降低程序的清晰度,程序的可读性差。
  • 教材留了一个好问题:程序 6-6.cpp 写得不好,你能指出哪些地方不好吗?(提示:所有数据都用全局变量传递、局部变量与全局变量混用、还留了一行必然编译失败的语句——应该把数据用参数和返回值传递,删掉多余的全局变量与错误语句。)

【类似练习】把 6_6.cpp 改成“不使用任何全局变量”的版本:comp 与 add 之间、函数与主函数之间的数据全部用参数和返回值传递,main 中只保留局部变量。改完后你会发现程序更短、更清晰。

递推是计算机数值计算中的一个重要算法。思路是通过数学推导,将复杂的运算化解为若干重复的简单运算,以充分发挥计算机擅长于重复处理的特点。

【任务 6.4】输出前 n 项非波那契(Fibonacci)数列。非波那契数列的第 1、第 2 项的值为 1,从第 3 项开始,每一项的值是前两项的和。

解题思路:按照“第 1、第 2 项的值为 1,从第 3 项开始,每一项的值是前两项的和”这个变化规律,可以得到下面的数列:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

这个数列可用公式描述为:

F(n) = 1                    当 n = 1
F(n) = 1                    当 n = 2
F(n) = F(n-1) + F(n-2)      当 n > 2

如图 6.3 所示,令 f1、f2、f3 分别表示 F(n−2)、F(n−1) 和 F(n),从左至右,相邻 3 个数之间的关系满足 f1 + f2 = f3:

f1  f2  f3
1   1   2                      ← 第 1 行:f1=1, f2=1, f3=1+1=2
    1   1   2   3              ← 第 2 行:黑框右移一位,f1 取上一行的 f2,f2 取上一行的 f3
        2   3   5              ← 第 3 行:f3 = 2+3 = 5
            3   5   8          ← 依次类推
                5   8   13
                    8   13  21
                        13  21  34
                            21  34  55

例如当 n = 3 时,F(3) = F(2) + F(1),此时 F(2) = 1、F(1) = 1,得到 F(3) = 1 + 1 = 2(图 6.3 中第一行的情况,用黑框框起的 3 个数据是 f1 = 1、f2 = 1、f3 = 2)。接下来求 F(4),让黑框向右移一位,此时的 f1 是上一行的 f2,此时的 f2 是上一行的 f3,第二行的 f3 = f1 + f2 = 1 + 2 = 3。以此类推,不难找到如图 6.4 的算法框图:

设初始条件:f1 = 1;f2 = 1
输入具体计算项数 n
输出 f1 和 f2
for (i = 1; i <= n - 2; i++)
    计算 f3:f3 = f1 + f2
    输出 f3
    计算新 f1:f1 = f2
    计算新 f2:f2 = f3

通过这个问题可以发现:如果未知项与已知项之间存在着某种关系,可以借助已知项一项一项地推出未知项,这种方法称为递推。递推算法是最常用的一种程序设计方法。

按照图 6.4,可写出教材程序 6-7.cpp:

// 程序名:6_7.cpp
// 主要功能:输出非波那契数列的前 n 项
#include <iostream>
#include <iomanip>                   // 使用 setw() 需要这个头文件(Linux/g++ 下必须加)
using namespace std;
 
void F()                             // 定义无返回值的函数 F()
{                                    // 自定义函数开始
    int i, f1, f2, f3, n;            // 定义整型变量
    f1 = 1;                          // 赋值(数列第 1 项)
    f2 = 1;                          // 赋值(数列第 2 项)
    cout << "需要输出多少项?";        // 提示信息
    cin >> n;                        // 输入一个整数
    cout << setw(2) << f1 << "," << setw(2) << f2 << endl;   // 输出数列的第 1、2 项
    for (i = 1; i <= n - 2; i++)     // 循环,输出第 3~n 项
    {                                // 循环体开始
        f3 = f1 + f2;                // 前两项相加赋给 f3
        cout << setw(2) << f3 << endl;   // 输出 f3
        f1 = f2;                     // 准备算下一项
        f2 = f3;                     // 准备算下一项
    }                                // 循环体结束
}                                    // 自定义函数结束
 
int main()
{
    F();                             // 调用 F() 函数
    return 0;
}                                    // 主函数结束

运行结果(输入 9):

$ g++ -o 6_7 6_7.cpp && ./6_7
需要输出多少项?9
 1, 1
 2
 3
 5
 8
13
21
34
  • 主函数只有两条语句,其中一条就是调用 F() 函数
  • 被调用的 F() 函数在主函数之前定义,自己完成定义变量、初始化、计算、输入和输出等全部功能;F() 函数不需要有返回值,因此在定义时其数据类型取 void
  • Linux 提示:教材 6-7.cpp 只写了 #include <iostream> 却使用了 setw(),setw 声明在 <iomanip> 中;g++ 下不加 <iomanip> 会报 ‘setw’ was not declared in this scope
  • 递推的核心是三句“滚动更新“:f3 = f1 + f2;、f1 = f2;、f2 = f3;——顺序不能颠倒

【类似练习】用同样的”滚动更新”思路,输出前 n 项累加和数列 1, 3, 6, 10, 15, …(第 i 项等于前 i 个自然数之和):

// 程序名:sum_seq.cpp
// 主要功能:用递推输出前 n 项累加和数列
#include <iostream>
using namespace std;
 
int main()
{
    int n, i, s = 0;
    cout << "需要输出多少项? ";
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        s = s + i;                   // 已知前一项的和,再加 i 就得到新一项
        cout << s << " ";
    }
    cout << endl;
    return 0;
}

递归算法在可计算理论中占有重要地位,是算法设计的有力工具,对于拓展编程思路非常有用。

【任务 6.5】用递归算法求 n!。

解题思路:当 n ≥ 0 时,求 n! 的问题可以转化为求 n × (n−1)! 的新问题,而求 (n−1)! 的解法与原来求 n! 的解法相同,只是运算对象由 n 变成了 n−1;而求 n × (n−1)! 的问题又可以转化为求 n × (n−1) × (n−2)! 的新问题……每次转化为新问题时,运算对象就递减 1,直到运算对象的值递减至 0 时,阶乘的值为 1,求 n! 的递归结束,所以当 n = 0 时是递归结束的条件。

用公式表示为:

n! = 1                    当 n = 0 时
n! = n × (n-1)!           当 n > 0 时

为了表述得直观清晰,定义两个节点:“或节点”和“与节点”。

  • 或节点(图 6.5,用“○”表示):图中 A 为或节点,A 依不同条件会有两种不同的取值 B 或 C。如果多于两种取值,则用图 6.6 表示(条件为 Z1, Z2, …, Zn 时,A 取值为 B 或 C … 或 G)。
  • 与节点(图 6.7):与节点要涂黑,相关联的 B 与 C 之间要用弧线连起来。A 为与节点,A 的最终取值为 C 节点的值,但为了求得 C 的值,得先求出 B 节点的值,C 是 B 的函数。

根据以上图示定义,可以画出求 n! 的与或图(图 6.8):A 为或节点;B 为直接可解节点,值为 1(直接可解节点用圆圈中加一个黑点表示);C 为与节点,当 n > 1 时,A 的取值即 C 的值;而 C 的值即 E 的值;为了求得 E 的值,需要先求出 D 的值;D 值 fact(n−1) 乘以 n 即为 E 的值。

以 3! 为例的与或节点图(图 6.10):

             A ○  fact(3)
              |   3>1
              ● C
       n=1 /      \ n>1
       B ○          ○ E
   fact(2)  2>1     3*fact(2)
       ...
右侧标注:C=1
          D = 2 * C = 2
          B = D = 2
          E = 3 * B = 3 * 2 = 6
          A = E = 6

图 6.11 画出了调用和返回的递归示意图(A→B→C 逐层调用,再从 C→D→E 逐层返回)。通过图 6.11 可以想象:欲求 fact(3),先要求 fact(2);要求 fact(2),先求 fact(1)。就像剥一颗圆白菜,从外向里,一层层剥下来,到了菜心,遇到 1 的阶乘,其值为 1,到达了递归的边界;然后再用 fact(n) = n * fact(n-1) 这个普遍公式,从里向外倒推回去得到 fact(n) 的值。 这就是教材的“圆白菜”比喻。

为了进一步讲清递归的概念,将递归与递推做一比较(仍以求阶乘为例):

  • 递推是从已知的初始条件出发,逐次去求所需要的阶乘值。如求 3!,初始条件 fact(1) = 1,于是 fact(2) = 2 * fact(1) = 2,fact(3) = 3 * fact(2) = 6。递推过程相当于从“菜心”推到“外层”。
  • 递归算法的出发点不放在初始条件上,而放在求解的目标上,从所求的未知项出发逐次调用本身的求解过程,直到递归的边界(即初始条件)。就本例而言,读者会认为递归算法可能是多余的、费力而不讨好;但许多实际问题不可能或不容易找到显而易见的递推关系,这时递归算法就表现出了明显的优势。递归算法比较符合人的思维方式,可将问题描述得简明扼要,具有良好的可读性,逻辑性强,且易于理解。许多相当复杂或难以下手的问题,如果能够使用递归方法,就能化难为易。

教材程序 6-8.cpp(用递归算法计算 n!):

// 程序名:6_8.cpp
// 主要功能:用递归算法计算 n!
#include <iostream>
using namespace std;
 
float fact (int n)                   // 定义 fact() 函数返回值为实型
{                                    // 自定义 fact() 函数开始
    float s;                         // 定义实型变量
    if (n == 0) return 1;            // 如果 n==0,返回 1
    else                             // 否则,执行下面的语句块
    {                                // else 语句块开始
        s = n * fact(n - 1);         // 调用函数 fact(n-1),乘以 n 再赋给 s
        return s;                    // 返回值 s
    }                                // else 语句块结束
}                                    // 自定义 fact() 函数结束
 
int main()
{
    int n;                           // 定义整型变量 n
    float y;                         // 定义实型变量 y
    cout << "您要查询第几项?";        // 提示信息
    cin >> n;                        // 输入一个整数
    if (n < 0)                       // 如果 n<0,提示输入不正确
        cout << "您的输入不正确";
    else                             // 否则,执行下面的语句块
    {
        y = fact(n);                 // 调用 fact(),返回值赋给 y
        cout << n << "!=" << y << endl;   // 输出 n 的阶乘值
    }
    return 0;
}

运行结果:

$ g++ -o 6_8 6_8.cpp && ./6_8
您要查询第几项?5
5!=120
  • 教材要求务必上机运行这个程序,弄清递归是如何进行的;有条件的话在 s = n * fact(n-1); 前后各加一句输出(例如 cout << "调用 fact(" << n-1 << ")" << endl;),就能看到“一层层剥白菜、再一层层返回”的完整过程
  • Linux 提示:fact 返回 float,n 稍大就会溢出(float 只有约 7 位有效数字,13! 就已超出精度);工程上应使用 long long,或用 <climits>/大数算法。想验证递归深度,可以在函数里加个静态计数器

【任务 6.6】通过递归算法输出非波那契数列第 n 项的值。

例题 6.4 中给出了求非波那契数列前 n 项值的递推算法,下面用递归算法来做。非波那契数列的数学公式如下:

F(n) = 1                    当 n = 1
F(n) = 1                    当 n = 2
F(n) = F(n-1) + F(n-2)      当 n > 2

根据公式可以画出如图 6.14 所示的与或节点图(F(n) 为或节点,n=1、n=2 时直接可解为 1;n>2 时为与节点:F(n−1) 与 F(n−2) 都求出来以后,才得到 F(n−1)+F(n−2))。按照这个图很容易写出用递归算法计算非波那契数列的程序。

教材程序 6-9.cpp:

// 程序名:6_9.cpp
// 主要功能:用递归算法计算非波那契数列的第 n 项
#include <iostream>
using namespace std;
 
int F (int n)                        // 定义递归函数 F(),返回值为整型
{                                    // 自定义函数开始
    int y;                           // 定义整型变量 y
    if (n == 1) y = 1;               // 如果 n 等于 1,y 赋值为 1
    else if (n == 2) y = 1;          // 否则,如果 n 等于 2,y 赋值为 1
    else y = F(n - 1) + F(n - 2);    // 否则,调用 F(n-1)、F(n-2) 相加后赋给 y
    return y;                        // 返回值 y
}                                    // 自定义函数结束
 
int main()
{
    int x, z;                        // 定义整型变量
    cin >> x;                        // 输入一个整数
    z = F(x);                        // 调用 F(),返回值赋给 z
    cout << "第" << x << "项的值为:" << z << endl;   // 输出结果
    return 0;
}                                    // 主函数结束

运行结果:

$ g++ -o 6_9 6_9.cpp && ./6_9
10
第10项的值为:55

用递归算法计算非波那契数列与前面的递推算法相比,显然是递归算法更为清晰、简练、易读、易理解。许多看来相当复杂、难以下手的问题,如果能把它们归纳成递归问题,处理起来就方便得多了。但是,对大多数程序而言,递归算法实现起来效率较低:因为当函数 F() 自己调用自己时,系统将自动把函数中当前的变量和形参暂时保存起来,在新一轮的调用过程中,系统又会为该次调用的函数所用到的变量和形参开辟另外的存储单元。因此,递归调用的层次越多,同名变量所占用的存储单元也就越多。当本次调用的函数运行结束时,系统将释放本次调用时所占用的存储单元,程序的执行流程返回到上一层的调用点,同时取当初进入该层时函数中的变量和形参所占用的存储单元中的数据。这样做,势必增加时间开销。

  • 实用建议:能用递推的地方优先用递推(本题递推版是 O(n),递归版是指数级时间 O(1.618ⁿ),n = 40 时递归版会明显变慢);递归适合描述结构上天然递归的问题(如汉诺塔、树的遍历、快速排序、选择排序)

【类似练习】用递归求 1 + 2 + 3 + … + n(对照 6_8.cpp 的写法:递归边界是 n = 1 时返回 1):

// 程序名:rsum.cpp
// 主要功能:用递归求 1+2+…+n
#include <iostream>
using namespace std;
 
int sum (int n)
{
    if (n == 1) return 1;            // 递归边界
    else return n + sum(n - 1);      // 递归调用
}
 
int main()
{
    int n;
    cout << "请输入 n:";
    cin >> n;
    cout << "1+2+...+" << n << " = " << sum(n) << endl;
    return 0;
}

运行结果:

$ g++ -o rsum rsum.cpp && ./rsum
请输入 n:100
1+2+...+100 = 5050

在 C 语言中,函数具有强大的功能,其中库函数更是重要,因为我们可以通过调用库函数使程序变得简单明了。使用库函数需要添加相应的头文件。下面请上机操作如下的两个程序(P95)。

【思考 6.1】编译并运行如下程序,根据运行结果判断 abs(number) 的功能是否为“返回参数 num 的绝对值”:

#include <iostream>
#include <cmath>                     // 教材写作 <math.h>
using namespace std;
 
int main(void)
{
    int number = -1234;
    cout << "number: " << number << " absolute value: " << abs(number) << endl;
    return 0;
}

运行结果:

$ g++ -o abs_demo abs_demo.cpp && ./abs_demo
number: -1234 absolute value: 1234
  • 结论:abs(num) 的功能是返回参数 num 的绝对值 ✔
  • Linux 提示:在 C++ 中 abs() 既可以用于整数(<cstdlib>)也可以用于浮点(<cmath> 中的重载版本);教材用的是 C 的函数原型 int abs(int x)。如果只写 #include <iostream> 而调用 abs(),g++ 下可能会报 ‘abs’ was not declared in this scope

【思考 6.2】编译并运行如下程序,根据运行结果判断 sqrt(num) 的功能是否为“返回参数 num 的平方根”,并注意 num 为负时的情况:

#include <iostream>
#include <cmath>                     // 教材写作 <math.h>
using namespace std;
 
int main(void)
{
    double x = 4.0, result;
    result = sqrt(x);
    cout << "The square root of " << x << " is " << result << endl;
    return 0;
}

运行结果:

$ g++ -o sqrt_demo sqrt_demo.cpp && ./sqrt_demo
The square root of 4 is 2
  • 结论:sqrt(num) 的功能是返回参数 num 的平方根;如果 num 为负,会产生域错误(教材原文:如果 num 为负,产生域错误)。在 Linux 下把 x 改成 −4.0,函数返回 NaN(-nan),并且不会像 VC 那样弹“域错误”对话框——g++ 下的处理是安静地返回 NaN
  • 其他库函数的内容请参考教材附录 D

【实训 6.1】程序任务是计算 1~8 之间各个自然数的阶乘,但程序有错误,请上机分析并改正程序中的错误(教材原程序 P96):

#include <iostream>
sing namespace std;              // 错误 1:拼写错误,应为 using
int p;                           // 错误 2:全局变量 p 与下面的函数 p 同名,冲突
int main()
{
    int n = 0;
    for (n = 1; n <= 8; n = n + 1)
    {
        cout << n << "!=" << p(n) << endl;   // 错误 3:函数 p 在使用前没有声明
    }
    return 0;
}
int p (int)                      // 错误 4:形参没有名字,函数体内也无法使用这个参数
{
    int k, s = 1;
    for (k = 1; k <= n; k = k + 1)       // 错误 5:这里的 n 来路不明
        s = s * k;
    return s;
}

改正后的程序(Linux 下可直接运行):

// 程序名:p_fact.cpp
// 主要功能:计算 1~8 的阶乘(实训 6.1 改错)
#include <iostream>
using namespace std;
 
int p (int n);                   // 先声明函数,形参必须命名
 
int main()
{
    for (int n = 1; n <= 8; n = n + 1)
    {
        cout << n << "!=" << p(n) << endl;
    }
    return 0;
}
 
int p (int n)                    // 用形参 n 控制求多少个数的连乘
{
    int k, s = 1;
    for (k = 1; k <= n; k = k + 1)
        s = s * k;
    return s;
}

运行结果:

$ g++ -o p_fact p_fact.cpp && ./p_fact
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320

【实训 6.2】一个糊涂人写了 n 封信和 n 个信封,到了邮寄的时候,把所有的信都装错了。设 Dₙ 为 n 封信装错时可能的种类数,可用递推公式表示为:

D(n) = (n-1) * (D(n-1) + D(n-2))     当 n > 2
D(n) = 1                             当 n = 2
D(n) = 0                             当 n = 1

试编程通过输入 n 计算 Dₙ 的值。解题思路:由于题目给出了递推公式,只需按照公式进行递推计算即可。

参考程序(递推实现,Linux 下可直接运行):

// 程序名:denv.cpp
// 主要功能:装错信封问题(递推)
#include <iostream>
using namespace std;
 
int main()
{
    int n, i;
    long d1 = 0, d2 = 1, d = 0;      // d1 表示 D(n-2),d2 表示 D(n-1)
    cout << "请输入信封数 n:";
    cin >> n;
    if (n == 1) d = 0;
    else if (n == 2) d = 1;
    else
    {
        for (i = 3; i <= n; i++)
        {
            d = (i - 1) * (d1 + d2); // 按公式递推
            d1 = d2;                 // 滚动更新
            d2 = d;
        }
    }
    cout << n << " 封信全部装错的情况共有 " << d << " 种" << endl;
    return 0;
}

运行结果:

$ g++ -o denv denv.cpp && ./denv
请输入信封数 n:5
5 封信全部装错的情况共有 44 种

【实训 6.3】输入一个整数 a(a < 32767),用一个长整型变量存放,求该数每一位数字的和。例如:输入 32423,首先分解成 3、2、4、2、3,然后再相加得 14 输出。

解题思路:通过一个自定义函数将整数求余分解,返回每位数,通过主函数相加求和。(提示:实现的本质仍是“取最低位 % 10、去掉最低位 / 10“这两步不断重复——与 6.2 节递推的”重复简单运算”是一个道理。)

参考程序:

// 程序名:digitsum.cpp
// 主要功能:求整数各位数字之和(自定义函数 + 主函数相加)
#include <iostream>
using namespace std;
 
int sumdigit (long a)            // 分解并累加各位数字
{
    int s = 0;
    while (a > 0)
    {
        s = s + a % 10;          // 取最低位累加
        a = a / 10;              // 去掉最低位
    }
    return s;                    // 返回各位数字之和
}
 
int main()
{
    long a;
    cout << "请输入一个整数:";
    cin >> a;
    cout << "各位数字之和为:" << sumdigit(a) << endl;
    return 0;
}

运行结果:

$ g++ -o digitsum digitsum.cpp && ./digitsum
请输入一个整数:32423
各位数字之和为:14

【实训 6.4】有 5 个人 A、B、C、D、E 坐在一起,好事者问 A 多少岁?A 说自己比 B 大 2 岁。问 B,B 说自己比 C 大 2 岁。问 C,C 说自己比 D 大 2 岁。问 D,D 说自己比 E 大 2 岁。最后,问 E,E 说 10 岁了。问 A 多大?

解题思路:显然这是一个递归问题,根据题意可以得到以下关系:

age[5] = age[4] + 2
age[4] = age[3] + 2
age[3] = age[2] + 2
age[2] = age[1] + 2
age[1] = 10

写成一般式表示为:

age(n) = 10               当 n = 1
age(n) = age(n-1) + 2     当 n > 1

参考程序:

// 程序名:age.cpp
// 主要功能:用递归计算 A 的年龄
#include <iostream>
using namespace std;
 
int age (int n)
{
    if (n == 1) return 10;           // 递归边界:E 为 10 岁
    else return age(n - 1) + 2;      // 前一个人比自己大 2 岁
}
 
int main()
{
    cout << "A 的年龄是 " << age(5) << " 岁" << endl;
    return 0;
}

运行结果:

$ g++ -o age age.cpp && ./age
A 的年龄是 18 岁
  • (1)使用函数是使程序实现模块化的重要思想,让每个函数完成一个确定的独立的任务,这样做,程序结构清晰、易读、易于调试、易于修改和维护。
  • (2)函数调用存在主从关系,主函数调用其他函数的目的,是让被调用函数完成某个计算或操作任务;如为计算则要给主函数返回一个计算出来的值,如为操作则不返回数据。有调用就要有返回,在被调用函数末尾有一条 return 语句,是一个值得提倡的好习惯。
  • (3)函数中的形式参数属于局部变量,作用域限定在函数体内。在一个函数调用另一个函数时,实际参数是一个具有确定值的表达式,实际参数的类型与个数,要与形式参数完全一致,且需一一对应。
  • (4)递归思想是算法设计的有力工具,对于拓展编程思路非常有效。学习和会用与或节点图对编写递归程序十分有用。

【试题 1】以下函数值的类型是。

fun (float x)
{
    float y;
    y = 3 * x - 4;
    return y;
}

A. int  B. 不确定  C. void  D. float

答:D。函数的类型由 return 语句中表达式的类型决定,这里返回的是 float 型变量 y,因此函数是 float 型。 Linux 提示:这份代码没有写返回类型,在 g++ 下会直接编译报错(ISO C++ forbids declaration of 'fun' with no type),必须先写成 float fun (float x)。

【试题 2】有以下程序:

void f (int v, int w)
{
    int t;
    t = v; v = w; w = t;
}
 
main()
{
    int x = 1, y = 3, z = 2;
    if (x > y)      f(x, y);
    else if (y > z) f(y, z);
    else            f(x, z);
    cout << x << "," << y << "," << z << endl;
}

执行后输出结果是。A. 1,2,3  B. 3,1,2  C. 1,3,2  D. 2,3,1

答:C(1,3,2)。x = 1、y = 3、z = 2,x > y 为假;y > z(3 > 2)为真,于是进入 f(y, z)。函数 f 把收到的两个值交换了一下,但交换的只是形参 v、w 这两个副本(6.1.4 讲的“传值调用是单向传递”),主函数里的 x、y、z 一个都没变,因此输出 1,3,2。 Linux 补充:在 g++ 下这段程序还要补上 #include <iostream>、using namespace std;,并把 main() 写成 int main(),否则无法通过编译。想让函数真正交换两个变量,必须传地址(引用或指针):

void swap2 (int &v, int &w)      // 引用作形参:形参就是实参的别名
{
    int t = v; v = w; w = t;
}

【试题 3】以下程序运行后的输出结果是。

void Fun (int x, int y)
{
    x = x + y;
    y = x - y;
    x = x - y;
    cout << x << "," << y << endl;
}
 
main()
{
    int x = 2, y = 3;
    Fun (x, y);
    cout << x << "," << y << endl;
}

答:Fun 内用“和差法”完成了交换——x = 2+3 = 5,y = 5−3 = 2,x = 5−2 = 3,所以函数内输出 3,2;但因为值传递,主函数中 x、y 仍是 2、3,接着输出 2,3。程序运行结果为:

3,2
2,3

【试题 4】若已经定义的函数有返回值,则以下关于该函数调用的叙述中错误的是。

  • A. 函数调用可以作为一个独立的语句存在
  • B. 函数调用可以作为一个函数的实参
  • C. 函数调用可以出现在表达式中
  • D. 函数调用可以作为一个函数的形参

答:D。函数调用的结果是一个值,它可以独立成句(A)、可以当实参(B)、可以参与运算(C);但形参是“变量声明”,只能是变量名,不能写成函数调用。

【试题 5】有以下程序:

int a = 3;
main()
{
    int s = 0, a = 5;
    s += a++;
    cout << s;
}

程序运行后的输出结果是。A. 8  B. 10  C. 7  D. 11

答:按 6.1.8 讲的“局部变量与全局变量同名时,局部变量起作用“,主函数里用的是局部 a = 5;s += a++ 是”先用后加”:先把 5 累加给 s(s = 5),再让 a 自增为 6。因此在 g++ 下实际输出 5。 需要说明的是:教材本题只给了 A、B、C、D 四个选项(8/10/7/11),其中没有 5,属于题干与选项不匹配(选项可能是按“局部变量 a 初值为 8”之类的另一种版本设计的)。遇到这类题最可靠的办法是上机跑一遍:

$ g++ -o t5 t5.cpp && ./t5
5

【试题 6】有以下程序:

int fun (int x, int y)
{
    return (x + y);
}
 
main()
{
    int a = 2, b = 5, c = 8;
    cout << fun( (int) fun(a + c, b), a - c);
}

程序运行后的输出结果是。A. 编译错误  B. 9  C. 21  D. 9.0

答:B(9)。分析步骤(自内向外):

  1. 先算内层 fun(a + c, b):a + c = 2 + 8 = 10,fun(10, 5) = 15;
  2. 再取整 (int)15 = 15(本题类型本来就一致,取整不起作用);
  3. 再算第二个实参 a - c = 2 − 8 = −6;
  4. 最后 fun(15, -6) = 15 + (−6) = 9。

这题考的就是 6.1.4“实参的个数与类型要与形参一致、前后对应关系不变”和 6.1.7“函数调用可以出现在表达式中,返回值参与运算”。

1.教材 VC 6.0 的操作 → Linux 终端的两条命令

  • 新建源文件:vim 6-1.cpp(或用任意编辑器创建 .cpp 文件)
  • 只编译、不链接(生成 6-1.o):g++ -c 6-1.cpp
  • 编译链接并运行:g++ -o 6-1 6-1.cpp 然后 ./6-1
  • 多个源文件组成一个工程:g++ -o main main.cpp comp.cpp
  • 出错信息:终端里直接显示 文件名:行号: 错误信息,不再弹出错误列表窗口
  • 程序结束:直接回到命令提示符,没有 Press any key to continue

2.教材中的 VC 写法 → 标准 C++ 写法

  • 教材的 #include <iostream.h> → 改成 #include <iostream>,并加一行 using namespace std;
  • 教材的 #include <cmath.h> 或 <math.h> → 改成 #include <cmath>
  • main() { … } → 改成 int main() { … return 0; }
  • 用了 setw() 却只包含 iostream → 额外加 #include <iomanip>
  • 用 float 存小数 → 建议改 double,精度更高
  • 数学函数链接错误 → 编译命令末尾加 -lm(现代 g++ 一般不需要)
  • 程序卡住不动 → 按 Ctrl+C 终止

3.教材错误信息 → g++ 错误信息对照

  • 教材的 error C2065: 'a': undeclared identifier → g++ 的 error: 'a' was not declared in this scope:用了别的函数里的局部变量(见 6-6.cpp 第 29 行)
  • 教材的 error C2143: syntax error → g++ 的 error: expected ';' before … token:漏了分号(函数声明、结构体定义结尾最常见)
  • 教材的“未包含头文件导致函数未定义” → g++ 的 error: 'setw' was not declared in this scope:忘了 #include <iomanip>(见 6-7.cpp)
  • 教材的“类型不匹配” → g++ 的 error: invalid conversion from 'double' to 'int':实参与形参类型不一致(6.1.4 强调过)
现象 原因 正确做法
编译报“未声明” 自定义函数写在了 main 之后却没有声明 在 main 之前写 float comp(float a,float b);
编译报“未声明”的函数是 setw/setprecision 忘了 #include <iomanip> 补上头文件(教材 6_7.cpp 的坑)
调用函数后主函数里的变量没变 传值调用是单向的,改的是形参副本 用引用 int &w 或指针作形参
实参个数/类型对不上 调用与定义的形参表不一致 个数、类型一一对应,顺序不可乱
函数里用了主函数的变量 局部变量只在函数体内有效 通过参数传入、通过 return 传出
全局变量与局部变量同名时结果出乎意料 同作用域内局部变量屏蔽全局变量 避免同名,或尽量不用全局变量
递归程序“算不出来”或很慢 递归边界写错/重复计算太多 先写清楚的递归边界(如 n==0),能递推就别递归
cout « n « “!=” « p(n) 报错 函数 p 未声明/形参没命名 先声明,形参必须命名并使用它
递推结果越来越离谱 f1 = f2; f2 = f3; 三句顺序写反 严格按“先算 f3,再滚动 f1、f2”的顺序写
求 “1~8 的阶乘” 结果溢出 用 int/float 存阶乘 8! = 40320 尚可,更大的阶乘要用 long long

本页内容全部来自教材 **第 6 章《函数、递推与递归》(P76~P99)**及第 7 章章首页(P100),对应 PDF 物理页 98~122;第 7 章正文(数组、排序、结构、二维数组等)见下一节点。

mdk height=480 color=#0f766e # 第6章 函数、递推与递归 ## 6.1 函数 - 库函数与自定义函数 - 形参、实参、返回值 - 全局变量与局部变量 ## 6.2 递推 - 由已知项推出未知项 - 非波那契数列 ## 6.3 递归 - 或节点、与节点、递归边界 - 递归求 n! ## 6.4 知识拓展 - abs 与 sqrt ## 6.5 思考与实训 - 阶乘改错、装错信封、数字之和、年龄 ## 6.6 小结 ## 6.7 知识巩固 - 试题 1 到 6 ## Linux 上机要点 - g++ -o 程序名 源文件.cpp - iostream.h 改 iostream - setw 需要 iomanip

该主题尚不存在

您访问的页面并不存在。如果允许,您可以使用创建该页面按钮来创建它。

  • 程序设计基础/第6章.1791299116.txt.gz
  • 最后更改: 2026/10/06 23:05
  • 由 张叶安