算法设计 第4章 分治法_48285.doc

/* 题目描述：设计分治算法求一个数组中的最大元素。 */ /* 思路：要用分治法来解决数组中的最大了元素，我们可以采用递归的思想， 两两比较用小标的变化来标志出存储最大的元素。 */ /* 算法： 1.首先输入数组的个数 2.用rand()随机产生数组 3.调用递归函数 3.1 递归函数找到最大元素的下标 4.输出最大元素 */ #include iostream using namespace std; int Max(int a[], int low, int high); int main() { int a[1000], m,n; cout请输入数组的个数：; cinn; for(int i = 0;i n;i++) a[i] = rand() %100; for(int j = 0;j n;j++) couta[j] ; coutendl; m = Max(a, 0, n-1); couta[m]endl; return 0; } int Max(int a[], int low, int high) { int mid, max, max1, max2; if(low==high) return low; else { mid=(low+high)/2; max1=Max(a, low, mid); max2=Max(a, mid+1, high); max = a[max1]a[max2]?max1: max2; return max; } } /* 题目描述：设计分治算法，实现将数组A[n]中所有的元素循环左移k个位置，要求时间 复杂度为，空间复杂度为，例如，对abcdefgh循环左移3位得到defghabc. */ /* 思路：将数组元素左移n块，则将数组分成几块，然后将每一块进行编号， 然后进行移动，序号相同的，前一段序号的那个数移到后一段序号的那个数即可。 */ /* 算法： 1.实现相邻两端相同编号的数进行移动 2.k个函数调用实现每个序号的书都进行移动 3.输出数组 */ #include iostream using namespace std; void Converse(char *A,int n,int k) ; void Reverse(char *A, int from, int to); int main() { char A[100]; int k; cout请输入数组：endl; cinA; cout请输入左移的位数k：endl; cink; 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=A[from+i]; A[from+i]=A[to-i]; A[to-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; for(int i=0;in;i++) { coutA[i]; } coutendl; } /* 题目描述：在有序序列（r1,r2,r3····rn）中，存在序号i（1=i=n）, 使得ri = i;请设计一个分治算法找到这个元素，要求算法在最坏的情况下的 时间性能为O(log2n); */ /* 思路：这道题主要采用的是折半查找的思路，同时也体现出了分治法； 把一个大的问题折半折半再折半···的处理，最终就可以找到目标。 */ /* 算法： 1.输入数组 2.定义折半查找的函数； 2.1.折半找到中间的数比较r[i]和i的大小； 2.2.如果r[i] i则我们就直接在数组的左边找；否则就在右边找。 2.3.找到目标输出； */ #includeiostream using namespace std; void f(int a[],int n); int main () { int a[1001]; int i,n; cout请输入有序数组的个数：; cinn; for(i = 0;i n;i++) { cina[i]; } f(a,n); return 0; } void f(int a[],int n) { int left = 0