算法设计与分析习题答案1-6章

{

while (low

a[low]=a[high];

while (low=prvotkey) ++low;

a[high]=a[low]; }

a[low]=prvotkey;

//如果s1（大的数集）的的个数大于n/2 if(low>=n/2) {

for(int i=0;i<=n/2-low-1;++i) {

for(int j=0;j

//如果s1（大的数集）的的个数小于n/2 else

for(int i=0;i<=n/2-low-1;++i) {

for(int k=n-1;ka[k-1]) { int temp1=a[k]; a[k]=a[k-1]; a[k-1]=temp1; } }//for } }

int main() { int a[n]={1,3,5,9,6,0,-11,-8}; partions(a,0,n-1); for(int i=0;i

if(i<4) {

cout<<\属于子集s1的：\ cout<

cout<<\属于子集s2的：\ cout<

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、