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 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 int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low while (low 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 void partions(int a[],int low,int high) { //进行一趟快排 int prvotkey=a[low]; a[0]=a[low]; while (low