| 算法设计与分析实验报告（完整代码） | 您所在的位置：网站首页 › 实验报告的实验步骤怎么写的 › 算法设计与分析实验报告（完整代码） |
|
实验一 分治法求众数问题（或…）
一、实验目的
掌握递归与分治方法的基本设计思想与原则，学会递归技术编程技巧。 二、实验内容 1、问题描述给定含有n个元素的的集合S，求出集合S中的众数。 （或 在有序序列（r1,r2,…,rn）中求ri=i的元素） 2、实验要求学习分治求解的思想，并使用递归与分治的方法求解。 三、完整代码 1、求众数 #include #include #include using namespace std; // 定义一个函数，用于查找给定数组的众数 分治法 int findMode(const vector& nums, int left, int right) { // 如果左边界等于右边界，说明只有一个元素，直接返回该元素作为众数 if (left == right) { return nums[left]; } // 计算中间位置 int mid = left + (right - left) / 2; // 递归查找左半部分的众数 int leftMode = findMode(nums, left, mid); // 递归查找右半部分的众数 int rightMode = findMode(nums, mid + 1, right); // 创建一个映射count，用于统计每个元素出现的次数 map count; //通过遍历数组中的元素，将每个元素作为键，出现次数作为值，存储到映射中。 for (int i = left; i rightCount) { return leftMode; } else if (leftCount < rightCount) { return rightMode; } else { // 如果左右两部分众数出现次数相同，则返回较大的那个 return max(leftMode, rightMode); } } int main() { // 定义一个包含重复元素的数组 vector nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 1, 1, 2, 2, 3, 3, 3, 3 }; // 调用findMode函数查找众数，并将结果存储在变量mode中 int mode = findMode(nums, 0, nums.size() - 1); cout |
| CopyRight 2018-2019 实验室设备网 版权所有 |