以下为《《算法设计与分析》实验报告（模板）》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

江苏科技大学

算法设计与分析实验报告

（2022/2023学年第1学期）

学生姓名： 翟文轩

学生学号： ***4104

院 系： 计***

专 业： 计算机科学与技术专业

考核得分：

2022 年 11 月 25 日

项目1 分治法求众数问题

实验目的

掌握递归与分治方法的基本设计思想与原则，学会递归技术编程技巧。

实验内容

问题描述

给定含有n个元素的的集合S，求出集合S中的众数。

实验要求

学习分治求解的思想，并使用递归与分治的方法求解。

代码

#include

#include

#include

#include

using namespace std;

typedef long long ll;

typedef pairpi;

const int maxn = 1e5 + 100;

const int N = 1e6 + 100;

const int M = 1e5 + 100;

const int mod = 1e9 + 7;

int n, m, T;

int a[N];

int ans = 0; //众数的重数

int idx = 0; //众数的下标

void split(int l, int r) //分治算法

{

if (l > r)return;

int ll = l; //记录原来的l位置

int rr = r; //记录原来的r位置

int mid = (l + r) >> 1;

for (; l < mid && a[l] != a[mid]; l++); //寻找众数的最左边

for (; r > mid && a[r] != a[mid]; r--); //寻找众数的最右边

//经过两个for循环后，众数个数就是r-l+1

if (ans = ans) //剪枝

split(ll, l - 1); // 对左边部分分治

if (rr - r - 1 + 1 >= ans) //剪枝

split(r + 1, rr); // 对右边部分分治

}

void solve()

{

scanf_s("%d", &n);

for (int i = 0; i < n; i++)

scanf_s("%d", a + i);

sort(a, a + n); //先排序，方便统计众数个数

int l = 0;

int r = n - 1;

split(l, r); 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 timal solution is:"

以上为《《算法设计与分析》实验报告（模板）》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。