} }
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}的一个排列，如果i 该排列的一个逆序。例如，2, 3, 1有两个逆序:(3, 1)和(2, 1)。设计算法统计给定排列中含 有逆序的个数。 //用归并进行排序 //当一个子集的一个数大于第二个子集的一个数，为逆序，即a[i]>a[j] //则逆序数为end-j+1; #include 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 cout< gelei(k+1); a[k]='0'?'1':'0'; //取反