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

算法作业


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(query((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


赞助商链接
相关文章:
计算方法大作业
计算方法大作业_数学_自然科学_专业资料。实验一 牛顿下山法 一、 实验目的: 1、 2、 掌握牛顿下山法求解方程根的推导原理。 理解牛顿下山法的具体算法与相应...
算法作业翻译
算法作业翻译 - 1.使用合并-查找数据结构,实现估计渗漏(Percolation)问题阈值的程序。 Write a program to estimate the value of the p...
算法课后作业
算法课后作业_理学_高等教育_教育专区。一些算法导论的课后作业算法课后作业 2.2.10.快速归并。实现一个 merge()方法,按降序将 a[]的后半部分复制到 aux[],然...
算法作业
算法作业_数学_自然科学_专业资料。矩阵相乘算法 多项式算法与矩阵相乘算法实验报告实验题目与要求:多项式算法与矩阵相乘算法 实验一:分别实现多项式的四种运算,若针对...
感知器算法 作业
感知器算法 作业_数学_自然科学_专业资料。感知器算法作业: 图为二维平面中的 4 个点,x1, x2∈ω 1 ,x3,x4∈ω 2 ,设计使用感知器算法的线性 分类器,...
算法部分作业答案
算法部分作业答案_工学_高等教育_教育专区。大部分的重要作业答案都在上面,自己做的哦,答案是正确的 1.1 算法:是对特定问题求解步骤的一种描述,是指令的有限...
算法作业
算法作业_数学_自然科学_专业资料。第 6 章 算法与程序设计基础实验 1 Raptor 编程环境一、实验目的 1.学习 Raptor 环境介绍,认识 Raptor 界面。 2.认识 Raptor...
2014年12月中南大学网络教育课程考试:算法分析与设计作...
2014年12月中南大学网络教育课程考试:算法分析与设计作业参考答案_教育学_高等教育_教育专区。《算法分析与设计》作业参考答案 作业一 一、名词解释: 1.递归算法:...
数据结构与算法离线作业题目及答案
浙江大学远程教育学院 《数据结构与算法》课程离线作业姓名: 年级: 陈翠 2013 秋学号: 713009014001 金华学习中心 学习中心: ———一、填空题: ( 【序号,章,节...
数值计算方法编程作业(C语言版)
数值计算方法编程作业(C语言版)_金融/投资_经管营销_专业资料。w1...辛普生算法是一种积分方法,采用三点法插值,如果 h 较小的话,误差很小,因为...
更多相关标签: