Mandelbrot
TCO '03 Qual. Round 2 · 2003-10-07 · by lars2520
TCO '03 Qual. Round 2 · 2003-10-07 · by lars2520 · Math, Simulation
Problem Statement
Problem Statement
A complex number is one of the form a+bi, where a and b are real numbers, and i represents the square root of -1. We call a the real part of the complex number, and b the imaginary part. When multiplying two complex numbers a+bi and c+di, the result is (a*c-b*d)+(a*d+b*c)i. When adding two complex numbers, a+bi and c+di, the result is (a+c)+(b+d)i. Finally, the magnitude of a complex number, a+bi, is sqrt(a*a+b*b).
The Mandelbrot set is a set of complex numbers. To determine whether or not a complex number, C = a+bi, is in the Mandelbrot set, we use the following recurrence:
Z0 = C
Zn+1 = Zn*Zn+C
If, for all n greater than or equal to 0, the magnitude of Zn is less than or equal to 2, then the complex number represented by C = a+bi is in the Mandelbrot set.
You will be given anint , max, representing the maximum value of n to check. For example, if max were 10, you would be required to check Zn for all 0 <= n <= 10. You will also be given two double s, a and b, representing the real and imaginary parts of Z0, respectively. If the magnitude of Zn is always less than or equal to 2, for all 0 <= n <= max, you should return -1. Otherwise, you should return the smallest n such that the magnitude of Zn is greater than 2.
The Mandelbrot set is a set of complex numbers. To determine whether or not a complex number, C = a+bi, is in the Mandelbrot set, we use the following recurrence:
Z0 = C
Zn+1 = Zn*Zn+C
If, for all n greater than or equal to 0, the magnitude of Zn is less than or equal to 2, then the complex number represented by C = a+bi is in the Mandelbrot set.
You will be given an
Constraints
- max will be between 1 and 30, inclusive.
- a will be between -2 and 2, inclusive.
- b will be between -2 and 2, inclusive.
- To prevent rounding errors, the magnitude of Zn will not be within 1e-3 of 2, for any n between 0 and n', inclusive, where n' is the smallest number (or max) such that the magnitude of Zn' is greater than 2.
Examples
0)
5 1 1 Returns: 1
Here, Z0 = 1 + 1i Thus, Z1 = 1 - 1 + 1i + 1i + 1 + 1i = 1 + 3i. The magnitude of 1+3i is sqrt(1*1 + 3*3) = sqrt(10) > 2. Therefore, the return is 1.
1)
2 -1 -1 Returns: 2
Z0 = -1 - 1i Z1 = -1 + 1i Z2 = -1 - 3i
2)
30 .25 .25 Returns: -1
In this example, the magnitude of Zn is never more than 2.
3)
30 -1.9 0 Returns: -1
4)
30 .375 .3 Returns: 21
Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Mandelbrot with a public method int iterations(int max, double a, double b) · 87 test cases · 2 s / 256 MB per case