} } return 0; }
13. 设a1, a2,?, an是集合{1, 2, ?, n}的一个排列，如果i
//用归并进行排序
//当一个子集的一个数大于第二个子集的一个数，为逆序，即a[i]>a[j] //则逆序数为end-j+1;
#include
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 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 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); }