内容发布更新时间 : 2024/12/23 14:30:54星期一 下面是文章的全部内容请认真阅读。
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