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

} }

int main() {

int a[n]={1,3,5,9,6,0,-11,-8};

partions(a,0,n-1); for(int i=0;i

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

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

13. 设a, a,?, a是集合{1, 2, ?, n}的一个排列，如果ia，则序偶(a, a)称为12nijij

该排列的一个逆序。例如，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<

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

要求的比赛日程表:

(1)每个选手必须与其他n-1个选手各赛一次;

(2)每个选手一天只能赛一次。 采用分治方法。

将2^k选手分为2^k-1两组，采用递归方法，继续进行分组，直到只剩下2个选手时，然

后进行比赛，回溯就可以指定比赛日程表了

n15. 格雷码是一个长度为2的序列，序列中无相同元素，且每个元素都是长度为n的

3二进制位串，相邻元素恰好只有1位不同。例如长度为2的格雷码为(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'; //取反