算法分析与设计实践大作业
1. 问题
圆排列问题：给定n个圆的半径序列，将它们放到矩形框中，各圆与矩形底边相切，求具有最小排列长度的圆排列。
2. 解析
首先，已知圆的个数n以及记录各圆半径的数组r[i],i=1~n ，记录各圆圆心横坐标的数组x[i],i=1~n。要记录最短排列长度minlen，最终求出排列顺序。要注意，只要大小合适，目标圆就有可能与排列中的任意一个圆相切。要求x[n]时，要从前往后的一一比较，先得到x[1]+a1的值，再得到x[2]+a2的值……一直到x[n-1]+an-1的值，与上一次的值相比较，若距离更大则更新，否则不做处理。
圆排列的解空间是一棵排列树。假设有n个圆排列：1，2，3……n。只要计算出n！/2种排列：
所以，只要知道第一个和第n个位置的数，那么排列时，就只剩下第2个到第n-1个位置。
另外，如果有m个圆的半径相同，那么交换后总长度也相同，所以只要计算一个。
如果有n个圆，前m个已经排好位置，那么还有n-m个待排序定位。当搜索到第m+1个圆时：
两个长度相加就是新的最短长度。
3. 设计
求每个圆的圆心坐标：
计算当前圆排列的长度：
回溯：
4. 分析
时间复杂度：
在回溯算法中，搜索子结点的时间复杂度是O(n!)次，而Backtrack()函数每次计算需要O(n)计算时间，从而整个算法的计算时间复杂性为O((n+1)!)。
空间复杂度：
由于r[]数组，x[]数组的大小都为n，故空间复杂度为O(n)。
5. 源码
https://github.com/kekekeQWQ/14