算法设计题1.doc

出2个算法设计题，每个20分。1. 设a0:n-1是有n个元素的数组，k(0kn-1)是一个非负整数。试设计一个算法将子数组a0:k-1和ak:n-1换位。要求算法在最坏情况下耗时O(n)，且只用到O(1)的辅助空间。初步思考：最简单的方法就是循环(n-k-1)次，将a数组的末尾数字插入到a0之前。具体做法：法一：(1) 首先开辟一个额外空间temp用于存放每一次a数组的末尾数据。 (2) temp - an-1 (3) 将a0: n-2 每个数据都依次向后移动一位赋值给a1: n-1。 (4) a0 - temp (5) 循环执行(2) -(4) 步 (n-k+1)次。代价分析： 时间代价 O(n-1)*(n-k+1) 即O(n2)数量级；空间代价O(1)法二：如果a0 : k 与 ak+1 : n-1 正好长度相等，则可以直接一一对应交换即可。 当然，这道题的难点就在于k并不一定是a数组的中间位置。即便如此，但是仍然可以交换： 如果a0 : k.length ak+1 : n-1.length， 则可以将a0 : k 与 ak+1 : n-1 中最后一部分大小相同的数据交换： |- ak+1 : n-1 -| a0:k ak+1 : n-k-2 an-k-1 : n-1 其中 a0:k 与 an-k-1 : n-1 长度相同，因此完全可以一一对应交换成： |- a0 : n-k-2 -| a0:k ak+1 : n-k-2 an-k-1 : n-1 交换完成以后，则an-k-1 : n-1 已经交换到位，而a0 : n-k-2 还需要进一步这样递归交换。 源代码如下：C代码 1 #include 2 3 /交换数组的两段大小相等的范围的对应数据 4 /alow1 alow2 alow1+1alow2+1 . ahigh1 ahigh2 5 void swap(int a,int low1,int high1,int low2,int high2) 6 7 int temp; 8 while(low1=high1) 9 temp=alow1; 10 alow1=alow2; 11 alow2=temp; 12 low1+; 13 low2+; 14 15 16 17 /利用分治算法， 每次选择最小的数组进行换位 18 void patition(int a, int low, int k, int high) 19 20 if(lowhigh) 21 if(k-low+1)=(high-k) 22 swap(a,low,k,k+1,high); 23 else if(k-low+1)(high-k) 24 swap(a,low,k,low+high-k,high); 25 patition(a,low,k,low+high-k-1); 26 27 else 28 swap(a,low,high+low-k-1,k+1,high); 29 patition(a,high+low-k,k,high); 30 31 32 33 34 /测试 35 int main() 36 int a=0,1,2,3,4,5,6,7,8,9,10,11,12,13; 37 patition(a,0,4,13); 38 for(int i=0;i14;i+) 39 printf(%d ,ai); 40 41 return 0; 42 c view plaincopy43 #include 44 45 /交换数组的两段大小相等的范围的对应数据 46 /alow1 alow2 alow1+1alow2+1 . ahigh1 ahigh2 47 void swap(int a,int low1,int high1,int low2,int high2) 48 49 int temp; 50 while(low1=high1) 51 temp=alow1; 52 alow1=alow2; 53 alow2=temp; 54 low1+; 55 low2+; 56 57 58 59 /利用分治算法， 每次选择最小的数组进行换位 60 void patition(int a, int low, int k, int high) 61 62 if(lowhigh) 63 if(k-low+1)=(high-k) 64 swap(a,low,k,k+1,high); 65 else if(k-low+1)(high-k) 66 swap(a,low,k,low+high-k,high); 67 patition(a,low,k,low+high-k-1); 68 69 else 70 swap(a,low,high+low-k-1,k+1,high); 71 patition(a,high+low-k,k,high); 72 73 74 75 76 /测试 77 int main() 78 int a=0,1,2,3,4,5,6,7,8,9,10,11,12,13; 79 patition(a,0,4,13); 80 for(int i=0;i14;i+) 81 printf(%d ,ai); 82 83 return 0; 84 这样的时间复杂度为O(n)，而且交换数据的时候只需要O(1)的额外空间。2. 设子数组a0:k-1和ak:n-1已经排好序k(0kn-1)。试设计一个合并这两个子数组为排好序的数组a0:n-1的算法。要求算法在最坏情况下耗时O(n)，且只用到O(1)的辅助空间。1）向右循环换位合并向右循环换位合并算法首先用二分搜索算法在数组段ak:n-1中搜索a0的插入位置，即找到位置p使得apa0=ap+1。数组段a0:p向右循环换位p-k+1个位置，使得ak-1移动到ap的位置。此时，原数组a0及其左边的所有元素均已经排好序。对剩余的数组元素重复上述过程，直到只剩下一个数组段，此时整个数组已经排好序。 代码如下所示。1 #include 2 using namespace std;34 #define MAXNUM 10056 /下面函数将数组段as:t中元素循环右移位k个位置7 void shiftright(int a, int s, int t, int k)8 9 int i = 0;10 int j = 0;11 for(i = 0; i s; j-)15 16 aj = aj-1;17 18 as = tmp;19 20 2122 /下面函数用于在数组段中aleft:right中搜索元素x的插入位置23 int binarySearch(int a, int x, int left, int right)24 25 int mid;26 while(left amid)34 35 left = mid + 1;36 37 else38 39 right = mid - 1;40 41 42 if(x amid)43 44 return mid;45 46 else47 48 return mid - 1;49 50 5152 /向右循环移位合并算法53 /length:数组的长度54 void mergefor(int a, int k, int length)55 56 /merge a0:k-1 and ak:n-157 int i = 0;58 int j = k;59 while(i j & j length)60 61 int p = binarySearch(a, ai, j, length - 1);62 shiftright(a, i, p, p - j + 1);63 j = p + 1;64 i += p - j + 2;65 66 6768 int main(int argc, char* argv)69 70 /这里的 k = 5，即a0:4、a5:871 int a9 = 1, 3, 5 , 7, 9, 2, 4, 6, 8;72 int length = sizeof(a)/ sizeof(a0);7374 cout 原数组为： endl;75 for(int i = 0; i length; i+)76 77 cout ai ;78 79 80 81 mergefor(a, 5, length);8283 cout endl 排序后为： endl;84 for(int i = 0; i length; i+)85 86 cout ai ;87 88 cout endl;89 return 0;90 上述算法中，数组段a0:k-1中元素的移动次数不超过k次，数组段ak:n-1中元素最多移动一次。因此，算法的元素移动总次数为:k2+(n-k)次。算法的比较次数不超过klog(n - k)（这个不明白）。当k n1/2时，算法的时间复杂度为O(n)；反之，则为O(n*n）。3. 设是一个实数，是一个正整数，试设计一个分治算法计算。4. 设有n个顾客同时等待一项服务，顾客i需要的服务时间为ti(1in)。问如何安排n个顾客的服务次序才能使平均等待的时间达到最小？平均等待时间是n个顾客等待服务的时间总和除以n。/link?url=fRZ_6gD71mtbeMpAemMlKPzR6LCg_eSOUKvHVoqF-8RpA99ecf2Zj8dhhWsn5buSXzQyJxfdXSmFwV-65xhl7WR2VFQZN3AoaNKTaYcgJ6S5. 设 是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样固定长度的闭区间？设计求解此问题的贪心算法。/link?url=K