《算法设计题1》由会员分享，可在线阅读，更多相关《算法设计题1（6页珍藏版）》请在金锄头文库上搜索。
1、 出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)次。代价分析： 时间代价
2、 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-
3、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=al
4、ow2; 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 els
5、e 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 al
6、ow2 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) 6
7、3 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
8、,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向右循环换
9、位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 = tm
10、p;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
