Splitting a line into a number of segments

Question

Splitting a line into a number of segments

Navigation

#1 by (1 votes)

1

I need to split a line into multiple segments, and all segments need to be integers. But sometimes the division of distância / segmentos results in a number that truncated does not cover all distance and taken to the ceiling exceeds the total size of the line. How do I divide the number of segments in a way that covers the desired area, and this segment can have two different values.

Ex: I have a of a size and b e. other, use x times a and y times b to exactly cover the desired distance?

algoritmo

asked by anonymous 10.04.2015 / 07:13

1 answer

How to focus on a specific browser tab from a php check Align vertically to footer items center

score 1 · Accepted Answer

Diophantine equations

A Diophantine equation is a polynomial equation where only integer solutions are desired (more information on wikipedia ).

In your case, you want to solve the following equation:

a * x + b * and + c * z + ... = C

where a, b, c ... are the measures of the segments you want; x, y, z ... are the quantities of each (the unknowns) and C is the total length of its segment.

For the rest of the answer I will assume you want to divide the C segment into pieces of 2 sizes, x and y.

First-order diophantine equation

To solve the equation:

a * x + b * y = C

We need to first know if it has a solution. This equation has solution with x and 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 has only C's answer is a multiple of mdc (a, b) we can solve it. To do this, call 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 some accounts let's stick with something of the form

s * a + t * b = g

This equation is easy to solve on the computer, we just need to use the Euclidean extended version algorithm!

The Euclidean algorithm

I think everyone implemented this once when they learned to program. It is used 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 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 seek is x = s * (c / g) and y = t * (c * g).