算法设计与分析（王佳）《算法分析与设计》实验一.docxVIP

《算法分析与设计》实验一 问题一：集合划分问题 实验目的： 通过对集合划分问题的算法的设计，进一步熟悉理解并灵活运用递归与分治策略，掌握该算法思想的核心内容。 实验内容： 1）内容描述：n 个元素的集合{1,2,., n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2， 3，4}可以划分为15 个不同的非空子集如下： {{1}，{2}，{3}，{4}}， {{1，2}，{3}，{4}}， {{1，3}，{2}，{4}}， {{1，4}，{2}，{3}}， {{2，3}，{1}，{4}}， {{2，4}，{1}，{3}}， {{3，4}，{1}，{2}}， {{1，2}，{3，4}}， {{1，3}，{2，4}}， {{1，4}，{2，3}}， {{1，2，3}，{4}}， {{1，2，4}，{3}}， {{1，3，4}，{2}}， {{2，3，4}，{1}}， {{1，2，3，4}} 2）编程任务：给定正整数n 和m，计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。 3）数据输入： 元素个数n 和非空子集数m。 4）结果输出: 计算出共有多少个不同的由m 个非空子集组成的集合。 问题二：输油管道问题 实验目的： 通过对计算最短输油管道长度问题的算法的设计，进一步熟悉理解并灵活运用递归与分治策略，掌握该算法思想的核心内容。 实验内容： 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置, 即使各油井到主管道之间的输油管道长度总和最小的位置? 1）编程任务： 给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。 2）数据输入： 油井数量n，每口油井的横坐标xi,纵坐标yi 3）结果输出: 油井到主管道之间的输油管道最小长度总和。 示例输入输出： 输入 5 1 2 3 5 3 7 3 4 2 7 输出 8 参考代码 问题一： #include iostream using namespace std; int F(int n,int m) { if(n==1) return 1; if(m==1||n==m) return 1; else return F(n-1,m-1)+m*F(n-1,m); } int main() { int n,m; int result = 0; cout请输入元素个数n＝; cinn; cout请输入非空子集个数m＝; cinm; cout非空子集个数为：F(n,m)endl; return 0; } 问题二： #includeiostream #includecmath using namespace std; void swap(inta,intb) { int t=a; a=b; b=t; } int partition(double a[],int l,int r) { int i = l-1,j=r; int v = a[r]; while(true) { while(a[++i]v); while(a[--j]v) if(j==l) break; if(i=j)break; swap(a[i],a[j]); } swap(a[i],a[r]); return i; } void qsort(double a[],int l,int r) { int i; if(r=l) return ; i=partition(a,l,r); qsort(a,l,i-1); qsort(a,i+1,r); } void pipesLength(double a[],int n) { double my;//主管道的y坐标 double minlength = 0; int i; //对油井的y坐标进行排序 qsort(a,0,n-1); if(n%2!=0) { //当个数为奇数时 my=a[n/2]; } else my = (double)(a[n/2-1]+a[n/2])/2;//个数为偶数 for(i = 0;in;i++) { minlength += fabs(my - a[i]); } coutmyendl; coutminlengthendl; } int main() { int n,i; double x[100]; double y[100]