算法设计与分析第三章：分治法

港控/mmm° 2023-06-11 05:25 81阅读 0赞

算法分析与设计实验报告  
第 三 次实验  
姓名 裴朵朵 学号 5001170016 班级 计科一班  
时间 2019.10 地点

实验名称 分治法及其应用  
实验目的 1、理解分治法的概念、原理方法。  
2、掌握分治法的使用规律与编程技巧  
3.能够应用分治法求解日常生活中问题

实验原理 1.设计一个算法，利用分治法求一个整数序列中的最大和最小元素  
2.设计一个算法，采用分治法求x^n  
3.有n个互不相同的整数，按递增顺序存放在数组a\[1,n-1\]中，若存在一个下标i(0<=i<=n) ,使得a\[i\]=i,设计一个算法以O（log2n)时间找到这个下标  
4.对于大于1的正整数n，可以分解为n=x1*x2*x3\*…*xm,其中xi>=2。例如，n=12时有8种不同的分解式，即12=12,12=6*2;12=4*3,12=3*4,12=3*2*2,12=2*6,12=2*3*2,12=2*2\*3,设计一个算法求n的不同分解式个数。  
5.给定一个整数序列，每个元素出现的次数称为众数。编写一个实验程序对递增有序序列a求众数。例如S=\{1,2,2,2,3,5\},多重集S的众数是2，其中重数是3  
6.给定一个整数数组A=(a0,a1…an-1),若i<j且ai>aj,则<ai,aj>就为一个逆序列对。例如数组（3，1，4，5，2）的逆序列对有<3,1>、❤️,2>,<4,2>,<5,2>。编写一个实验程序采用分治法求A中逆序对的个数，即逆序数  
7.求解半数集问题：给定一个自然数n，由n可以依次产生半数集set(n)中的数如下：(1)n属于set(n)。(2)在n的左边加一个自然数，但该自然数不能超过最近添加的数的一半。(3)按此规则进行处理，直到不能再添加自然数为止。例如，set(6)=\{6,16,26,126,36,136\},半数集set(6)中有6个元素。编写一个实验程序求给定n时对应半数集中元素的个数。  
8. 快速排序：分治法，将待排序数组通过一次排序分为两段，用相同方法排序 。  
9.对于给定的含有n个元素的无序序列，求这个序列中最大和次大的两个不同元素  
10.折半查找：要求元素有序

实验步骤 1.将数组a均分为s1和s2，求解s1和s2中的最大和最小值，最终的最大和最小值可以在s1和s2中的最大最小值中比较得到；对于s1和s2中的最大最小值，可以用同样的方法得到。  
2.当n=1时，结果为x；当n为奇数时，结果为f(x,n)=f(x,(n-1)/2)\*f(x,(n-1)/2)\*x;当n为偶数时，结果为f(x,n/2)\*f(x,n/2)  
3.采用二分查找法。a\[i\]=i时表示该元素在有序非重复序列a中恰好第i大。对于序列a\[low…high\],mid=(low+high)/2,若a\[mid\]=mid表示查找到该元素；若a\[mid\]>mid,说明右区间的所有元素都大于其位置，只能在左区间中查找；若a\[mid\]<mid，说明左区间的所有元素都小于其位置，只能在右区间中查找  
4.f(n)为n的所有因数的不同分解式个数之和，f(1)=1,是递归的出口  
5.count记录最大的重数，count1记录每个元素的重数，相同大小的元素记录完重数后，count1与count比较，若count1>count，则count1成为新的count，接下来进行下一个不同数值的比较，直到数组遍历完毕；如果count1=count,则表示最大重数有两个或多个，定义数组记录最大重数的数值  
6.定义两个变量i和j，最大值分别是n-1和n,从第一个元素开始，依次与其后面的元素比较大小，若符合逆序数的条件，则count加1  
7.半数集set(n)中元素个数的求解是个递归的过程，设set(n)中的元素个数为f(n),则明显有递归表达式：f(n)=1+∑f(i)，i=1,2……n/2  
8.先将数列中的第一个数作为基准， 将a\[0\]中的数保存到tmp中，可以理解为在a\[0\]上挖了个坑，可以将其他数据填充过来，从j开始向前找一个比tmp小或者等于tmp的数，找到符合条件的数时，将其位置挖坑，它本身填到a\[0\]位置上，然后从i开始找一个大于tmp的数，将其挖坑，其本身填到上一个坑中，直到a\[i\]=a\[j\]，将tmp填到a\[i\]中，这样就完成了一次排序，然后递归调用。  
9.若只有一个元素，则此元素是最大元素，没有元素；若只有两个元素，则最大元素为两个之中的较大者，次大元素为两个之中的较小者；若有两个以上元素，则分为\[low…mid\],\[mid+1…high\]，分别求出两边的最大值和次大值，左右最大值相互比较，左右次大值相互比较，递归进行，依次比较，直到结束  
10.首先确定元素的中间位置mid，将待查找元素与mid比较，若相等，则找到；若比mid小，则带查找元素在0…mid之间，查找0…mid的中间元素；若比mid大，则在mid+1…high之间，查找mid+1…high的中间值,依次进行

关键代码 1-1  
void MaxMin(int a\[\],int low,int high,int &maxe,int &mine)  
\{  
if(lowhigh) //只有一个元素  
\{  
maxe=a\[low\];  
mine=a\[low\];  
\}  
else if(lowhigh-1)//只有两个元素  
\{  
maxe=max(a\[low\],a\[high\]);  
mine=min(a\[low\],a\[high\]);

}
    else
    {
    	int mid=(low+high)/2;
    	int lmaxe,lmine;
    	MaxMin(a,low,mid,lmaxe,lmine);
    	int rmaxe,rmine;
    	MaxMin(a,mid+1,high,rmaxe,rmine);
    	maxe=max(lmaxe,rmaxe);
    	mine=min(lmine,rmine);
     }

\}  
1-2.  
double solve(double x,int n)  
\{  
double f;  
if(n1)//n是1的时候  
\{  
return x;  
\}  
if(n%20)  
\{  
f=solve(x,n/2);  
return f*f;  
\}  
else  
\{  
f=solve(x,(n-1)/2);  
return f*f\*x;  
\}  
\}  
1-3  
int Search(int a\[\],int n) //查找a\[i\]=i;  
\{  
int low=0;  
int high=n-1;  
int mid;  
while(low<=high)  
\{  
mid=(low+high)/2;  
if(a\[mid\]mid)  
\{  
return mid;  
\}  
else if(a\[mid\]<mid)  
\{  
low=mid+1;  
\}  
else  
\{  
high=mid-1;  
\}  
\}  
\}  
1-4.  
public class YinShu  
\{  
int solve(int n)  
\{  
if(n1) return 1;  
else  
\{  
int sum=0;  
for(int i=2;i<=n;i++)  
if(n%i==0)  
\{  
sum=sum+solve(n/i);  
\}

return sum;
       }
     }

\}  
1-5  
int solve(int a\[\],int n)  
\{  
int i;  
int j=-1;//j表示众数的个数  
int count=1;//记录最大重数  
int count1=1; //记录每个元素的重数值  
for(i=0;i<n-1;)  
\{  
while(a\[i\]a\[i+1\])//当遇到相同元素时，开始计算这个数值的重数  
\{  
count1++;//找到相同元素，该元素的重数加1  
i++;  
\}//直到同一个数值的重数计算完毕，退出循环  
if(count1>count)  
\{  
count=count1;  
j=1;  
elem\[j\]=a\[i\];  
\}  
else if(count1count)  
\{  
j++;  
elem\[j\]=a\[i\];  
\}  
count1=1;//将count1重置，记录下一个元素的重数  
i++;  
\}  
return j;  
\}  
1-6  
int solve(int a\[\],int n)  
\{  
int count=0;  
for(int i=0;i<n-1;i++)  
\{  
for(int j=i+1;j<n;j++)  
\{  
if(a\[i\]>a\[j\])  
\{  
count++;  
\}  
\}  
\}  
return count;  
\}  
1-7  
int comp(int n)  
\{  
int ans = 1;  
//说明已在之前求解过  
if (a\[n\] > 0)  
\{  
return a\[n\];  
\}  
for (int i = 1; i <= n/2; i++)  
\{  
ans += comp(i);  
\}  
//存储结果  
a\[n\] = ans;  
return ans;  
\}  
1-8  
int solve(int a\[\],int s,int t)//划分算法  
\{  
int i=s;  
int j=t;  
int tmp=a\[s\];//用序列的第1个记录作为基准  
while(i!=j)//从序列两端交替向中间扫描，直到i=i为止  
\{  
while(i<j&&a\[j\]>=tmp)  
\{  
j–;//j向左移动，直到找到a\[j\]<tmp  
\}  
a\[i\]=a\[j\];//将a\[j\]放到a\[i\]的位置  
while(i<j&&a\[i\]<=tmp)  
\{  
i++;//从左向右扫描，找到第一个大于tmp的值  
\}  
a\[j\]=a\[i\];//将此数放到a\[i\]位置，它本身的位置挖坑  
\}  
a\[i\]=tmp;  
return i;  
\}  
1-9.  
\#include <stdio.h>  
\#include <limits.h>  
\#include  
using namespace std;  
void solve(int a\[\],int low,int high,int &max1,int &max2)  
\{  
if(lowhigh)//区间只有一个元素  
\{  
max1=a\[low\];  
max2=INT\_MIN;  
\}  
else if(lowhigh-1)//区间只有两个元素  
\{  
max1=max(a\[low\],a\[high\]);  
max2=min(a\[low\],a\[high\]);  
\}  
else//区间有两个以上元素  
\{  
int mid=(low+high)/2;  
int lmax1,lmax2;  
solve(a,low,mid,lmax1,lmax2);//左区间求1max1和1max2  
int rmax1,rmax2;  
solve(a,mid+1,high,rmax1,rmax2);//右区间求rmax1和rmax2  
if(lmax1>rmax1)  
\{  
max1=lmax1;  
max2=max(lmax2,rmax1);  
\}  
else  
\{  
max1=rmax1;  
max2=max(lmax1,rmax2);  
\}

\}  
\}  
1-10  
\#include <stdio.h>  
int solve(int a\[\],int low,int high,int k)  
\{  
int mid;  
if(low<=high)  
\{  
mid=(low+high)/2;  
if(a\[mid\]==k)  
\{  
return mid;  
\}  
else if(a\[mid\]>k)  
\{  
return solve(a,low,mid,k);  
\}  
else  
\{  
return solve(a,mid+1,high,k);  
\}

}
    else return -1;

测试结果 1.

1.  
2.  
3.  
4.

实验心得 加深了对分治法的理解，通过自己动手编程练习，初步掌握了分治法的内涵，学会编写经典程序，在今后下一章的学习中，还要接着练习本章分治法的内容，达到熟练掌握，有所提高。

附录：完整程序代码，依次按照题目序号 1-1 1-2  
1-1.  
\#include <stdio.h>  
\#define max(x,y) ((x)>(y)?(x):(y))  
\#define min(x,y) ((x)<(y)?(x):(y))  
//求a中的最大最小元素  
void MaxMin(int a\[\],int low,int high,int &maxe,int &mine)  
\{  
if(lowhigh) //只有一个元素  
\{  
maxe=a\[low\];  
mine=a\[low\];  
\}  
else if(lowhigh-1)//只有两个元素  
\{  
maxe=max(a\[low\],a\[high\]);  
mine=min(a\[low\],a\[high\]);

int main()

\{  
int a\[\]=\{7,3,9,2,4\};  
int n=sizeof(a)/sizeof(a\[0\]);  
int maxe,mine;  
MaxMin(a,0,n-1,maxe,mine);  
printf(“最大值是：%d, 最小值是：%d\\n”,maxe,mine);  
return 0;  
\}  
1-2.  
//求x^n  
\#include <stdio.h>  
double solve(double x,int n)  
\{  
double f;  
if(n1)//n是1的时候  
\{  
return x;  
\}  
if(n%20)  
\{  
f=solve(x,n/2);  
return f*f;  
\}  
else  
\{  
f=solve(x,(n-1)/2);  
return f*f\*x;  
\}  
\}  
int main()  
\{  
double a;  
int b;  
printf(“请输入x和n的值：\\n”);  
scanf("%lf",&a);  
scanf("%d",&b);  
printf(“输出结果是：\\n”);  
for(int i=1;i<=b;i++)  
\{  
printf("%.2f的%d次方是：%.2f\\n",a,i,solve(a,i));//小数点后保留2位  
\}  
return 0;

\}  
1-3  
\#include <stdio.h>  
int Search(int a\[\],int n) //查找a\[i\]=i;  
\{  
int low=0;  
int high=n-1;  
int mid;  
while(low<=high)  
\{  
mid=(low+high)/2;  
if(a\[mid\]mid)  
\{  
return mid;  
\}  
else if(a\[mid\]<mid)  
\{  
low=mid+1;  
\}  
else  
\{  
high=mid-1;  
\}  
\}  
\}  
int main()  
\{  
int a\[\]=\{-3,0,1,3,5,6\};  
int b\[\]=\{-2,0,1,4,5,6\};  
int n=sizeof(a)/sizeof(a\[0\]);  
int i=Search(a,n);  
printf(" 检索得到的结果是：\\n");  
if(i!=-1)  
\{  
printf(“存在a\[%d\]=%d\\n”,i,i);  
\}  
else  
\{  
printf(“不存在 a\[%d\]=%d\\n”,i,i);  
\}  
\}  
1-4.  
public class YinShu  
\{  
int solve(int n)  
\{  
if(n1) return 1;  
else  
\{  
int sum=0;  
for(int i=2;i<=n;i++)  
if(n%i==0)  
\{  
sum=sum+solve(n/i);  
\}

return sum;
       }
     }

\}  
import java.util.Scanner;  
import java.util.\*;  
public class Test  
\{  
public static void main(String args\[\])  
\{  
System.out.printf(“请输入你要求解的数：”);  
Scanner sc=new Scanner(System.in);  
YinShu ys=new YinShu();  
int n=sc.nextInt();  
int result=ys.solve(n);  
System.out.println(“结果是：”+result);  
\}

\}  
1-5  
\#include <stdio.h>  
int elem\[100\];//记录众数  
int solve(int a\[\],int n)  
\{  
int i;  
int j=-1;//j表示众数的个数  
int count=1;//记录最大重数  
int count1=1; //记录每个元素的重数值  
for(i=0;i<n-1;)  
\{  
while(a\[i\]a\[i+1\])//当遇到相同元素时，开始计算这个数值的重数  
\{  
count1++;//找到相同元素，该元素的重数加1  
i++;  
\}//直到同一个数值的重数计算完毕，退出循环  
if(count1>count)  
\{  
count=count1;  
j=1;  
elem\[j\]=a\[i\];  
\}  
else if(count1count)  
\{  
j++;  
elem\[j\]=a\[i\];  
\}  
count1=1;//将count1重置，记录下一个元素的重数  
i++;  
\}  
return j;  
\}  
int main()  
\{  
int arr\[\]=\{1,2,2,2,2,4,5,6,6\};  
int num=solve(arr,9);  
int s=sizeof(arr)/sizeof(int);

for(int i=0;i<=s;i++)
    {
    	printf("众数为:%d ",elem[i]);
    }
    
    return 0;

\}  
1-6  
\#include <stdio.h>  
int solve(int a\[\],int n)  
\{  
int count=0;  
for(int i=0;i<n-1;i++)  
\{  
for(int j=i+1;j<n;j++)  
\{  
if(a\[i\]>a\[j\])  
\{  
count++;  
\}  
\}  
\}  
return count;  
\}  
int main()  
\{  
int arr\[\]=\{3,4,2,5,6,7,1\};  
int s=sizeof(arr)/sizeof(int);

printf("此序列中存在的逆序数是：%d",solve(arr,s));
    return 0;

\}  
1-7.  
\#include  
using namespace std;  
int a\[1000\];  
int comp(int n);  
int main()  
\{  
int n;  
cin>>n;  
cout<<comp(n)<<endl;  
system(“pause”);  
\}  
int comp(int n)  
\{  
int ans = 1;  
//说明已在之前求解过  
if (a\[n\] > 0)  
\{  
return a\[n\];  
\}  
for (int i = 1; i <= n/2; i++)  
\{  
ans += comp(i);  
\}  
//存储结果  
a\[n\] = ans;  
return ans;  
\}  
1-8.  
\#include <stdio.h>  
void disp(int a\[\],int n) //输出a中的所有元素  
\{  
int i;  
for(i=0;i<n;i++)  
\{  
printf("%d “,a\[i\]);  
\}  
printf(”\\n");  
\}  
int solve(int a\[\],int s,int t)//划分算法  
\{  
int i=s;  
int j=t;  
int tmp=a\[s\];//用序列的第1个记录作为基准  
while(i!=j)//从序列两端交替向中间扫描，直到i=i为止  
\{  
while(i<j&&a\[j\]>=tmp)  
\{  
j–;//j向左移动，直到找到a\[j\]<tmp  
\}  
a\[i\]=a\[j\];//将a\[j\]放到a\[i\]的位置  
while(i<j&&a\[i\]<=tmp)  
\{  
i++;//从左向右扫描，找到第一个大于tmp的值  
\}  
a\[j\]=a\[i\];//将此数放到a\[i\]位置，它本身的位置挖坑  
\}  
a\[i\]=tmp;  
return i;  
\}  
void QuickSort(int a\[\],int s,int t)  
\{  
if(s<t)  
\{  
int i=solve(a,s,t);  
QuickSort(a,s,i-1);//对左子序进行递归排序  
QuickSort(a,i+1,t);//对右子序递归排序  
\}  
\}  
int main()  
\{  
int n=7;  
int a\[\]=\{2,5,1,7,10,6,9\};  
printf(“排序前：”);  
disp(a,n);  
QuickSort(a,0,n-1);  
printf(“排序后：”);  
disp(a,n);  
return 0;

\}  
1-9.  
\#include <stdio.h>  
\#include <limits.h>  
\#include  
using namespace std;  
void solve(int a\[\],int low,int high,int &max1,int &max2)  
\{  
if(lowhigh)//区间只有一个元素  
\{  
max1=a\[low\];  
max2=INT\_MIN;  
\}  
else if(lowhigh-1)//区间只有两个元素  
\{  
max1=max(a\[low\],a\[high\]);  
max2=min(a\[low\],a\[high\]);  
\}  
else//区间有两个以上元素  
\{  
int mid=(low+high)/2;  
int lmax1,lmax2;  
solve(a,low,mid,lmax1,lmax2);//左区间求1max1和1max2  
int rmax1,rmax2;  
solve(a,mid+1,high,rmax1,rmax2);//右区间求rmax1和rmax2  
if(lmax1>rmax1)  
\{  
max1=lmax1;  
max2=max(lmax2,rmax1);  
\}  
else  
\{  
max1=rmax1;  
max2=max(lmax1,rmax2);  
\}

\}  
\}  
int main()  
\{  
int a\[\]=\{7,3,9,2,4,6\};  
int n=sizeof(a)/sizeof(a\[0\]);  
int max01,max02;  
solve(a,0,n,max01,max02);  
printf(“最大值是：%d,次大值是：%d\\n”,max01,max02);  
return 0;  
\}  
1-10  
\#include <stdio.h>  
int solve(int a\[\],int low,int high,int k)  
\{  
int mid;  
if(low<=high)  
\{  
mid=(low+high)/2;  
if(a\[mid\]==k)  
\{  
return mid;  
\}  
else if(a\[mid\]>k)  
\{  
return solve(a,low,mid,k);  
\}  
else  
\{  
return solve(a,mid+1,high,k);  
\}

}
    else return -1;

int main()  
\{  
int n=10;  
int i;  
int k=6;  
int a\[\]=\{1,2,3,4,5,6,7,8,9,10\};  
i=solve(a,0,n-1,k);  
if(i>=0)  
\{  
printf(“a\[%d\]=%d\\n”,i,k);  
\}  
else  
\{  
printf(“未找到%d元素\\n”,k);  
\}  
return 0;  
\}

项目 比例 成绩  
学习态度 10% 积极 一般 较差  
算法设计及结果 50% 功能正确 功能基本正确 错误  
内容完整性 20% 完整 基本完整 不完整  
报告规范性 20% 规范 基本规范 不符合要求  
成绩