算法设计分治法

1、/*题目描述：设计分治算法求一个数组中的最大元素。*/*思路：要用分治法来解决数组中的最大了元素，我们可以采用递归的思想, 两两比较用小标的变化来标志出存储最大的元素。*/*算法：.首先输入数组的个数.用rand()随机产生数组.调用递归函数递归函数找到最大元素的下标.输出最大元素*/#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+)cout

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

3、d;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 Convers

4、e(char *A,int n,int k) Reverse(A, 0, k-1);Reverse(A, k, n-1);Reverse(A, 0, n-1);cout移动后的数组为：endl;for(int i=0;in;i+)(coutAi;)coutendl;)/*题目描述：在有序序列(r1,r2,r3 rn)中，存在序号i (1=i i则我们就直接在数组的左边找；否则就在右边找。找到目标输出；*/#includeusing namespace std;void f(int a,int n);int main ()(int a1001;int i,n;coutn;for(i = 0;i

5、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(

6、n);*/*算法：.输入数组；.对数组进行快速排序.for循环遍历数组，用if判断找出众数.输出众数。*/#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

7、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)(int i = first, j = end;while (i j)(while (i j & ri = rj) j-;if (i j) int temp = ri; ri = rj; rj = tem

8、p;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);QuickSort(r,

9、 pivot+1, end);求解子问题1,对左侧子序列进行快速排序 求解子问题2,对右侧子序列进行快速排序/*题目描述：设 M是一个nx n的矩阵，其中每行的元素从左到右单增有序，每列的元素从上到下单增有序。给出一个分治算法计算出给定元素x在M中的位置或者表明x不在M中。分析算法的时间复杂性。*/*思路：在nx n的矩阵中其中每行的元素从左到右单增有序，每列的元素从上到下单增有序。那么我们就可以找到矩阵的中心元素对其进行比较，比较后要找的元素可能有两块区域， 再对这两块区域再进行递归调用就可以找到我们想要的元素。*/*算法：输出元素是否存在及其位置。1,调用 MatrixBinary 函数每

10、次都找到中心元素用要查找的元素与之进行比较如果比中心元素大就在其右侧或左下角反之在其左侧或者右上角继续递归调用 MatrixBinary找到了返回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)

11、/ 2;if (rb re | cb ce)return 0;if(x = Mrmcm)coutx所在的位置：Mrmcm Mrmcm)(return MatrixBinary(M,rb,re,cm+1,ce)|MatrixBinary(M,rm+1,re,cb,cm); ) else (return MatrixBinary(M,rb,rm-1,cb,ce)|MatrixBinary(M,rm,re,cb,cm-1);)int main()(int a = MatrixBinary(M,0,4,0,4);if(a = 1) (cout要查找的x存在endl;)elsecout要查找的x不存在e

12、ndl;return 0;)/*题目描述：在一个序列中出现次数最多的元素称为众数， 请设计算法寻找众数并分析算法的时间复杂性；*/*思路：题目要求是要用分治法，那我们就只有在排序上用分治法，将数组用快速排序，之后再遍历一次数组我们就可以找到s1,s2。此时算法的时间复杂性为nlog(n);*/*算法：.输入数组；.对数组进行快速排序.for循环遍历数组，找到 s1,s2.输出两个子集元素之和的最大差。*/#include using namespace std;int Partition(int r , int first, int end);void QuickSort(int r , in

13、t first, int end);int main()int r10001;int n,s1 = 0,s2 = 0,c;coutn;cout请输入数组的元素：;for(int j = 0;j rj;QuickSort(r,0,n-1);int k = n / 2;for(int i = 0;i k;i+)= s1 + ri;for(int q = k;q n;q+)= s2 + rq;c = s2 - s1;cout两个子集元素之和的最大差是： return 0;int Partition(int r , int first, int end)int i = first, j = end;w

14、hile (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-;cendl;划分初始化待划分区间右侧扫描将较小记录交换到前面左侧扫描将较大记录交换到后面/返回轴值记录的位置return i;快速排序划分，pivot是轴值在序列中的位置求解子问题1,对左侧子序列进行快速排序求解子问题2,对右侧子序列进行快速排序)void QuickSort(int r ,

15、 int first, int end)(int pivot;if (first end) pivot = Partition(r, first, end);QuickSort(r, first, pivot-1);QuickSort(r, pivot+1, end);) /*题目描述：循环赛日程安排问题：设有n=2Ak个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次;(2)每个选手一天只能参赛一次；*/ /*思路：先用2个选手模拟，再用 4个选手模拟找到其中相似之处：日程表划分为四小块，左下小块可以用左上小块的每个数相加同一个数;

16、右上角的数和左下角的数是一样的；右下角的数和左上角的数是一样的。 我们找到它们的位置关系就可以把日程表表示出来；注：第一列表示选手的人数，第二列表示第一天，依次类推。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手K = 2 时：1 2 3 44 3 2 1k = 3 时：1 2 3 4 5 6 7 82 1 4 3 6 5 8 7*/*算法：1.输入K;.创建动态二维数组.日程函数：填左下角填右上角填右下角.输出日程表；*/#includeusing namespace std;void Table(int k,int *a);int main ()int k;cink;int n

17、 = 1;for(int j = 1;j = k;j+)/参加比赛选手的人数n = n * 2;int *a = new int *n+1;/根据n动态分配二维数组afor(int i = 0;i = n;i+)ai = new intn+1;Table(k,a); /分配日程函数for(int q=1; q=n; q+)for(int l=1; l=n; l+)coutaql ;coutendl;for(int r = 0;r = n;r+)释放空间delete ar;delete a;return 0;void Table(int k,int *a)int i,j,t,temp;int n = 2;a11 = 1; a12 = 2;最开始只有两个人比赛的安排a21 = 2; a22 = 1;for(t = 1;t k;t