C++编程：调试、算法分析与继承的深入探讨

### C++编程：调试、算法分析与继承的深入探讨 #### 一、调试与递归练习 在编程过程中，我们常常会遇到程序崩溃的情况，比如出现 “segmentation fault” 或 “stack overflow” 错误。这通常是因为我们忘记了结束条件，或者程序没有朝着结束条件前进。使用调试器可以帮助我们找出问题所在。 接下来有一些递归相关的练习： 1. **斐波那契数列函数**：斐波那契数列的定义为 Fibonacci (1) = 1，Fibonacci (2) = 1，当 n > 2 时，Fibonacci (n) = Fibonacci (n - 1) + Fibonacci (n - 2)。我们需要使用递归编写斐波那契函数并进行测试。 2. **缩进函数**：编写并测试一个函数 `void indent (const char* what, int howMuch)`，该函数会在缩进 `howMuch` 个空格后打印字符串 `what`。如果 `howMuch` 为 0，则直接打印字符串；否则，打印一个空格并以 `howMuch - 1` 个空格调用自身。 3. **递归版的幂函数**：编写并测试递归版本的 `pow` 函数，`pow (a, b)` 返回 `a` 的 `b` 次幂。 4. **递归对数函数**：编写并测试一个递归函数 `log`，给定一个正整数 `number` 和一个整数 `base`，返回以 `base` 为底 `number` 的对数。这里的对数定义为将 `number` 除以 `base` 直到得到 1 的次数。 #### 二、算法分析与 O 符号 在算法设计中，我们需要考虑算法的效率。有时候，一个算法看起来可行，但实际上可能效率极低。例如，对一个名字列表进行排序，如果我们生成所有可能的排列，直到找到一个完全有序的排列，这种方法的复杂度会非常高。假设有 N 个元素，可能的排列数为 N!，当 N = 100 时，这个数字是 10^158，计算机的速度是无法承受的。 为了简化对算法时间要求的描述，我们使用 O 符号来评估算法。O 符号的简化规则如下： - 当数据集很大时，如果一个加数明显小于另一个加数，则丢弃较小的加数。例如，对于 1 + 3N，丢弃 1 得到 3N。 - 丢弃常数乘数。例如，3N 变为 N。 以下是一些不同算法复杂度的例子： | 算法描述 | 复杂度分析 | | --- | --- | | 读取 N、M、P，相加后除以 3 并打印平均值 | 每个操作执行 1 次，共 6 次操作，丢弃常数乘数后复杂度为 O(1)，即常数时间 | | 遍历数组，将负数变为正数 | 遍历数组 N 次，每次操作复杂度为 O(1)，整体复杂度为 O(N)，即线性时间 | | 冒泡排序 | 每次遍历数组复杂度为 O(N)，最坏情况下需要 N - 1 次遍历，复杂度为 O(N^2)，即二次时间 | 我们通常希望避免复杂度为 O(2^N) 的指数时间算法。 同时，还有一些关于 O 符号复杂度计算的练习： 1. 计算返回数组中最小数字的函数的时间复杂度。 2. 计算判断一个单词是否为回文的函数的时间复杂度。 3. 计算打印 NxN 网格中所有元素的函数的时间复杂度。 4. 编写一个函数 `intersection`，找出两个数组中的公共元素并放入新数组，计算该函数的时间复杂度。 5. 编写冒泡排序并验证其正确性。 6. 使用埃拉托斯特尼筛法编写一个程序，找出小于某个限制的所有素数，并计算其时间复杂度。 7. 计算前面递归练习中部分函数的时间复杂度。 #### 三、继承的基础与应用 继承是 C++ 中实现代码复用的重要机制。以员工记录为例，我们定义了 `Employee` 类，包含员工的基本信息，如姓名、入职日期、工资等。 ```cpp //Class Employee // -- from _C++ for Lazy Programmers_ #ifndef EMPLOYEE_H #define EMPLOYEE_H #include <iostream> #include <string> #include "date.h" class Employee { public: Employee () {} Employee (const Employee&) = delete; Employee (const std::string& theFirstName, const std::string& theLastName, const Date& theDateHired, int theSalary); const Employee& operator= (const Employee&) = delete; void print(std::ostream&) const; //access functions const std::string& firstName () const { return firstName_; } const std::string& lastName () const { return lastName_; } const Date& dateHired () const { return dateHired_; } int salary () const { return salary_; } bool isOnPayroll () const { return isOnPayroll_; } int badPerformanceReviews () const { return badPerformanceReviews_; } void quit () { isOnPayroll_ = false;} void start () { isOnPayroll_ = true; } void meetWithBoss () { ++badPerformanceReviews_; } private: std::string firstName_, lastName_; Date dateHired_; int salary_; bool isOnPayroll_; int badPerformanceReviews_; }; inline std::ostream& operator<< (std::ostream& out, const Employee& foo) { foo.print (out); return out; } #endif //EMPLOYEE_H ``` 并非所有员工都是相同的，例如经理除了拥有员工的基本信息外，还具有额外的特征，如招聘和解雇员工的权力等。为了避免重复编写代码，我们可以让 `Manager` 类继承自 `Employee` 类。 ```cpp //Class Manager // -- from _C++ for Lazy Programmers_ #ifndef MANAGER_H #define MANAGER_H #include "employee.h" using Meeting = std::string; class Manager: public Employee { public: Manager (); Manager (const Manager&) = delete; Manager (const std ```