山东大学计科3递归实验报告：全排列与子集生成

本篇文档是山东大学计算机科学与技术学院学生张愈博在2018年9月28日完成的一份数据结构与算法课程实验报告。实验的主题围绕递归编程展开，涉及两个部分：全排列和子集生成。 实验一：全排列递归练习 1. 实验目的： - 熟悉开发工具的使用，如DevCpp 5.11、Visual Studio 2017在Windows 10环境下的应用。 - 掌握递归算法实现，通过递归的方式对n个互不相同的整数进行全排列。使用递归策略，首先选取第一个数，然后对剩余n-1个数进行全排列，这是一种分治法的应用。 - 实现了一个通用算法，用于求解线性数组list[m:n]的全排列，提高了算法的实用性。 2. 实验内容： - 用户输入n和n个整数，程序输出这些整数的所有全排列。递归函数设计的关键在于正确处理基本情况（如n=1时返回单个数字）和递归情况（n>1时调用自身处理n-1个数字）。 实验二：子集生成递归练习 1. 实验目的： - 同样锻炼递归能力，通过生成n个整数的所有子集，利用递归生成0/1向量数组表示每个子集，当元素为0则跳过该整数，否则输出。 2. 实验内容： - 输入n个整数生成n维的0/1向量数组，通过递归判断数组元素来决定是否输出对应的整数。然而，实验过程中遇到了问题，即在输出过程中，list[0]的值被改变，初步怀疑可能与编译器有关。 3. 测试结果与分析： - 题目一运行正常，但在执行题目二时，遇到一个异常现象：在调用Sub_Generation函数前，list的元素显示正常，但在函数内部输出时，list[0]的值被temp数组覆盖，导致输出错误。经过代码检查未发现逻辑问题，推测可能是编译器优化或内存管理上的问题，需进一步排查。 总结： 这份实验报告展示了张愈博在递归算法方面的实践，包括全排列和子集生成两种典型递归应用场景。同时，也反映了他在遇到问题时的思考过程，显示出良好的问题解决能力。在今后的学习和开发工作中，理解递归的原理和熟练运用递归算法对于处理复杂数据结构和算法问题至关重要。同时，对编译器行为的了解也有助于识别和解决潜在的编程陷阱。