当前位置:首页 >> 其它课程 >>

算法作业


1. pseudo_code: find_median(m1, n1, m2, n2) { if(n1-m1<=2 or n2-m2<=2) { find and print median from “query(m1, D1), … ,querr(n1,D1), query(m2, D2), … ,querr(n2, D2),”; return; } if(quer

y((n1+m1)/2, D1) > query((n2+m2)/2, D2)) find_median(m1,n1+m1)/2,(n2+m2)/2, n2); else find_median((n1+m1)/2,n1, m2, (n2+m2)/2); } explanation:m1, n1 is range of medain in D1, if we find median_one of D1 and median_two of D2, we can delete the part above a larger number of both medians and the part under a smaller number of both medians. subproblem reduction graph:

Analyse the complexity of the algorithm: O(log n *2 +2) = O(log n) Prove the correctness of the answer: first, every substep is right. because the median of 2n number can’t exist in either the part above a larger number of the medians or the part under a smaller number of the medians. So deleting them is right. And then we prove that the median of 2n equal to the median of subproblem. two part of deleting is equivalent and if we delete the same numbers on either side of the median, the median is not changed. above of all, my algorithm is right. by the way, deleting should be same numbers in algorithm implementation.

4. pseudo_code: find_local_min(root) { if root have no son return root; if probe(root)>probe(left) find_local_min(left); else if probe(root)>probe(right) find_local_min(right); else return root; } subproblem reduction graph:

Analyse the complexity of the algorithm: if c= 1 / and 4 ≥ ci≥ 1,c 2 ≤42 . sothe complexity of the algorithm is O(42 )= O(2 ). Prove the correctness of the answer: if there is a local_min node in the path from root to leaf.it will be found out by the algorithm. but, if not, the leaf is smaller than its father, so the leaf must be local_min node. so whatever, a local_min node can be found out.

5.algorithm: first, probe all node in six line including horizontal line 1, horizontal line n, horizontal line (n+1)/2, vertical line 1. vertical line n. vertical line (n+1)/2. Six line divide into four part. Then find the min node on the six line, and judge whether the minimum node is local_min node. if is, return; if not, node there is smaller node n around the minimum, so keep finding by using recursive function.from the part including the noden .

subproblem reduction graph:

Analyse the complexity of the algorithm: according to master theorem, if T n = T
n 4

+ , T(n)=O(n)

Prove the correctness of the answer: assumpt my answer is wrong, so there is no local_min node in sub part. n in the part is not local_min node, so there is a node n <n , obviously n is smaller than four line all around the part. every node beside the part is smaller than one node labled. so there is no minimum node in the part. however, Every node is distinct, there must be minimum node, so the assumption is wrong. my answer is right.

7. i)Code: #include <stdio.h> #include<stdlib.h> int N=100000; int data[100000]; long long merge_and_count(int l,int m,int r) { int count = 0; int* L = (int*)malloc((m-l+1)*sizeof(int)); int* R = (int*)malloc((r-m)*sizeof(int)); for(int i=l; i<=m; i++) L[i-l] = data[i]; for(int i=m+1; i<=r; i++) R[i-m-1] = data[i]; int i = 0,j = 0,k = l; for(i=0; i<m-l+1 && j<r-m;) { if(L[i] > R[j]) { data[k++]=R[j++]; count+=m-l-i+1; } else data[k++]=R[i++]; } for(;i<m-l+1;) data[k++]=L[i++]; for(;j<r-m;) data[k++]=R[j++]; return count; } long long inversion_Count(int l,int r) { FILE* fp = fopen("res.txt","a"); if(l < r) { int m=(l+r)>>1; long long L=inversion_Count(l,m); long long R=inversion_Count(m+1,r); long long LR=merge_and_count(l,m,r); long long tmp = L+R+LR; fwrite(&tmp, sizeof(long long), 1, fp); fclose(fp);

return tmp; } else { fclose(fp); return 0; } } int main() { FILE* fp = fopen("Q5.txt","r"); for(int i=0;i<N;i++) fread(&data[i], sizeof(int), 1, fp); printf("%lld",inversion_Count(0,N-1)); fclose(fp); return 0; } The result is 2951724343. ii) No. Because there is not the sorted half array. in fact, we get two sorted half array and can compute one number in left array and another number in right array by uing Merge_Sort. But Quick_Sort function is the same with visiting tree in preorder. we can’t insert same steps into the later.

10. karatsuba algorithm code: long long karatsuba(long long x, long long y, long long dnum) { if (x<10 || y<10) return x*y; long long xh = x, xl = 0, xt = 0; long long yh = y, yl = 0, yt = 0; for (int i=0;i<dnum/2;i++) { xt = xh % 10; xl = xl * 10 + xt; xh = xh / 10; } for (int i=0;i<dnum/2;i++) { yt = yh % 10; yl = yl * 10 + yt;

yh = yh / 10; } long long k0 = karatsuba(xl,yl,dnum/2); long long k1 = karatsuba((xl+xh), (yl+yh),dnum/2); long long k2 = karatsuba(xh,yh,dnum/2); long long tmp = k1-k2-k0; for (int i=0; i<dnum/2;i++) { tmp=tmp*10; } for (int i=0; i<dnum;i++) { k2=k2*10; } return k2+tmp+k0; }

quadratic grade-school method code. long long Multiplication(long long x, long long y, long long dnum) { long long xp[MAXDNUM]; long long yp[MAXDNUM]; long long xt = 0, yt = 0; for (int i=0;i<dnum;i++) { xt = x % 10; xp[i]=xt; x = x / 10; yt = y % 10; yp[i] = yt; y = y / 10; } long long s = 0; long long s1=0; for (int i=0;i<dnum;i++) { for (int j=0;j<dnum;j++) { long long tmp = 1;
for (int k = 0;k<j;k++) { tmp = tmp*10; }

s1= s1 + xp[i] * yp[j] * tmp; } long long tmp = 1; for (int k = 0;k<i;k++) { tmp = tmp*10; } s =s+s1*tmp; s1 = 0; } return s; }

compare the performance(/um) digit number quadratic grade-school method 2 ~ 4 1 8 3 16 17 (intel i5 2.5GHz, 4G memory, win7)

karatsuba algorithm ~ 1 4 20


相关文章:
算法大作业
算法作业 暂无评价|0人阅读|0次下载|举报文档 算法作业 1)问题描述 Problem Description 旅行商问题(TravelingS alesmanP roblem,简记为TSP)是一个典型的NP完...
算法作业
算法作业_其它课程_高中教育_教育专区。卜东波算法第一次作业 1. pseudo_code: find_median(m1, n1, m2, n2) { if(n1-m1<=2 or n2-m2<=2) { find ...
算法大作业
算法作业 姓名 学号 基于社团评估函数 Q 的社区网络检测算法一、问题描述随着对网络性质的物理意义和数学特性的深入研究, 人们发现许多实际网络都具有一个共同 ...
算法作业
算法作业_数学_自然科学_专业资料。第 6 章 算法与程序设计基础实验 1 Raptor 编程环境一、实验目的 1.学习 Raptor 环境介绍,认识 Raptor 界面。 2.认识 Raptor...
算法作业
算法作业_计算机软件及应用_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 算法作业_计算机软件及应用_IT/计算机_专业资料。全排列问题: 设计思想:假设 ...
算法作业
算法作业_数学_自然科学_专业资料。第六章作业 一、选择题 1.在如下四实例上分别运行快速分类算法,其中在(A )上算法所作元素比较次数最少。 A. (5,5,5,5...
算法作业-3
算法作业-3_电脑基础知识_IT/计算机_专业资料。算法作业1.证明 graham-scan 的正确性 2.优化 matrix-chain-order ≥≤?∑≠θΩε∞≠∣ Print-optimal-parens...
算法作业答案1
算法作业答案1_理学_高等教育_教育专区。算法分析与设计基础 算法作业答案1 一· 算法一 该算法设计思想依据的公式为 f ( x) ? an xn ? an?1xn?1 ??? ...
算法大作业
算法作业——寻找多数元素 班级:0213051 学号: (1)问题提出: 令 A[1,2,…n]是一个整数序列,A 中的整数 a 如果在 A 中出现的 次数多于 ,那么 a 称...
各类作业调度算法
实习题: 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业等待算法:分别采用先来先服务(FCFS),最短作业优先(SJF)、响 应比高者优先(HRN)的调度算法。...
更多相关标签:
算法 | 算法设计与分析 | 电子科大算法作业 | 短作业优先调度算法 | 短作业优先算法 | 作业调度算法 | 最短作业优先调度算法 | 批处理作业调度算法 |