Diophantine equations
A Diophantine equation is a polynomial equation in which only integer solutions
are desired (more information on
wikipedia).
In your case, you want to solve the following equation:
a * x + b * y + c * z + ... = C
where a, b, c... are the measurements of the segments you want; x, y, z... are the
quantities of each (unknown) and C is the total length of its segment.
For the rest of the answer I’ll assume you want to split segment C into pieces of 2 sizes, x and y.
First order Diophantine equation
To solve the equation:
a * x + b * y = C
we first need to know if it has solution. This equation has solution with x
y integers only if C is of the form K * mdc(a, b). That is, C is a multiple of
maximum common divisor of a and b.
A little bit of math
Now that we know that the equation only has C response is multiple of mdc(a, b)
we can solve it. To do this, call g o mdc(a, b). Both a * x + b * y must
be divisible by g, and C also, since it is of the form K * g. Therefore, we can
divide both sides of the equation by c / g and after a few accounts we will get something of the form
s * a + t * b = g
This equation is easy to solve on the computer, we just need to use the Euclid algorithm extended version!
The algorithm of Euclid
I think everyone implemented this one once when they learned to program. It serves to calculate the mdc between two numbers. The extended version of it will calculate the value of s and t in the above equation.
Copied discaradamente from wikipedia:
function extended_gcd(a, b)
s := 0; old_s := 1
t := 1; old_t := 0
r := b; old_r := a
while r ≠ 0
quotient := old_r div r
(old_r, r) := (r, old_r - quotient * r)
(old_s, s) := (s, old_s - quotient * s)
(old_t, t) := (t, old_t - quotient * t)
output "greatest common divisor:", old_r
output "quotients by the gcd:", (t, s)
Now that we know s and t, the answer we’re looking for is x = s * (c / g) and y = t * (c * g).
And what’s the problem you have? and what programming language do you want to use for that calculation?
– Sergio
Java, but it’s more an algorithm problem to do this, than an implementation problem.
– pmargreff
I usually solve this problem by subtracting the segments in the desired precision, so the rounding error is discounted in the next ones. In certain situations it is preferable to have a small variation between the pieces, but the total coincides with the initial measure.
– Bacco
@Bacco This is my intention, further develop your idea ....
– pmargreff
There are several ways, one of them is you when making each division, subtract the total of the segment you just created, and divide this remaining segment by n - 1. Example: length 9 divided by 7, with 2 decimal places of precision: 1.29 (gives more houses than that). Take 9 - 1.29 = 7.71 and divide these 7.71 by 6. Gives 1.29 again (rounding). Caught 7.71 - 1.29 = 6.42 and divided by 5... this time the rounding gives 1.28. I repeat the process dividing ( 6.42 - 1.28 ) by 4, and so on. In the end, the sums will beat with the total, and the error distributed by the pieces (there are other means, it was just example).
– Bacco
Do the segments have to be equal to each other? Can there be space between them? Can you give an example via image?
– Jorge B.
Segments need not be equal to each other, but must be integer.
– pmargreff
@pmargreff note that the example I gave uses 2 decimals, but works perfectly for integers.
– Bacco