算法设计第4章分治法

1、/*题目描述：设计分治算法求一个数组中的最大元素。*/*思路：要用分治法来解决数组中的最大了元素，我们可以采用递归的思想，两两比较用小标的变化来标志出存储最大的元素。*/*算法：1.首先输入数组的个数2.用rand()随机产生数组3.调用递归函数3.1 递归函数找到最大元素的下标4.输出最大元素*/#include using namespace std;int Max(int a, int low, int high);int main() int a1000, m,n;coutn;for(int i = 0;i n;i+) ai = rand() %100; for(int j = 0;j n;j+) coutaj ;coutendl;m = Max(a, 0, n-1); coutamamax2?max1: max2; return max; /*题目描述：设计分治算法，实现将数组An中所有的元素循环左移k个位置，要求时间复杂度为，空间复杂度为，例如，对abcdefgh循环左移3位得到defghabc.*/*思路：将数组元素左移n块，则将数组分成几块，然后将每一块进行编号，然后进

2、行移动，序号相同的，前一段序号的那个数移到后一段序号的那个数即可。*/*算法：1.实现相邻两端相同编号的数进行移动2.k个函数调用实现每个序号的书都进行移动3.输出数组 */#include using namespace std;void Converse(char *A,int n,int k) ;void Reverse(char *A, int from, int to);int main()char A100;int k;cout请输入数组：A;cout请输入左移的位数k：k;Converse(A,strlen(A),k);return 0;void Reverse(char *A, int from, int to)for(int i=0;i(to-from+1)/2;i+)char temp=Afrom+i;Afrom+i=Ato-i;Ato-i=temp;void Converse(char *A,int n,int k) Reverse(A, 0, k-1);Reverse(A, k, n-1);Reverse(A, 0, n-1);cout移动后的数组为：endl;

3、for(int i=0;in;i+)coutAi;coutendl;/*题目描述：在有序序列（r1,r2,r3rn）中，存在序号i（1=i i则我们就直接在数组的左边找；否则就在右边找。2.3.找到目标输出；*/#includeusing namespace std;void f(int a,int n);int main ()int a1001;int i,n;coutn;for(i = 0;i ai;f(a,n);return 0;void f(int a,int n)int left = 0,right = n - 1,mid;while(left right)mid = (left + right) / 2;if(amid = mid)cout这个元素是：amid mid)right = mid;elseleft = mid;/*题目描述：在一个序列中出现次数最多的元素称为众数，请设计算法寻找众数并分析算法的时间复杂性；*/*思路：题目要求是要用分治法，那我们就只有在排序上用分治法，将数组用快速排序，之后再遍历一次数组我们就可以找到众数。此时算法的时间复杂性为nlog(n);*

4、/*算法： 1.输入数组； 2.对数组进行快速排序 3.for循环遍历数组，用if判断找出众数 4.输出众数。*/#include using namespace std;int Partition(int r , int first, int end);void QuickSort(int r , int first, int end);int main() int r10001;int n,cont = 0,max = 0,temp;coutn;cout请输入数组的元素：;for(int j = 0;j rj;QuickSort(r,0,n-1);for(int i = 0;i n;i+)int k = i + 1;while(ri = rk & i max) temp = i - 1;max = cont;cont = 0;i = i - 1;cout众数是：rtemp 重复的次数是：maxendl;/for(int i = 0;i n;i+)/coutri ;/coutendl;return 0;int Partition(int r , int first, int end)

5、 /划分 int i = first, j = end; /初始化待划分区间 while (i j) while (i j & ri = rj) j-; /右侧扫描 if (i j) int temp = ri; ri = rj; rj = temp; /将较小记录交换到前面i+; while (i j & ri = rj) i+; /左侧扫描 if (i j) int temp = ri; ri = rj; rj = temp; /将较大记录交换到后面 j-; return i; / 返回轴值记录的位置void QuickSort(int r , int first, int end) /快速排序 int pivot; if (first end) pivot = Partition(r, first, end); /划分，pivot是轴值在序列中的位置 QuickSort(r, first, pivot-1); /求解子问题1，对左侧子序列进行快速排序 QuickSort(r, pivot+1, end); /求解子问题2，对右侧子序列进行快速排序 /*题目描述：设M 是一个nn

6、的矩阵，其中每行的元素从左到右单增有序，每列的元素从上到下单增有序。 给出一个分治算法计算出给定元素x 在M 中的位置或者表明x 不在M 中。分析算法的时间复杂性。*/*思路：在nn 的矩阵中其中每行的元素从左到右单增有序，每列的元素从上到下单增有序。那么我们就可以找到矩阵的中心元素对其进行比较，比较后要找的元素可能有两块区域，再对这两块区域再进行递归调用就可以找到我们想要的元素。*/*算法：输出元素是否存在及其位置。 1，调用MatrixBinary函数 2.1 每次都找到中心元素 2.2用要查找的元素与之进行比较 2.3如果比中心元素大就在其右侧或左下角反之在其左侧或者右上角 2.4继续递归调用MatrixBinary 2.5找到了返回1，否则返回0； 3.输出。*/#includeusing namespace std; int M55= 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 11,12,13,14,15, 16,17,18,19,20, 21,22,23,24,25 ; int x = 19;int MatrixBinary(int M55,int rb,int re,int cb,int ce) int rm = (rb+re) / 2; int cm = (cb+ce) / 2; if (rb re | cb ce) re

《算法设计第4章分治法》由会员re****.1分享，可在线阅读，更多相关《算法设计第4章分治法》请在金锄头文库上搜索。