递归创建阿波罗垫片[有了解决方案] [英] Recursively create apollonian gaskets [With solution]

问题描述

阿波罗垫片=它们是从圆的三元组，其中每一圈相切其他两个生成平面分形。在他的垫片的图纸，我们开始了两个外切圆直径这是D1和D2。然后，我们添加第三个圆其直径为D1 + D2和到原来的两个圆是内切。这是第一代圈。 每个后续一代圈的构造通过采用以下方案： 对于任何三个圆A，任何previous几代这是相切的一个新的循环构造是相切的A，B，C的BC。新的圈子必须不同于迄今为止建造各界。当生成完成，即没有其他的圈可以被添加，那么下一代圈可以开始正在建设中。

Apollonian gaskets = They are planar fractals generated from triples of circles, where each circle is tangent to the other two. In his drawing of the gasket, we start with two externally tangent circles which diameter is D1 and D2. Then we add a third circle which diameter is D1+D2 and to which the two original circles are internally tangent. This is the first generation of circles. Each subsequent generation of circles is constructed by applying the following scheme: For any three circles A, B C of any previous generations which are tangent to each other a new circle is constructed which is tangent to A,B,C. The new circle must differ from all circles constructed so far. When a generation is complete, i.e no other circle can be added, then the next generation of circles can start being constructed.

还有一个额外的停车规则，起价产生无穷小圆圈p $ pvents。的圆可以被添加到所述垫片当且仅当其直径的lenght是至少MIND这是一个固定的正值。

There is an additional stopping rule which prevents from generating infinitesimally small circles. A circle can be added to the gasket if and only if the lenght of its diameter is least minD which is a fixed positive value.

输入由三个十进制数D1，D2和心灵一行。数之间用空格分隔。该格式是常用的十进制格式（另见示例波纹管），没有指数部分。 它认为，1.0≤D1，D2≤1000.0，0.001≤介意≤D1 + D2。

Input consists of one line with three decimal numbers D1, D2 and minD. The number are separated by spaces. The format is usual decimal format (see also the examples bellow) with no exponent part. It holds that 1.0 ≤ D1, D2 ≤ 1000.0, 0.001 ≤ minD ≤ D1+D2.

输出继电器由一个包含两个十进制数的L1和L2的文本行的。 L1重新presents各界的面积之和的垫片除了bigggest圈。 L2重新presents各界周边的总和锡垫片除了bigggest圈。这两个输出值四舍五入到6位小数。小数位数必须始终美元的，即使其中有些是零的输出P $ psent。 Maximim输出值小于107。

Ouput consists of one text line containing two decimal numbers L1 and L2. L1 represents the sum of areas of all circles in the gasket except for the bigggest circle. L2 represents the sum of perimeters of all circles in tin the gasket except for the bigggest circle. Both output values are rounded to 6 decimal digits. Decimal digits must be always present in the output even if some of them are zeros. Maximim output value is less than 107.

输入

17.000000 40.000000 1.000000

输出

2439.258588 835.263228

2

2

对于给定的D1和D2，我创建这个两个圆圈所示（第一次迭代）：

For given D1 and D2, I create this two circles like this (first iteration):

   double D1 = 17.00;
   double D2 = 40.00;
   double minD = 1.00;
   int i = 250, j = 350;
   comp.addCircle(i, j, (int) D2, randomColor);
   comp.addCircle(i + (int) D2 / 2 + (int) D1 / 2, j, (int) D1, randomColor);
   comp.addCircle(i + (int) D1 / 2, j, (int) (D1 + D2), randomColor);

更新：

那么，解决方案是基于笛卡尔定理。我们很好地半径，不是直径和曲率，用的是工作 1 / R 。 我们将使用双所有的计算，但如果你的工作与显著小的数字，我想preFER的BigDecimal。它会缓慢算法，你应该寻找平方根使用外部方法，因为BigDecimal的没有任何。

So, solution is based on Descartes' theorem. We well work with radius, not diameter, and Curvature, with is 1/r. We will use double for all calculation, but if you work with significantly small numbers, I would prefer BigDecimal. It will slow algorithm, and you should use external method for finding square root, because BigDecimal doesn't have any.

对于给定的D1，D2，介意我们修改code以上的效率：

For given D1, D2, minD we modify code above for efficiency:

有些preparation：

Some preparation:

 double D1 = sc.nextDouble() / 2;
 double D2 = sc.nextDouble() / 2;
 minD = sc.nextDouble() / 2;
 double D3 = D1 + D2;

所以，第一个步骤是这样的：

So, first step looks like this:

下一步看起来有点复杂。

Next step looks a little bit more complicated.

假设我们要递归写来解决这个问题，并根据笛卡尔定理，为三个圆，相切对方，给定的曲率（下面峰）。 ，我们可以发现曲率的两个圆，但是作为我们的目的，我们只需要小的，所以，我们可以简化公式

Assume we want to write a recursion to solve this problem, and according to Descartes' theorem, for given curvatures of three circles, tangent to each other, (pic. below) , we could find curvatures of two circles, but for our purposes, we need only small one, so, we can simplify formula to

this.curve = a.curve + b.curve + c.curve + 2 * Math.sqrt(Math.abs(a.curve * b.curve + a.curve * c.curve + b.curve * c.curve));

让我们再次来看看阿波罗垫片：尽量发挥它。 看到？这是一样的垫圈，但具有不同的启动条件。和最新对我们更重要的是，是，它是对称的！因此，我们将计算短短一个半月，然后乘以两个结果！ 让我们写一个递归！输入将是三个圆圈曲率。无输出，我们将使用改变我们的全局变量。

Lets take a look at Apollonian gaskets again: try to play with it. See? It is same gaskets, but with different start condition. And whats more important for us, is that it is symmetrical! So, we will calculate just a half, and then multiply result by two! Lets write a recursion! Inputs will be curvatures of three circles. No output, we will use change our global variables.

double radius_sum = 0.0;
double square_radius_sum = 0.0;

void createAG(double a, double b, double c){
 double n = a + b + c + Math.sqrt(a*b + a*c + b*c + 4.0); 
 if ((minD * n) < 1){
     radius_sum += 2. / n; //Remember about symmetry? 
     square_radius_sum += 2. * (1. / n) * (1. / n); //Remember about symmetry? 
     createAG(a, b, n);
     createAG(a, c, n);
     createAG(b, c, n);
   }
}

要查找的结果，我们将用公式来计算面积和圆的周长。 周长是圆周的长度，等于。 面积等于，因为你已经知道了，因为我们已经计算出它在previous一步，否则我们不得不存储每个半径和做更多的计算。

To find the result, we will use formulas to calculate area and perimeter of circle. Perimeter is length of circumference and equal to . Area is equal to , as you already know, because we already calculated it in previous step, otherwise we had to store every radius and do more calculations.

radius_sum  = 2 * Math.Pi * radius_sum;
square_radius_sum = Math.Pi * square_radius_sum;

但我们忘记了我们的第一个两界！让我们来解决它！

But we forget about our first two circles! Let's fix it!

   radius_sum  += D1*2 + D2*2;
   square_radius_sum += D1*D1 + D2*D2;
   radius_sum  = 2 * Math.Pi * radius_sum;
   square_radius_sum = Math.Pi * square_radius_sum;

和总有一个改进的余地。例如，使用 IEEE 754 更好的办法，我想你会使用 1。 / X 而不是 1 / X 。

And there is always a room for improvement. For example, to use IEEE 754 in better way, I assume you will use 1. / x instead of 1 / x.

谢谢！

P.S。版权！这个任务（文字和阿波罗垫片的第一张图片）是由教师在CTU，为当然的 ALG 。图片公式是从维基百科。一切是公共领域，如果没有申请专利，注册等

P.S. Copyright! This task (text and first picture of Apollonian gasket) is created by teachers at CTU, for course ALG. Picture of formulas is from Wikipedia. Everything else is public domain, if not patented, registered e.t.c.

推荐答案

那么，解决方案是基于笛卡尔定理。我们很好地半径，不是直径和曲率，用的是工作 1 / R 。 我们将使用双所有的计算，但如果你的工作与显著小的数字，我想preFER的BigDecimal。它会缓慢算法，你应该寻找平方根使用外部方法，因为BigDecimal的没有任何。

So, solution is based on Descartes' theorem. We well work with radius, not diameter, and Curvature, with is 1/r. We will use double for all calculation, but if you work with significantly small numbers, I would prefer BigDecimal. It will slow algorithm, and you should use external method for finding square root, because BigDecimal doesn't have any.

对于给定的D1，D2，介意我们修改code以上的效率：

For given D1, D2, minD we modify code above for efficiency:

有些preparation：

Some preparation:

 double D1 = sc.nextDouble() / 2;
 double D2 = sc.nextDouble() / 2;
 minD = sc.nextDouble() / 2;
 double D3 = D1 + D2;

所以，第一个步骤是这样的：

So, first step looks like this:

下一步看起来有点复杂。

Next step looks a little bit more complicated.

假设我们要递归写来解决这个问题，并根据笛卡尔定理，为三个圆，相切对方，给定的曲率（下面峰）。 ，我们可以发现曲率的两个圆，但是作为我们的目的，我们只需要小的，所以，我们可以简化公式

Assume we want to write a recursion to solve this problem, and according to Descartes' theorem, for given curvatures of three circles, tangent to each other, (pic. below) , we could find curvatures of two circles, but for our purposes, we need only small one, so, we can simplify formula to

this.curve = a.curve + b.curve + c.curve + 2 * Math.sqrt(Math.abs(a.curve * b.curve + a.curve * c.curve + b.curve * c.curve));

让我们再次来看看阿波罗垫片：尽量发挥它。 看到？这是一样的垫圈，但具有不同的启动条件。和最新对我们更重要的是，是，它是对称的！因此，我们将计算短短一个半月，然后乘以两个结果！ 让我们写一个递归！输入将是三个圆圈曲率。无输出，我们将使用改变我们的全局变量。

Lets take a look at Apollonian gaskets again: try to play with it. See? It is same gaskets, but with different start condition. And whats more important for us, is that it is symmetrical! So, we will calculate just a half, and then multiply result by two! Lets write a recursion! Inputs will be curvatures of three circles. No output, we will use change our global variables.

double radius_sum = 0.0;
double square_radius_sum = 0.0;

void createAG(double a, double b, double c){
 double n = a + b + c + Math.sqrt(a*b + a*c + b*c + 4.0); 
 if ((minD * n) < 1){
     radius_sum += 2. / n; //Remember about symmetry? 
     square_radius_sum += 2. * (1. / n) * (1. / n); //Remember about symmetry? 
     createAG(a, b, n);
     createAG(a, c, n);
     createAG(b, c, n);
   }
}

要查找的结果，我们将用公式来计算面积和圆的周长。 周长是圆周的长度，等于。 面积等于，因为你已经知道了，因为我们已经计算出它在previous一步，否则我们不得不存储每个半径和做更多的计算。

To find the result, we will use formulas to calculate area and perimeter of circle. Perimeter is length of circumference and equal to . Area is equal to , as you already know, because we already calculated it in previous step, otherwise we had to store every radius and do more calculations.

radius_sum  = 2 * Math.Pi * radius_sum;
square_radius_sum = Math.Pi * square_radius_sum;

但我们忘记了我们的第一个两界！让我们来解决它！

But we forget about our first two circles! Let's fix it!

   radius_sum  += D1*2 + D2*2;
   square_radius_sum += D1*D1 + D2*D2;
   radius_sum  = 2 * Math.Pi * radius_sum;
   square_radius_sum = Math.Pi * square_radius_sum;

和总有一个改进的余地。例如，使用 IEEE 754 更好的办法，我想你会使用 1。 / X 而不是 1 / X 。

And there is always a room for improvement. For example, to use IEEE 754 in better way, I assume you will use 1. / x instead of 1 / x.

谢谢！

P.S。版权！这个任务（文字和阿波罗垫片的第一张图片）是由教师在CTU，为当然的 ALG 。图片公式是从维基百科。一切是公共领域，如果没有申请专利，注册等

P.S. Copyright! This task (text and first picture of Apollonian gasket) is created by teachers at CTU, for course ALG. Picture of formulas is from Wikipedia. Everything else is public domain, if not patented, registered e.t.c.

这篇关于递归创建阿波罗垫片[有了解决方案]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！