发布时间 : 星期日 文章算法设计与分析习题答案1-6章更新完毕开始阅读
营业员答道:“噢，对不起，我今天非常头疼，所以把键按错了。”然后，营业员将结果重算了一遍，将这四样东西的价格加在一起，然而，令他俩更为吃惊的是总和也是$7.11。设计蛮力算法找出这四样东西的价格各是多少,
该算法为:
int $7.11(float a[],float b[],float c[],float d[],int n) {
for(int i=0;i!=n;++i) for(int j=0;j!=n;++j) for(int k=0;k!=n;++k) for(int m=0;m!=n;++m) {
if((a[i]+b[j]+c[k]+d[m])==7.11 && a [i]*b[j]*c[k]*d[m]==7.11) cout< 1. 分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的 个数有关，试说明这几个参数与分治法时间复杂性之间的关系。 2. 证明:如果分治法的合并可以在线性时间内完成，则当子问题的规模之和小于原问 题的规模时，算法的时间复杂性可达到O(n)。 O(N)=2*O(N/2)+x O(N)+x=2*O(N/2)+2*x a*O(N)+x=a*(2*O(N/2)+x)+x=2*a *O(N/2)+(a+1)*x 由此可知，时间复杂度可达到O(n); 3.分治策略一定导致递归吗,如果是，请解释原因。如果不是，给出一个不包含递归的 分治例子，并阐述这种分治和包含递归的分治的主要不同。 不一定导致递归。 如非递归的二叉树中序遍历。 这种分治方法与递归的二叉树中序遍历主要区别是:应用了栈这个数据结构。 4. 对于待排序序列(5, 3, 1, 9)，分别画出归并排序和快速排序的递归运行轨迹。 归并排序: 第一趟:(5,3)(1,9); 第二趟:(3,5,1,9); 第三趟:(1,3,5,9); 快速排序: 第一趟:5( ,3,1,9);//5为哨兵，比较9和5 第二趟:5(1,3, ,9);//比较1和5，将1挪到相应位置; 第三趟:5(1,3, ,9);//比较3和5; 第四趟:(1,3,5,9); 5. 设计分治算法求一个数组中的最大元素，并分析时间性能。 //简单的分治问题 //将数组均衡的分为“前”，“后”两部分 //分别求出这两部分最大值，然后再比较这两个最大值 #include int a[n]={0,6,1,2,3,5};//初始化 int mid=n/2; int num_max1=0,num_max2=0; for(int i=0;i<=n/2;++i)//前半部分 { if(a[i]>num_max1) num_max1=a[i]; } for(int j=n/2+1;j if(a[j]>num_max2) num_max2=a[j]; } if(num_max1>=num_max2) cout<<\数组中的最大元素: \else cout<<\数组中的最大元素: \return 0; } 时间复杂度:O(n) 6. 设计分治算法，实现将数组A[n]中所有元素循环左移k个位置, 要求时间复杂性为O(n)，空间复杂性为O(1)。例如，对abcdefgh循环左移3位得到defghabc。 //采用分治法 //将数组分为0-k-1和k-n-1两块 //将这两块分别左移 //然后再合并左移 #include void LeftReverse(char *a, int begin, int end) { for(int i=0;i<(end-begin+1)/2;i++)//交换移动 { int temp=a[begin+i]; a[begin+i]=a[end-i]; a[end-i]=temp; } } void Converse(char *a,int n,int k) { LeftReverse(a, 0, k-1); LeftReverse(a, k, n-1); LeftReverse(a, 0, n-1);