讲义

课后作业

2024/1/26

# 第十三课

# 1. 编写一个 C++程序，返回斐波那契数列的第n项值（递归算法）

// 示例输入
7
// 示例输出:
13
  • ✅
  • 历史解析
    • 题解思路正确，本题主要考察斐波那契数列定义以及不使用循环迭代而使用递归解决的完成思路，没有问题💯

# 2. 请将fileIn.txt的文件内容使用冒泡排序算法进行升序排序，完成后将排序完毕的内容生成fileOut.txt文件，要求与fileIn.txt格式相同

附件：fileIn.txt (opens new window)

// 示例文件输出:
1
2
3
4
5
5
6
7
8
9
  • ❌
  • 参考解析
    • 本题主要考查使用freopen重定向标准流操作文件，冒泡排序算法
    • 思路：获取文件信息后将数值存储到数组中，并使用冒泡排序算法进行排序，最后输出至生成文件
    • 注意点：
      • 读取与写入时需要考虑文件内容带换行
      • 创建接收数组时，对于初始长度不知，需考虑使用vector及其相关方法亦或是通过多遍读取文件来处理长度与输入

# 3. 编写一个 C++ 函数，输入a,b后，使用欧几里得算法来计算三个值：两个整数a和b的最大公约数，并找出整数x和y，使得ax + by = gcd(a, b)即ax+by=（你求出的最大公约数）

// 示例输入
a = 35, b = 15
// 示例输出:
GCD = 5, x = 1, y = -2 //请注意，`x`和`y`可能有多组解，展示符合的一组即可
  • ✅
  • 历史解析
    • 题解思路正确，本题主要考欧几里得算法以及对于递归边界处理的完成思路，没有问题💯
    • 对于此题的解法，我们根据欧几里得算法的边界条件进行倒推即可，即gcd(a, b) b等于0时a即为最大公约数,那么此时我们设置符合题意的x y初始值即可，之后递归迭代时符合公式ax + by = gcd(a, b)便可找出其对应的x y，因为x y的迭代是一直符合条件的

# 4. 假设你在爬楼梯，楼梯共有 n 阶。每次你可以爬 1 阶或 2 阶。编写一个函数，使用递归的方式来计算有多少种不同的方法可以爬到楼顶

// 示例输入
n = 5
// 示例输出:
8

  • ❌

  • 历史解析

    • 从题目中不难看出这是一道斐波那契数列简单变形题
    • 题目要求使用递归求解，而你的解法是使用了循环迭代

  • 参考答案

#include <iostream>
using namespace std;

int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

int main() {
    int n;
    cout << "n = ";
    cin >> n;
    cout << climbStairs(n) << endl;
    return 0;
}

# 5. 编写一个 C++程序，使用冒泡排序算法对一个整数数组进行排序。数组的大小和元素应由用户输入。除了实现基本的冒泡排序外，程序还需要提供以下功能：

  1. 计数比较和交换次数： 在排序过程中，计算比较和交换操作的次数，并在排序完成后将这些数据输出。
  2. 优化检测： 实现一种机制来检测数组在排序过程中是否已经完成排序。如果在某一轮排序中没有发生任何交换，则提前结束排序。
  3. 输出每轮排序的结果： 在每一轮冒泡过程结束后，输出当前数组的状态，以便观察排序的进度。

小提示：注意观察示例中输出项第二轮排序和第三轮排序，他们的打印是相同的，这便是你判断当前数组是否完成全部排序的条件(即优化检测)，那么我们是需要每次都去比较上一轮排序的结果么？思考一下

// 示例输入
请输入数组大小: 5
请输入数组元素: 34 22 45 27 31
// 示例输出:
第 1 轮排序后的数组：22 34 27 31 45
第 2 轮排序后的数组：22 27 31 34 45
第 3 轮排序后的数组：22 27 31 34 45
比较次数: 9
交换次数: 5
排序后的数组: 22 27 31 34 45

  • ❌

  • 历史解析

    • 题解思路正确，但打印与题目要求以及示例输出不一致
    • 计数比较和交换次数：使用局部变量来在对的位置插入即可记录
    • 优化检测：当一轮子循环后都没有进入条件语句，说明此排序已经结束了，那么就跳出总循环即可
    • 输出每轮排序的结果：在跳出之前打印即可，跳出后即终止循环，那么之前的循环都是他所经历的，需要打印

  • 参考答案

#include <iostream>
#include <vector>
using namespace std;

void printArray(const vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    int totalComparisons = 0, totalSwaps = 0;
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            totalComparisons++;
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
                totalSwaps++;
            }
        }
        // 打印每轮排序后的数组状态
        cout << "第 " << i + 1 << " 轮排序后的数组：";
        printArray(arr);
        if (!swapped) {
            break;
        }
    }
    cout << "总共比较次数: " << totalComparisons << endl;
    cout << "总共交换次数: " << totalSwaps << endl;
}

int main() {
    int size;
    cout << "输入元素的个数: ";
    cin >> size;
    vector<int> arr(size);
    cout << "输入 " << size << " 个整数:" << endl;
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }
    bubbleSort(arr);
    cout << "排序后的数组: ";
    printArray(arr);
    return 0;
}
上次更新: 2024-10-19 10:01:51

第十四课