# 算法设计与分析 **Repository Path**: ruofan-daimacangku/algorithm-design-and-analysis-experiments ## Basic Information - **Project Name**: 算法设计与分析 - **Description**: To save and display my Algorithm homework - **Primary Language**: C - **License**: MulanPSL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2025-04-01 - **Last Updated**: 2025-06-10 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 算法设计与分析 ## 实验（一）实现快速排序算法 - 实验目的 - （1）掌握常见的排序算法的基本原理、基本设计流程； - （2）掌握简单的冒泡排序、快速排序算法的时间复杂度分析； - （3）掌握简单的冒泡排序、快速排序算法的空间复杂度分析； - 实验内容 - （1）设计利用递归与分治策略设计简单的冒泡排序、快速排序算法； - （2）设计具有数据输入、处理和输出功能的快速排序算法，实现算法的编译和运行，记录实验过程并整理实验结果。 - 实验要求 - （1）能够独立完成快速排序算法的设计、分析和实现，正确掌握求解算法的设计思路 以及程序调测等相关知识，最终形成分析和求解问题的工程实践能力； - （2）记录本实验的设计思路、设计过程、调试流程，能正确地分析实验结果并得出结论，撰写格式规范、组织合理、内容充实的实验报告。 - 支撑的课程目标 - 可以支撑课程目标 2 和课程目标 3。 - 针对特定需求进行简单的冒泡排序、快速排序算法的设计与编程，掌握递归与分治的设 计原理和方法，利用现有软件开发平台实现相应的算法，通过调试、测试及运行结果分析， 找到好的解决方案。 ## 实验（二）用递归与分治法实现元素的二分查找 - 实验目的 - （1）掌握递归与分治策略求解问题的基本原理、基本设计流程； - （2）掌握递归与分治算法的时间复杂度分析； - （3）掌握递归与分治算法的空间复杂度分析； - （4）掌握二分查找/折半排序算法。 - 实验内容 - （1）设计利用递归与分治策略设计出二分查找算法； - （2）设计具有数据输入、处理和输出功能的二分查找算法，实现算法的编译和运行， 记录实验过程并整理实验结果。 - 实验要求 - （1）能够独立完成二分查找算法的设计、分析和实现，正确掌握求解算法的设计思路 以及程序调测等相关知识，最终形成分析和求解问题的工程实践能力； - （2）记录本实验的设计思路、设计过程、调试流程，能正确地分析实验结果并得出结 论，撰写格式规范、组织合理、内容充实的实验报告。 - 支撑的课程目标 - 可以支撑课程目标 2 和课程目标 3。 - 针对特定需求进行二分查找算法的设计，掌握递归与分治算法的设计原理和方法，利用 现有软件开发平台实现相应的算法，通过调试、测试及运行结果分析，找到较好的解决方案。 ## 实验（三）二分查找算法的改进 - 实验目的 - （1）进一步掌握递归与分治策略求解问题的基本原理、基本设计流程； - （2）进一步掌握二分查找/折半排序算法。 - 实验内容 - （1）设计出二分查找算法的改进版； - （2）设计具有数据输入、处理和输出功能的二分查找算法的改进版，实现算法的编译 和运行，记录实验过程并整理实验结果。 - 实验要求 - （1）能够独立完成二分查找算法的设计、分析和实现，正确掌握求解算法的设计思路 以及程序调测等相关知识，最终形成分析和求解问题的工程实践能力； - （2）记录本实验的设计思路、设计过程、调试流程，能正确地分析实验结果并得出结 论，撰写格式规范、组织合理、内容充实的实验报告。 - 支撑的课程目标 - 可以支撑课程目标 2 和课程目标 3。 - 针对特定需求进行二分查找算法的基本版和改进版设计，掌握递归与分治算法的设计原 理和方法，利用现有软件开发平台实现相应的算法，通过调试、测试及运行结果分析，找到 较好的解决方案。 ## 实验（四） 最大子段和 - 问题描述Description: 给定有n个整数(可能为负整数)组成的序列a1 ,a2, ..., an,求该序列连续的子段和的最大值。 如果该子段的所有元素和是负整数时定义其最大子段和为0。 - Input: 第一行有一个正整数n(n<1000)，后面跟n个整数,绝对值都小于10000。直到文件结束。 - Output: 输出它的最大子段和。 - Sample Input：6 -2 11 -4 13 -5 -2 - Sample Output：24 - 解决该问题有很多方法，可以通过暴力、分治、动态规划。本实验运用分治和动态规划的方法来解决该题目。 ## 实验（五）基于多段图问题的动态规划算法设计 ![输入图片说明](%E5%9B%BE%E7%89%87/%E5%AE%9E%E9%AA%8C5.png) - 实验目的 - （1）掌握动态规划策略求解问题的基本原理、基本设计流程。 - （2）能够利用合适的数据结构去表示求解问题的数据输入与输出，实现该数据结构。 - （3）能够利用蛮力法求解多段图问题，具有设计并实现该算法的能力。 - （4）能够利用动态规划策略求解多段图问题，具有设计并实现该算法的能力。 - （5）分析与总结重叠子问题在该实验中的特点、应用、作用。 - （6）理解动态规划策略求解多段图问题的时间复杂度分析； - （7）理解动态规划策略求解多段图问题的空间复杂度分析； - 实验内容 - 利用动态规划策略设计具有数据输入、处理和输出功能的多段图规划问题：求源点 S 到汇点 T 的最小成本路径的求解算法，实现算法的编译和运行，记录实验过程并整理实验 结果。根据原理图，连接实验线路。 - 实验要求 - （1）能够独立完成多段图规划问题的动态规划算法的设计、分析和实现，正确掌握求 解算法的设计思路以及程序调测等相关知识，最终形成分析和求解问题的工程实践能力； - （2）记录本实验的设计思路、设计过程、调试流程，能正确地分析实验结果并得出结 论，撰写格式规范、组织合理、内容充实的实验报告。 - 支撑的课程目标 - 可以支撑课程目标 2 和课程目标 3。 - 为计算多段图规划问题的最优解进行动态规划算法设计，并对设计方案和流程的可行 性、算法的时间空间复杂度进行分析，利用现有软件开发平台实现相应的算法设计，通过调 试、测试及运行结果分析，找到有效的解决方案。 ## 实验（六）用贪心算法求解最小生成树 - Prim 算法和 Kruskal 算法 - 实验目的 - （1）掌握贪心方法求解问题的基本原理、基本设计流程； - （2）掌握贪心方法求解最小生成树问题的 Prim 算法和 Kruskal 算法，具有设计并实现 该算法的能力。 - 实验内容 - 利用贪心策略设计具有数据输入、处理和输出功能的最小生成树算法，包括两种不同方 式：Prim 算法和 Kruskal 算法，实现算法的编译和运行，记录实验过程并整理实验结果。 - 实验要求 - （1）能够独立完成利用贪心策略求解最小生成树问题的 Prim 算法和 Kruskal 算法设计、 分析和实现，正确掌握求解算法的设计思路以及程序调测等相关知识，最终形成分析和求解 问题的工程实践能力； - （2）记录本实验的设计思路、 设计过程、调试流程，能正确地分析实验结果并得出结 论，撰写格式规范、组织合理、内容充实的实验报告。 - 支撑的课程目标 - 可以支撑课程目标 2 和课程目标 3。 - 为了求解最小生成树问题而设计贪心算法，包括 Prim 算法和 Kruskal 算法，并对设计 方案和流程的可行性、算法的时间空间复杂度进行分析，利用现有软件开发平台实现相应的 算法设计，通过调试、测试及运行结果分析，分析和评价最小生成树贪心算法的效率。 ## 实验（七）用回溯法求解 0-1 背包问题 - 实验目的 - （1）掌握回溯法求解问题的基本原理、基本设计流程； - （2） 掌握利用回溯法求解 0-1 背包问题任意解的方法，具有设计并实现相应算法； - （3）掌握对回溯算法进行效率分析的基本方法。 - 实验内容 - （1）熟悉实验环境，掌握回溯法求解 0-1 背包问题任意解的算法原理； - （2）利用回溯法设计具有数据输入、处理和输出功能的 0-1 背包问题求解算法，实现 算法的编译和运行，记录实验过程并整理实验结果； - （3）编写算法实现对 0-1 背包问题求解，基于回溯法的效率评估。 - 实验要求 - （1）能够独立完成求解 0-1 背包问题任意解算法的设计、分析和实现，正确掌握求解 算法的设计思路以及程序调测等相关知识，最终形成分析和求解问题的工程实践能力； - （2）记录本实验的设计思路、 设计过程、调试流程，能正确地分析实验结果并得出结 论，撰写格式规范、组织合理、内容充实的实验报告。 - 支撑的课程目标 - 可以支撑课程目标 2 和课程目标 3。 - 为了求解 0-1 背包问题而设计相应的回溯算法，并对设计方案和流程的可行性、算法 的时间空间复杂度进行分析，利用现有软件开发平台实现相应的算法设计，通过调试、测试 及运行结果分析，分析评价回溯算法求解实际问题的效率。 ## 实验（八）用分支限界法求解 0-1 背包问题 - 实验目的 - （1）掌握分支限界法求解问题的基本原理、基本设计流程； - （2）掌握利用分支限界法求解 0-1 背包问题，具有设计并实现相应算法； - （3）掌握对分支限界法进行效率分析的基本方法。 - 实验内容 - （1）熟悉实验环境，掌握分支限界法求解 0-1 背包问题任意解的算法原理； - （2）利用回溯法设计具有数据输入、处理和输出功能的 0-1 背包问题求解算法，实现 算法的编译和运行，记录实验过程、进行算法效率的合理评估，最后整理实验结果。 - 实验要求 - （1）能够独立完成求解 0-1 背包问题任意解算法的设计、分析和实现，正确掌握求解 算法的设计思路以及程序调测等相关知识，最终形成分析和求解问题的工程实践能力； - （2）记录本实验的设计思路、 设计过程、调试流程，能正确地分析实验结果并得出结 论，撰写格式规范、组织合理、内容充实的实验报告。 - 支撑的课程目标 - 可以支撑课程目标 2 和课程目标 3。 - 为了求解 0-1 背包问题而设计相应的分支限界法，并对设计方案和流程的可行性、算 法的时间空间复杂度进行分析，利用现有软件开发平台实现相应的算法设计，通过调试、测 试及运行结果分析，分析评价分支限界法求解实际问题的效率。