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

using namespace std;

int data[100];

//在m个数中输出n个排列数（n<=m） void DPpl(int num,int m,int n,int depth) {

if(depth==n) {

for(int i=0;i

for(int j=0;j

if((num&(1<

DPpl(num+(1<

int main() {

DPpl(0,5,1,0); DPpl(0,5,2,0); DPpl(0,5,3,0); DPpl(0,5,4,0); DPpl(0,5,5,0);

return 0; }

8. 设计分治算法求解一维空间上n个点的最近对问题。

参见4.4.1最近对问题的算法分析及算法实现

9. 在有序序列(r1, r2, ?, rn)中，存在序号i（1≤i≤n），使得ri=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n)。 //在有序数组中

//采用二分法查找符合条件的元素

#include using namespace std;

void Findnum(int *a,int n) {

int low=0; int high=n-1;

while(low<=high) {

int mid=(low+high)/2; if(a[mid]==mid) { cout<<\这个数是： \ break; } else if(a[mid]>mid) high=mid-1; else low=mid+1; } }

int main() { int a[7]={1,0,2,5,6,7,9}; Findnum(a,7); return 0; }

时间复杂度为O(log2n)。

10. 在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间复杂性。

//先对序列进行快速排序 //再进行一次遍历 //输出众数的重复次数

#include using namespace std;

int partions(int b[],int low,int high) {

int prvotkey=b[low];

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