没有合适的资源?快使用搜索试试~ 我知道了~
算法分析与设计 期末大作业.doc
1星 需积分: 50 35 下载量 101 浏览量
2019-12-27
21:43:16
上传
评论 4
收藏 489KB DOC 举报
温馨提示
试读
27页
C语言版 算法分析与设计 期末大作业 西安电子科技大学 计算机学院 软件学院 C语言版 算法分析与设计 期末大作业 西安电子科技大学 计算机学院 软件学院 C语言版 算法分析与设计 期末大作业 西安电子科技大学 计算机学院 软件学院
资源推荐
资源详情
资源评论
1. 设计一个分治算法在给定的无序整数数组,设计实现一个分治算法,寻
找输入数据中的最大值,实现该分治算法,分析算法的时间复杂度。
/*
* 设计一个分治算法
* 在给定的无序整数数组,设计实现一个分治算法,
* 寻找输入数据中的最大值,实现该分治算法,分析算法的时间复杂度。
*/
int maxVale(int low,int high,int array[])
{
if (low==high) return array[low];
else
{
int mid = (low + high) / 2;
int left = maxVale(low, mid, array);
int right = maxVale(mid + 1, high, array);
int max = left > right ? left : right;
return max;
}
}
1. 设计实现一个分治算法,将给定数组形式存储的无序输入数据整理成一个
大顶堆。
/*
* 设计实现一个分治算法,将给定数组形式存储的无序输入数据整理成一个大顶堆。
*/
void Heapfy(int heap[],int item,int heapLength)
{
int length = heapLength;
int left = 2 * item + 1;
int right = 2 * item + 2;
int largest;
if ((left <= length - 1) && (heap[left] > heap[item])) {
largest = left;
} else {
largest = item;
}
if ((right <= length - 1) && (heap[right] > heap[largest])) {
largest = right;
}
if (largest != item) {
int temp = heap[item];
heap[item] = heap[largest];
heap[largest] = temp;
Heapfy(heap, largest,heapLength);
}
}
void build(int *heap,int heapLength) {
int length = heapLength;
int lastParent = (length - 2) / 2;
for (int item = lastParent; item >= 0; item--) {
Heapfy(heap, item,heapLength);
}
}
void buildHeapBegin()
{
int arrayTest[] = {1,2,22,33,44,21};
int arrayLength = sizeof(arrayTest)/sizeof(arrayTest[0]);
build(arrayTest,arrayLength);
for (auto i :arrayTest)
cout<<i<<endl;
}
结果:
2. 分别实现分治形式的归并算法及快速排序算法,随机产生一定数量的输入
数据,对两个算法的计算时间进行实际测试对比。
/*
* 分别实现分治形式的归并算法及快速排序算法,随机产生一定数量的输入数据,对
两个算法的计算时间进行实际测试对比。
*/
///< 分治-归并
void JYmerge(double *array, int left, int mid, int right, double *result) {
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (array[i] >= array[j]) {
result[k++] = array[j++];
} else {
result[k++] = array[i++];
}
}
while (i <= mid) {
result[k++] = array[i++];
}
while (j <= right) {
result[k++] = array[j++];
}
i = left;
k = 0;
while (i <= right) {
array[i++] = result[k++];
}
}
void JYmergeSort(double *array, int left, int right, double *result) {
if (left < right) {
int mid = (left + right) / 2;
JYmergeSort(array, left, mid, result);
JYmergeSort(array, mid + 1, right, result);
JYmerge(array, left, mid, right, result);//两个子问题序列合并
}
}
void JYmergeSort(double *array,int arrayLength) {
double result[arrayLength];
JYmergeSort(array, 0, arrayLength - 1, result);
}
///< 分治-快排
int JYpartition(double *array, int left, int right) {
int i = left;
int j = right;
while (i < j) {
while (i < j && array[i] <= array[j]) {
j--;
}
if (i < j) {
double temp = array[j];
array[j] = array[i];
array[i] = temp;
i++;
}
while (i < j && array[i] <= array[j]) {
i++;
}
if (i < j) {
double temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
return i;
}
void JYquickSort(double *array, int left, int right) {
if (left < right) {
int pivot = JYpartition(array, left, right);
JYquickSort(array, left, pivot - 1);
JYquickSort(array, pivot + 1, right);
}
}
void JYquickSort(double *array,int arrayLength) {
JYquickSort(array, 0, arrayLength - 1);
}
结果:
4.实现最大子数组的分治算法,将其实际运行效率与改进后的蛮力算法进行对
比分析。
/*
* 实现最大子数组的分治算法,将其实际运行效率与改进后的蛮力算法进行对比分析。
*/
int variation[10000];
void MaxSubarray(int *array,int arrayLength) {
for (int i = 0; i < arrayLength - 1; ++i) {
variation[i] = array[i + 1] - array[i];
}
}
//cross
int crossing(int *array, int left, int mid, int right) {
int temp_left = -99999;
int temp_right = -99999;
// 从 mid 向前求最大值
int sum = 0;
for (int i = mid; i >= left; --i) {
sum += array[i];
if (sum > temp_left) {
temp_left = sum;
}
}
// 从 mid+1 向后求最大值
sum = 0;
for (int j = mid + 1; j < right; ++j) {
sum += array[j];
if (sum > temp_right) {
temp_right = sum;
}
}
return temp_left + temp_right;
}
int divideConquer(int *array, int left, int right) {
if (left == right) {
return array[left];
} else {
int mid = (left + right) / 2;
int left_sum = divideConquer(array, left, mid);
int right_sum = divideConquer(array, mid + 1, right);
int cross_sum = crossing(array, left, mid, right);
剩余26页未读,继续阅读
资源评论
- 奔跑吧犀牛2021-06-17一些算法作业,仅有题目和代码,不是论文模式的大作业,仅仅是一些习题
- 孤影メ残刀2021-12-15不是论文,仅仅是代码
weixin_33691506
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- Windows 常见运行运行库32+64
- 基于3KW光伏并网单相逆变器设计(TMS320F28035控制板+显示板+STM32F103功率板)硬件(原理图+PCB)工程
- 正点原子HAL库 STM32F4 外部中断(学习自用附源码)
- delphi rzcombobox DropDownList 灰色背景改为白色
- sap sd.docsap sd.doc
- torch-1.10.2-cp38-cp38-win-amd64.whl
- 菜单栏实现增加数据,修改数据,查询数据,删除数据
- 全国省市区三级联动json文件,带code
- C8_全局&局部&static.zip
- Unity和安卓交互插件Unity调Android Native Goodies PRO
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功