算法分析实验八报告

《算法分析实验八报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》实验报告算法过程设计.四、程序调试及结果（附截图）源代码（附源代码）.一、实验内容描述和功能分析.1.排列树问题内容描述：试设计一个用回溯法搜索排列空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解圆排列问题。圆排列问题描述如下：给定n个大小不等的圆cl，c2,..・，cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3,且所给的3个圆的半径分别为1,L2时，这3个圆的最小长度的圆排列是1,2,1，

2、其最小长度为2+4*sqr(2)o编程任务：对于给定的n(n<10)个圆，编程计算最小长度排列。功能分析：输入由多组测试数据组成。每组测试数据输入的第一行是1个正整数n，表示有n个圆。第2行有n个正数，分别裹示n个圆的丰径。对应每组输入，输出的每行是计算出的最小长度，保留3位小数。例如：输入：3输出：7.657112二、算法过程设计.1.排列树问题排列树问题是通过设置相关数组，调用库函数来解决问题。三、程序调试及结果(附截图).1•排列树问题

3、c°C::IDocuMerrtsand1217.65759143829106.940源代码（附源

4、代码）.1•排列树问题#include#include#includeusingnamespacestd;floatMin;vectorx;vectorr;intn;HoatCenter(intt){floattemp=0;for(intj=0;jtemp)temp=valuex;}returntemp;IvoidComputer(){floatlow=0

5、,high=0;for(inti=0;ihigh)high=x[i]+r[i];}if(high-lown-1)Compute");elsefor(intj=t;j

6、t+1);swap(r[t],r[j]);intmain()while(cin»n){Min=9999;x.resize(n);r.resize(n);for(inti=0;i