算法设计与分析实验报告(完整代码) |
您所在的位置:网站首页 › 算法分析的主要内容包括哪些方面 › 算法设计与分析实验报告(完整代码) |
实验一 分治法求众数问题(或…)
一、实验目的
掌握递归与分治方法的基本设计思想与原则,学会递归技术编程技巧。 二、实验内容 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 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |