算法导论第九章课后答案

9.1-1 证明：在最坏情况下，找到n个元素中第二小的元素需要n+向上取整lgn-2次比较。

我们对于查找第2小元素分成2步。
step1:我们先将数组中的元素两两成对比较，共需n/2次比较，那么就有n/2个元素是较小的元素，然后再将这些较小的元素再次两两成对比较，又淘汰一半，重复这样的循环，每次淘汰一半元素直到只剩下1个元素，该元素就是最小元素。经过的比较次数为S=n/2+n/4+...(n/(2^k)=1) k=lgn S=n-1次。
step2:经过以上比较，就形成了一个二叉树，那么第2小的元素肯定与最小元素比较过，所以我们采取的方法是，从根结点也就是最小元素开始沿着根向叶子结点开始查找等于根节点的子结点A，第二小的元素就应该在与A结点属于同一个父结点的另外一个子结点B上，将B结点上的值给予第二小元素second，这样经过以上方式最坏lgn-1次比较，只要小于second值的元素，second就被覆盖成该元素，最终总能找到第2小元素。所以总比较次数为n-1+lgn-1=n+lgn-2。但是具体实现我还未想出来。

9.1-2 证明：在最坏情况下，同时找到n个元素中最大值和最小值的比较次数的下界是向上取整3n/2-2

我们将输入元素两两相互进行比较，然后把较小的与当前最小值比较，较大的与当前最大值比较，所以2个元素每次循环要比较3次，但是仅仅需要进行n/2次循环，所以总的比较次数为(向上取整)3n/2-2次。

以下是代码：

[cpp] view plaincopy

1. //同时求最小与最大值，只需要3n/2次比较  
2. #include <iostream>  
3. #include <time.h>  
4. using namespace std;  
5. const n=10;  
6. void max_min(int A[],int &max,int &min)//同时找出最大值和最小值。  
7. {  
8.     for (int i=0;i<n;i+=2)  
9.     {  
10.         if (A[i]>A[i+1])  
11.         {  
12.             if (A[i]>max)  
13.             {  
14.                 max=A[i];  
15.             }  
16.             if (A[i+1]<min)  
17.             {  
18.                 min=A[i+1];  
19.             }  
20.         }  
21.         else  
22.         {  
23.             if (A[i+1]>max)  
24.             {  
25.                 max=A[i+1];  
26.             }  
27.             if (A[i]<min)  
28.             {  
29.                 min=A[i];  
30.             }  
31.         }  
32.     }  
33. }  
34. void main()  
35. {  
36.     //数组A max min全部置0  
37.     int A[n]={0},max=0,min=0;  
38.     //随机输入数组  
39.     srand( (unsigned)time( NULL ) );  
40.     for (int i=0;i<n;i++)  
41.     {  
42.         A[i]=rand()%100;  
43.         cout<<A[i]<<" ";  
44.     }  
45.     cout<<endl;  
46.     //max与min初始化  
47.     if (n%2!=0)  
48.     {  
49.         max=A[0];  
50.         min=A[0];  
51.     }  
52.     else  
53.     {  
54.         if (A[0]>A[1])  
55.         {  
56.             max=A[0];min=A[1];  
57.         }  
58.         else  
59.         {  
60.             max=A[1];min=A[0];  
61.         }  
62.     }  
63.     //求数组A的max与min  
64.     max_min(A,max,min);  
65.     //输出max与min  
66.     cout<<"max="<<max<<endl;  
67.     cout<<"min="<<min<<endl;  
68. }  

9.2节代码：

[cpp] view plaincopy

1. #include <iostream>  
2. #include <time.h>  
3. using namespace std;  
4. const n=8;  
5. int PARTITION(int A[],int p,int r);  
6. int RANDOM(int p,int r)  
7. {  
8.     int t=rand()%(r-p+1)+p;  
9.     return t;  
10. }  
11. int RANDOMIZED_PARTITION(int A[],int p,int r)  
12. {  
13.     int i=RANDOM(p,r);  
14.     swap(A[r],A[i]);  
15.     return PARTITION(A,p,r);  
16. }  
17. int PARTITION(int A[],int p,int r)  
18. {  
19.     int x=A[r];  
20.     int i=p-1;  
21.     for (int j=p;j<=r-1;j++)//O(n)  
22.     {  
23.         if (A[j]<=x)  
24.         {  
25.             i++;  
26.             swap(A[i],A[j]);  
27.         }  
28.     }  
29.     swap(A[i+1],A[r]);  
30.     return i+1;  
31. }  
32. int RANDOMIZED_SELECT(int A[],int p,int r,int i)  
33. {  
34.     if (p==r)  
35.     {  
36.         return A[p];  
37.     }  
38.     int q=RANDOMIZED_PARTITION(A,p,r);  
39.     int k=q-p+1;  
40.     if (i==k)  
41.     {  
42.         return A[q];  
43.     }  
44.     else if(i<k)  
45.     {  
46.         return RANDOMIZED_SELECT(A,p,q-1,i);  
47.     }  
48.     else return RANDOMIZED_SELECT(A,q+1,r,i-k);  
49. }  
50.   
51. void main()  
52. {  
53.     //int A[n]={43,11,29,82,0,89};  
54.     int A[n]={0};  
55.     //随机输入数组  
56.     srand( (unsigned)time( NULL ) );  
57.     for (int i=0;i<n;i++)  
58.     {  
59.         A[i]=rand()%100;  
60.         cout<<A[i]<<" ";  
61.     }  
62.     cout<<endl;  
63.    cout<<RANDOMIZED_SELECT(A,0,7,2)<<endl;  
64. }  

9.2-1 证明：在RANDOMIZED-SELECT中，对长度为0的数组，不会进行递归调用。

看上面的代码，从RANDOMIZED-SELECT函数知，长度为0的数组 p=r，那么直接返回A[p].不做下面的随机划分和递归调用。

9.2-2 证明：指示器随机变量Xk和T(max(k-1,n-k))是独立的。

因为我们最初假设输入数组各个元素是互异的，所以有证明结论。

9.2-3 给出RANDOMIZED-SELECT的一个基于循环的版本。

[cpp] view plaincopy

1. int RANDOMIZED_SELECT(int A[],int p,int r,int i)  
2. {  
3.     while (1)  
4.     {  
5.         if (p==r)  
6.         {  
7.             return A[p];  
8.         }  
9.         int q=RANDOMIZED_PARTITION(A,p,r);  
10.         int k=q-p+1;  
11.         if (i==k)  
12.         {  
13.             return A[q];  
14.         }  
15.         else if(i<k)  
16.         {  
17.             r=q-1;//这行代码可以处理有重复的待查找数。  
18.             //q--;//网上给的答案是用这行，这行代码不能处理重复元素，例如int A[n]={63,34,92,34,44,16,2,39};需要找的第3小数刚好有重复数。  
19.         }  
20.         else  
21.         {  
22.             p=q+1;  
23.             i=i-k;  
24.         }  
25.   
26.     }  
27. }  

每次都选择最大元素作为划分主元，这样就有T(n)=T(0)+T(n-1)+O(n)产生最坏运行时间。

9.3 最坏情况为线性时间的选择算法 

由于书上没有给出代码，经过我研究代码可以这么写，当然对于第3步递归调用SELECT以找到中位数的中位数，不知道怎么实现，所以我就在插入排序函数中对中位数辅助数组B进行排序以便求出中位数的中位数x

9.3最坏情况为线性时间的选择算法的代码 http://blog.csdn.net/z84616995z/article/details/18889535

9.3-1在算法SELECT中，输入元素被分为每组5个元素。如果它们被分为每组7个元素，该算法仍然会是线性时间吗？证明：如果分成每组3个元素，SELECT的运行时间不是线性的。

当被划分为每组7个元素时，类似书中分析有至少有一半大于等于中位数的中位数x，因此在Ceil(n/7)个组中，除了那个所含元素可能少于7的组合包含x的2那个组外，至少有一半的组有4个元素大于x，不计这两个组，大于x元素个数至少为4(Ceil((1/2)Ceil(n/7))-2)≥2n/7-8,类似小于x的元素至少有2n/7-8个，那么最多有5n/7+8元素递归调用SELECT。T(n)≤T(n/7)+T(5n/7+8)+Ο(n),假设有线性时间T(n)≤cn，那么用代换法，T(n)≤cn/7+5nc/7+8c+an=cn+(-nc/7+8c+an) 只要-nc/7+8c+an≤0即可，那么当n≥112时，我们选择c≥14a，T(n)=Ο(n),当n≤112，有T(n)=Θ(1).
当被划分为每组3个元素时，类似上面分析有2(Ceil((1/2)Ceil(n/3))-2)≥n/3-4,至少有2n/3+4个元素参与递归。T(n)≤T(n/3)+T(2n/3+4)+Ο(n)假设T(n)≤cn也有线性时间，则T(n)≤cn+4c+an,由于我们假设的这两个常数是＞0的，所以4c+an无论如何也不可能＜0，所以T(n)≠Ο(n)。所以被划分为3个元素就无法在线性时间内完成选择。所以有此我们知划分最低是5个一组。

9.3-2分析SELECT，并证明：如果n≥140，则至少ceil(n/4)个元素大于中位数的中位数x,至少ceil(n/4)个元素小于x？

由书中知：当n≥140时，3(Ceil((1/2)Ceil(n/5))-2)≥3n/10-6≥2.5n/10+1=n/4+1≥Ceil(n/4),所以至少有Ceil(n/4)个元素大于中位数的中位数
x同理，由书中知，有多少大于x的数，就有多少小于x的数。

9.3-3 假设所有元素都是互异的，说明在最坏情况下，如何才能使快速排序的运行时间为Ο(nlgn)?

最坏情况快速排序的运行时间为Ο(nlgn)的算法http://blog.csdn.net/z84616995z/article/details/18894189

9.3-4 假设对一个含有n个元素的集合，某算法只用比较来确定第i小的元素。证明：无需另外的比较操作，它也能找到比i小的i-1个元素和比i大的n-i个元素。

因为在SELECT函数查找第i个元素时，不断的以辅助中位数数组的中位数x为主元进行划分。必然大于主元x的在右边，小于主元x的在左边。x就是第k小的元素，当待查找元素i=k时，则返回x。如果i≠k，那么继续递归。所以只要找到了第i小元素，那么就会以这个元素作为主元对整个数组进行划分，低区的i-1个元素肯定都是小于主元的，高区n-i个元素肯定都是大于主元的。

9.3-5 假设已经有了一个用于求解中位数的“黑箱”子程序，它在最坏情况下需要线性运行时间。写出一个能解决任意顺序统计量的选择问题的线性时间算法。

请看链接处find函数代表查找中位数子程序SELECT函数代表能解决任意统计量的选择问题线性算法

http://blog.csdn.net/z84616995z/article/details/18889535

9.3-6 对一个含有n个元素的集合来说，所谓k分位数（the kth quantile），就是能把已排序的集合分成k个大小相等的集合的k-1个顺序统计量。给出一个能输出某一集合的这k-1个顺序统计量的O(nlgk)时间的算法。

9.3-6求k分位数 用O(nlgk)时间查找k分位数(所谓k分位数：将n个元素分成k个大小相等的集合的k-1个顺序统计量)

http://blog.csdn.net/z84616995z/article/details/18903483

9.3-7 给出一个O(n)时间的算法，在给定一个有n个不同数字的集合S以及一个正整数k≤n后，它能确定出S中最接近其中位数的k个数

线性时间查找最接近中位数的k个数找出集合S最接近中位数的k(k≤n)个数

http://blog.csdn.net/z84616995z/article/details/18909475

9.3-8 设 x[1..n]和Y[1..n]为两个数组，每个都包含n个已排序的数。给出一个求数组X和Y中所有2n个元素的中位数的O(lgn)时间的算法。

O(lgn)时间内求出两个已排序数组的中位数用O(lgn)时间求出两个已排序数组的中位数

http://blog.csdn.net/z84616995z/article/details/18938181

9.3-9 Olay教授是一家石油公司的顾问。这家公司正在计划建造一条从东向西的大型输油管道，这一管道将穿越一个有n口油井的油田。公司希望有一条管道支线沿着最短路径从每口油井链接到主管道（方向或南或北），给定每口油井的x和y坐标，教授应该如何选择主管道的最优位置，使得各支线的总长度最小？证明：该最优位置可以在线性时间内确定。

设x代表东西向的横坐标，y代表南北向的纵坐标。主管道坐标(x,y)，主管道与支线管道的最短距离d=√(xi-x)^2+(yi-y)^2，由于是最短距离，那么xi=x。也就是di=|yi-y| 。总的距离

d=∑di=∑|yi-y|。要使d最小，那么需要求出数组yi中位数。当n为奇数，那么中位数很容易求得。当n为偶数，那么就是求n/2与n/2+1之间的值。

如何证明呢？ 我们可以用到书中最坏线性时间求第i小元素的方法来求y1,y2..yn这n个数的中位数。最坏线性时间求第i小元素已经在此链接给出