第1页 / 共27页
第2页 / 共27页
第3页 / 共27页
第4页 / 共27页
第5页 / 共27页
第6页 / 共27页
第7页 / 共27页
第8页 / 共27页
算法分析与设计 期末大作业.doc
1.设计一个分治算法在给定的无序整数数组，设计实现一个分治算法，寻找输入数据中的最大值，实现该分治算法，
1.设计实现一个分治算法，将给定数组形式存储的无序输入数据整理成一个大顶堆。
2.分别实现分治形式的归并算法及快速排序算法，随机产生一定数量的输入数据，对两个算法的计算时间进行实际测
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<
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);
return left_sum > cross_sum ? (left_sum > right_sum ? left_sum : right_sum)
: (cross_sum > right_sum ? cross_sum : right_sum);
}
}
///< 分治求解
int divideConquer() {
return divideConquer(variation, 0, 10000 - 1);
}
///< 蛮力求解
void bruteForce() {
int sum = 0;
int start = 0;
int end = 0;
for (int i = 0; i < 10000; ++i) {
int temp = 0;
for (int j = i; j < 10000; ++j) {
temp += variation[j];
if (temp > sum) {
sum = temp;
start = i;
end = j;
}
}
}
}
结果:
*
*
暴力法：O(n^2)
分治法：T(n) = 2\*T(n/2) = 4\*T(n/4) = …… = n\*T(1) 每层代价
为 n,共 logn 层 T(n)=O(nlogn)
5.设计实现一个装配线调度问题的二分分治算法（即将 n 个站从中间位置分为
两个 n/2 个站的子问题），分析你所设计算法的计算复杂度，实现讲义上的动
态规划算法，产生测数据对比两种算法的计算时间。
void Print(int a[], int i) {
for (int j = 0; j < i; j++)
{
printf("%d\t", a[j]);
}
printf("\n");
}
int line1[6] = { 7,9,3,4,8,4 };
int line2[6] = { 8,5,6,4,5,7 };
int timeLine1[5] = { 2,3,1,3,4 };
//第一装配线
//第二装配线
//第一条线向第二条线传送花费时间
//第二条线向第一条线传送花费时间
//第一条线向第二条线传送花费时间
//第二条线向第一条线传送花费时间
//进入第一条线的时间
//进入第二条线的时间
//退出第一条线的时间
//退出第二条线的时间
int timeLine2[5] = { 2,1,2,2,1 };
int transTimeLine1[5] = { 2,3,1,3,4 };
int transTimeLine2[5] = { 2,1,2,2,1 };
int inTimeLine1 = 2;
int inTimeLine2 = 4;
int outTimeLine1 = 3;
int outTimeLine2 = 2;
int farLine1[6];
int farLine2[6];
int markLine1[5];
int markLine2[5];
/*
* 分治 T(n)=cn+2cn/2+4cn/4+…+ncn/n=nlgn
*/
void fastestwayOfDivide(int low,int high) {
//到 line1 上各点的最短路径
//到 line2 上各点的最短路径
//记录上一次位置
if (low == high && low == 0) {
farLine1[low] = inTimeLine1 + line1[0];
farLine2[low] = inTimeLine2 + line2[0];
}
else if (low == high) {
int temp1 = 0;
int temp2 = 0;
temp1 = farLine1[low - 1] + line1[low];
temp2 = farLine2[low - 1] + line2[low] + timeLine2[low - 1];
if (temp1 > temp2) { farLine1[low] = temp2; markLine1[low-1] = 2; }
else { farLine1[low] = temp1; markLine1[low-1] = 1; }
temp1 = farLine2[low - 1] + line2[low];
temp2 = farLine1[low - 1] + line2[low] + timeLine1[low - 1];
if (temp1 > temp2) { farLine2[low] = temp2; markLine2[low-1] = 1; }
else { farLine2[low] = temp1; markLine2[low-1] = 2; }
}
else {
int mid = low+(high - low) / 2;
fastestwayOfDivide(low, mid);
fastestwayOfDivide(mid + 1, high);
}
}
void fastestwayOfDivideBegin()
{
int low = 0;
int high = 5;
printf("分治 - 当前的装配线为：\n");
Print(line1, 6);
Print(line2, 6);
fastestwayOfDivide(low,high);
printf("分治 - farLine1 的值为:\n");
Print(farLine1, 6);
printf("分治 - farLine2 的值为：\n");
Print(farLine1, 6);
printf("分治 - markLine1 的值为：\n");
Print(markLine1, 5);
printf("分治 - markLine2 的值为：\n");
Print(markLine2, 5);
}
/*
* 动态规划 T(n)=cn+2cn/2+4cn/4+…+ncn/n=nlgn
*/
void fastestwayOfDynamic() {
for (int i = 0; i < 6; i++) {
int temp1 = 0;
int temp2 = 0;
if (i == 0) {
farLine1[i] = inTimeLine1 + line1[0];
farLine2[i] = inTimeLine2 + line2[0];
}
else {
temp1 = farLine1[i - 1] + line1[i];
temp2 = farLine2[i - 1] + transTimeLine2[i - 1] + line1[i];
if (temp1 > temp2) { farLine1[i] = temp2; markLine1[i-1] = 2; }
else { farLine1[i] = temp1; markLine1[i-1] = 1; }
temp1 = farLine2[i - 1] + line2[i];
temp2 = farLine1[i - 1] + transTimeLine1[i - 1] + line2[i];
if (temp1 > temp2) { farLine2[i] = temp2; markLine2[i-1] = 1; }
else { farLine2[i] = temp1; markLine2[i-1] = 2; }
}
}
}
void fastestwayOfDynamicBegin()
{
printf("动态 - 当前的装配线为：\n");
Print(line1, 6);
Print(line2, 6);
fastestwayOfDynamic();
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
