圆排列问题-回溯法

问题描述:

    给定n个大小不等的圆 c1 c2 c3 c4 要将n个圆排进一个矩形框中,且要求底边相切。找出有最小长度的圆排列。

    例如:当n=3,且所给的3个圆半径分别为1,1,2时,这3个圆的最小长度的圆排列 最小长度为2+4根号2.

算法设计:

    设开始的a =【r1,r2,r3,r4...rn】是所给的n歌圆半径。

    CirclePerm(n,a)返回最小长度。

    Center计算当前选择的圆中心的横坐标。

    Compute计算当前圆排列的长度。

    数组r当前圆排列。

算法描述:

#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
class Circle{
 
friend float CirclePerm(int ,float *);
 
private:
float Center(int t);
void Compute(void);
void Backtrack(int t);
float min,*x,*r;
int n;
};
float Circle::Center(int t)
{
float temp = 0;
for(int j=1;j<t;j++)
{
float valuex=x[j]+2.0*sqrt(r[t]*r[j]);
if(valuex > temp)
temp = valuex;
}
return temp;
}
void Circle::Compute(void)
{
float low = 0,
high = 0;
for(int i=1;i<=n;i++)
{
if(x[i]-r[i] < low)
low = x[i]-r[i];
if(x[i]+r[i] > high)
high = x[i]+r[i];
}
if(high-low < min)
min = high-low;
}
void Circle::Backtrack(int t)
{
if(t>n)
Compute();
else
for(int j=t;j<=n;j++)
{
swap(r[t],r[j]);
float centerx = Center(t);
if(centerx+r[t]+r[1]<min)
{
x[t] = centerx;
Backtrack(t+1);
}
swap(r[t],r[j]);
}
}
float CirclePerm(int n,float *a)
{
Circle X;
X.n = n;
X.r = a;
X.min = 100000;
float *x = new float [n+1];
X.x = x;
X.Backtrack(1);
delete [] x;
return X.min;
}
int main()
{
int n;
cout<<"please enter your numbers!:";
cin>>n;
float *p = new float [n+1];
cout<<"please enter your circles:";
for(int i=0;i<n;i++)
{
cin>>p[i];
}
cout<<CirclePerm(n,p)<<endl;
delete [] p;
return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Codeforces Round #411 (Div. 2)(A,B,C,D 四水题)

A. Fake NP time limit per test:1 second memory limit per test:256 megabytes inpu...

32260
来自专栏聊聊技术

原 HDOJ 1002 A + B Pro

311110
来自专栏青玉伏案

算法与数据结构(四) 图的物理存储结构与深搜、广搜(Swift版)

开门见山,本篇博客就介绍图相关的东西。图其实就是树结构的升级版。上篇博客我们聊了树的一种,在后边的博客中我们还会介绍其他类型的树,比如红黑树,B树等等,以及这些...

191100
来自专栏开发与安全

从零开始学C++之虚继承和虚函数对C++对象内存模型造成的影响(类/对象的大小)

首先重新回顾一下关于类/对象大小的计算原则: 类大小计算遵循结构体对齐原则 第一个数据成员放在offset为0的位置 其它成员对齐至min(sizeof(me...

24200
来自专栏Python小屋

针对递归函数的优化与Python修饰器实现

我们围绕一个数学问题来说明本文的思想,组合数C(n,i),也就是从n个元素中任选i个,共有多少种选法。当然,这个问题有很多种求解方法,例如【最快的组合数算法之P...

42690
来自专栏程序员互动联盟

【答疑释惑】C语言里面结构体大小统计方法

之前说过一个关于结构体在内存中所占字节数的问题,我们知道结构体长度的计算并不是所有成员长度的相加,而是因为编译器优化会对其进行对齐,这样会优化访问速度等。 那...

34370
来自专栏数据结构与算法

P1387 最大正方形

题目描述 在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。 输入输出格式 输入格式: 输入文件第一行为两个整数n,m(1<=n...

28650
来自专栏闻道于事

Java异常处理中的恢复模型

30140
来自专栏人工智能头条

TensorFlow架构与设计:变量初始化

10540
来自专栏吴伟祥

关于“分类”的应用 原

三、SQL中区分类别的过滤条件:比如取分类2,那么就是 2=2 <![CDATA[ & ]]>type

9320

扫码关注云+社区

领取腾讯云代金券