算法设计与分析（第2版） 王红梅 胡明 习题答案

} } return 0; }

13. 设a1, a2,?, an是集合{1, 2, ?, n}的一个排列，如果iaj，则序偶(ai, aj)称为该排列的一个逆序。例如，2, 3, 1有两个逆序：(3, 1)和(2, 1)。设计算法统计给定排列中含有逆序的个数。

//用归并进行排序

//当一个子集的一个数大于第二个子集的一个数，为逆序，即a[i]>a[j] //则逆序数为end-j+1;

#include using namespace std;

int count;

void Merge(int a[],int a1[],int begin,int mid,int end)//合并子序列 {

int i=begin,j=mid+1,k=end; while(i<=mid&&j<=end) {

if(a[i]<=a[j]) a1[k++]=a[i++];//取a[i]和a[j]中较小者放入r1[k] else { a1[k++]=a[j++]; count+=(end-j+1); } }

while(i<=mid) a1[k++]=a[i++]; while(j<=end) a1[k++]=a[j++]; }

void MergeSort(int a[ ], int begin, int end) {

int mid,a1[1000]; if(begin==end) return ; else

{ mid=(begin+end)/2; MergeSort(a,begin,mid); MergeSort(a,mid+1,end); Merge(a,a1,begin,mid,end); } }

int main() { int a[6]={6,5,4,3,2,1}; count=0; MergeSort(a,0,6); cout<

14. 循环赛日程安排问题。设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：

（1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能赛一次。

采用分治方法。

将2^k选手分为2^k-1两组，采用递归方法，继续进行分组，直到只剩下2个选手时，然后进行比赛，回溯就可以指定比赛日程表了

15. 格雷码是一个长度为2n的序列，序列中无相同元素，且每个元素都是长度为n的二进制位串，相邻元素恰好只有1位不同。例如长度为23的格雷码为(000, 001, 011, 010, 110, 111, 101, 100)。设计分治算法对任意的n值构造相应的格雷码。

//构造格雷码

#include using namespace std;

int n;

char a[100]; void gelei(int k) {

if(k==n) {

cout<

}

gelei(k+1);

a[k]='0'?'1':'0'; //取反

gelei(k+1); }

int main() {

while(cin>>n && n != 0) { memset(a,'0',sizeof(a)); //初始化，全部置零

a[n] ='\\0'; gelei(0); cout<

return 0; }

16. 矩阵乘法。两个n×n的矩阵X和Y的乘积得到另外一个n×n的矩阵Z，且Zij 满足 （1≤i, j≤n），这个公式给出了运行时间为O(n3)的算法。可以用分 治法解决矩阵乘法问题，将矩阵X和Y都划分成四个n/2×n/2的子块，从而X和Y的乘积可以用这些子块进行表达，即

从而得到分治算法：先递归地计算8个规模为n/2的矩阵乘积AE、BG、AF、BH、CE、DG、CF、DH，然后再花费O(n2)的时间完成加法运算即可。请设计分治算法实现矩阵乘法，并分析时间性能。能否再改进这个分治算法？

习题5

1. 下面这个折半查找算法正确吗？如果正确，请给出算法的正确性证明，如果不正确，请

说明产生错误的原因。

int BinSearch(int r[ ], int n, int k) {

int low = 0, high = n - 1; int mid;

while (low <= high)

{

mid = (low + high) / 2; if (k < r[mid]) high = mid;

else if (k > r[mid]) low = mid;

else return mid; }

return 0;

}

错误。 正确算法：

int BinSearch1(int r[ ], int n, int k) {

int low = 0, high = n - 1; int mid;

while (low <= high) {

mid = (low + high) / 2; if (k < r[mid]) high = mid - 1;

else if (k > r[mid]) low = mid + 1;

else return mid; }

return 0; }

2. 请写出折半查找的递归算法，并分析时间性能。

//折半查找的递归实现

#include using namespace std;

int digui_search(int a[],int low,int high,int x) {

if (low > high) return 0;

int mid = (low+high)/2; if (a[mid] == x) return mid;

else if (a[mid] < x)

digui_search(a,low,mid-1,x); else

digui_search(a,mid+1,high,x); }