Início / coding / Perguntas / 79446920
Accepted
Linda
Asked: 2025-02-18 09:05:35 +0800 CST

Por que o MDC é necessário neste algoritmo para descobrir se todos os grupos de três pontos são colineares no plano de coordenadas cartesianas?

  • 772

Eu estava tentando resolver este desafio de codificação: "Dado um conjunto de pares, cada par (x, y), ambos inteiros, denota a coordenada de um ponto no plano de coordenadas cartesianas. Encontre muitos grupos de três pontos que são colineares."

Acontece que o algoritmo correto é o seguinte:

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def how_many_3point_in_line( points ):
    ans = 0
    n = len( points )
    for i in range( n - 2 ):
        slopes = defaultdict( int )
        for j in range( i + 1, n ):
            dy, dx = points[i][1] - points[j][1], points[i][0] - points[j][0]
            gcd_num = gcd( dx, dy )
            slopes[( dy // gcd_num, dx // gcd_num )] += 1
        for _, occ in slopes.items():
            ans += math.comb( occ, 2 )
    return ans

Aparentemente o mdc é usado para representar a inclinação. Que problema ele aborda?

python

1 respostas

  1. Best Answer

    Um esclarecimento:

    Muito obrigado pelo ensinamento do colega sem comentários . De fato, o MDC na solução publicada pelo OP é necessário, e minha resposta original está errada.

    Tomando points = [(0, 0), (999999997, 999999998), (999999998, 999999999)]como exemplo, a diferença entre 999999997/999999998e 999999998/999999999aparece somente após tantos dígitos decimais que o número de ponto flutuante não inclui, levando a 999999997/999999998 == 999999998/999999999ser avaliado como Verdadeiro.

    Também encontrei esta resposta que discutiu muito bem um tópico relacionado.

    Esta resposta foi marcada como aceita, então não posso excluí-la; vou mantê-la aqui como um contraexemplo.

    Resposta original (errada):

    Acho que o autor do seu código está tentando resolver a imprecisão da representação de ponto flutuante.

    Mas essa preocupação é realmente desnecessária, dado que x e y são inteiros, por exemplo, 3,0/9,0 == 9,0/27,0 lhe dará Verdadeiro, estudei recentemente sobre um tópico relacionado e posso, portanto, confirmar isso. O único caso em que você (pode ou não) ter problemas é quando o denominador ou numerador é um número de ponto flutuante, o que não se aplica à sua pergunta.

    Então, você pode modificar a solução para usar simplesmente a inclinação numérica, mas precisa lidar especialmente com o caso em que dx é 0, caso contrário, você obtém a exceção “dividido por zero”.

    def how_many_3point_in_line( points ):
    ans = 0
    n = len( points )
    for i in range( n - 2 ):
        slopes = defaultdict( int )
        numVertical = 0
        for j in range( i + 1, n ):
            dy, dx = points[i][1] - points[j][1], points[i][0] - points[j][0]
            if dx != 0:
                slopes[dy / dx] += 1
            else:
                numVertical += 1
        for _, occ in slopes.items():
            ans += math.comb( occ, 2 )
        ans += math.comb( numVertical, 2 )
    return ans
    • 4

relate perguntas