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

b[0]=b[low]; while (low

while (low=prvotkey) --high;

b[low]=b[high];

while (low

b[high]=b[low]; }

b[low]=b[0]; return low; }

void qsort(int l[],int low,int high) {

int prvotloc; if(low

prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); //递归调用排序 由low 到prvotloc-1 qsort(l,prvotloc+1,high); //递归调用排序 由 prvotloc+1到 high

} }

void quicksort(int l[],int n) {

qsort(l,1,n); //第一个作为枢轴 ，从第一个排到第n个 }

int main() {

int a[10]={1,2,3,5,3,3,3,2,5,1}; int i=0;

int count=0;

int max=0;//max表示出现的次数 qsort(a,0,10); while(i<10) { int j; j=i+1;

if(a[i]=a[j]&&i<10) { count++; i++; } if(count>max) { max=count; count=0; } }//while

cout<<\重复次数：\

return 0; }

时间复杂度nlog(n)

11. 设M是一个n×n的整数矩阵，其中每一行（从左到右）和每一列（从上到下）的元素都按升序排列。设计分治算法确定一个给定的整数x是否在M中，并分析算法的时间复杂性。

12. 设S是n（n为偶数）个不等的正整数的集合，要求将集合S划分为子集S1和S2，使得| S1|=| S2|=n/2，且两个子集元素之和的差达到最大。

//先用快速排序进行一趟排序

//如果s1（大的数集）的的个数大于n/2 //将（i<=n/2-low-1）个最小的数排到后面 //如果s1（大的数集）的的个数小于n/2 //将s2（小的数集）n/2-low-1排到前面 //将排好的数组的前n/2个数赋值给s1 //将排好的数组的后n/2个数赋值给s2

#include using namespace std; const int n=8;

void partions(int a[],int low,int high) { //进行一趟快排 int prvotkey=a[low]; a[0]=a[low]; while (low

{

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的