算法设计 第4章 分治法

《算法设计 第4章 分治法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、/*题目描述：设计分治算法求一个数组中的最大元素。*//*思路：要用分治法来解决数组中的最大了元素，我们可以采用递归的思想，两两比较用小标的变化来标志出存储最大的元素。*//*算法：1.首先输入数组的个数2.用rand()随机产生数组3.调用递归函数3.1递归函数找到最大元素的下标4.输出最大元素*/#includeusingnamespacestd;intMax(inta[],intlow,inthigh);intmain(){inta[1000],m,n;cout<<"请输入数组的个数："

2、;cin>>n;for(inti=0;i

3、+1,high);max=a[max1]>a[max2]?max1:max2;returnmax;}}/*题目描述：设计分治算法，实现将数组A[n]中所有的元素循环左移k个位置，要求时间复杂度为，空间复杂度为，例如，对abcdefgh循环左移3位得到defghabc.*//*思路：将数组元素左移n块，则将数组分成几块，然后将每一块进行编号，然后进行移动，序号相同的，前一段序号的那个数移到后一段序号的那个数即可。*//*算法：1.实现相邻两端相同编号的数进行移动2.k个函数调用实现每个序号的书都进行移动3.输出数组

4、*/#includeusingnamespacestd;voidConverse(char*A,intn,intk);voidReverse(char*A,intfrom,intto);intmain(){charA[100];intk;cout<<"请输入数组："<>A;cout<<"请输入左移的位数k："<>k;Converse(A,strlen(A),k);return0;}voidReverse(char*A,intfrom,intto){for

5、(inti=0;i<(to-from+1)/2;i++){chartemp=A[from+i];A[from+i]=A[to-i];A[to-i]=temp;}}voidConverse(char*A,intn,intk){Reverse(A,0,k-1);Reverse(A,k,n-1);Reverse(A,0,n-1);cout<<"移动后的数组为："<

6、，存在序号i（1<=i<=n）,使得ri=i;请设计一个分治算法找到这个元素，要求算法在最坏的情况下的时间性能为O(log2n);*//*思路：这道题主要采用的是折半查找的思路，同时也体现出了分治法；把一个大的问题折半折半再折半···的处理，最终就可以找到目标。*//*算法：1.输入数组2.定义折半查找的函数；2.1.折半找到中间的数比较r[i]和i的大小；2.2.如果r[i]>i则我们就直接在数组的左边找；否则就在右边找。2.3.找到目标输出；*/#includeusingnamespace

7、std;voidf(inta[],intn);intmain(){inta[1001];inti,n;cout<<"请输入有序数组的个数：";cin>>n;for(i=0;i>a[i];}f(a,n);return0;}voidf(inta[],intn){intleft=0,right=n-1,mid;while(left

8、(a[mid]>mid)right=mid;elseleft=mid;}}/*题目描述：在一个序列中出现次数最多的元素称为众数，请设计算法寻找众数并分析算法的时间复杂性；*//*思路：题目要求是要用分治法，那我们就只有在排序上用分治法，将数组用快速排序，之后再遍历一次数组我们就可以找到众数。此时算法的时间复杂性为nlog(n);*//*算法：1.输入数组；2.对数组进行快