Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como dividir um retângulo em n triângulos retângulos

0 votos
42 visitas
perguntada Jun 25 em Ciência da Computação por CP (37 pontos)  

Ache todos os valores n > 1 tais que pode-se dividir um retângulo em n triângulos retângulos. Implemente uma solução força bruta para esse problema. Use e abuse de figuras que você gerará computacionalmente (e apresente os códigos usados para isso).

Compartilhe

1 Resposta

0 votos
respondida Jun 25 por CP (37 pontos)  
editado Jul 17 por CP

Duas bibliotecas serão utilizadas:

import matplotlib.pyplot as plt
from math import ceil

Como primeiro passo, determina-se os eixos do gráfico que será gerado:

fig = plt.figure()
plt.axis([-50, 250, -50, 250])
cont = 0

Considerando que o retângulo poderá ser dividido perfeitamente em valor par de triângulos retângulos, um método recursivo será empregado. Sendo desejado dividir em n triângulos, inicialmente divide-se o retângulo em \[\frac{n}{2}\] para posteriormente secciona-lo diagonalmente, obtendo-se 2 triângulos retângulos.

def ret(x1, x2, y1, y2, n):  # Aqui inserimos As coordenadas para a retângulo e a 
   # quantidade de triângulos retângulos desejadas
    plt.plot([x1, x1], [y1, y2], 'k')
    plt.plot([x2, x2], [y1, y2], 'k')
    plt.plot([x1, x2], [y1, y1], 'k')
    plt.plot([x1, x2], [y2, y2], 'k')

    if n == 2:  # Com n = 2 define-se o retângulo para em seguida seccioná-lo na diagonal
        plt.plot([x1, x2], [y2, y1], 'm')

    else:
        # Caso n > 2, divide-se o retângulo em n/2 segmentos, para depois seccionar cada 
            # segmento
        # Na diagonal empregrando um método recursivo
        "Nesse ponto é necessários decidir como a divisão do retângulo será reaalizada." \
            "A fim de assegurar a estética do gráfico, iremos proceder realizando a 
            decomposição" \
            "de n em fatores primos"
        fac = primes_fac(n)  # Lista com a decomposição de n em fatores primos
        div = ceil((len(fac))/2)
        multv = 1
        multh = 1
        for t in range(1, div):  # Em quais ponto o retângulo será seccionado na vertical
            multv = fac[t] * multv
        for g in range(div, len(fac)):  # Em quais ponto o retângulo será seccionado na 
            # horizontal
            multh = fac[g] * multh
        incrx = (x2 - x1) / multh
        incry = (y2 - y1) / multv
        xi = [x1]
        yi = [y1]
        y3 = y1
        x3 = x1
        for s in range(int(multh)):
            x3 = x3 + incrx
            xi.append(x3)
        for i in range(int(multv)):
            y3 = y3 + incry
            yi.append(y3)

        for j in range(len(xi) - 1):  # Aplicação recursiva sobre cada retângulo
            for t in range(len(yi) - 1):
                ret(xi[j], xi[j + 1], yi[t], yi[t + 1], 2)


def primes_fac(n):  # Função para a decomposição de n em fatores primos
    primes = [2]
    factor = []
    for i in range(3, n+1, 2):
        primes.append(i)
    for j in range(len(primes)):
        while n % primes[j] == 0:
            factor.append(primes[j])
            n = n / primes[j]
            if n == primes[j]:
                factor.append(primes[j])
                break
    return factor


if __name__ == '__main__':
    ret(0, 100, 0, 200, 40)  # O retângulo será de 100 por 200, sendo dividido em 40 
    # triângulos
    plt.savefig("RET")

Como resultado tem-se:

A imagem será apresentada aqui.

o código acima valerá para n par, de modo a se obter n triângulo igual tamanho. Para que o código seja válido para n arbitrário, considerar:

    def ret(x1, x2, y1, y2, n):  # Aqui inserimos As coordenadas para a retângulo e a 
       # quantidade de triângulos retângulos desejadas
        plt.plot([x1, x1], [y1, y2], 'k')
        plt.plot([x2, x2], [y1, y2], 'k')
        plt.plot([x1, x2], [y1, y1], 'k')
        plt.plot([x1, x2], [y2, y2], 'k')

        if n == 2:  # Com n = 2 define-se o retângulo para em seguida seccioná-lo na diagonal
            plt.plot([x1, x2], [y2, y1], 'm')

        elif n // 2 == 0: 
            # Caso n > 2, divide-se o retângulo em n/2 segmentos, para depois seccionar cada 
                # segmento
            # Na diagonal empregrando um método recursivo
            "Nesse ponto é necessários decidir como a divisão do retângulo será reaalizada." \
                "A fim de assegurar a estética do gráfico, iremos proceder realizando a 
                decomposição" \
                "de n em fatores primos"
            fac = primes_fac(n)  # Lista com a decomposição de n em fatores primos
            div = ceil((len(fac))/2)
            multv = 1
            multh = 1
            for t in range(1, div):  # Em quais ponto o retângulo será seccionado na vertical
                multv = fac[t] * multv
            for g in range(div, len(fac)):  # Em quais ponto o retângulo será seccionado na 
                # horizontal
                multh = fac[g] * multh
            incrx = (x2 - x1) / multh
            incry = (y2 - y1) / multv
            xi = [x1]
            yi = [y1]
            y3 = y1
            x3 = x1
            for s in range(int(multh)):
                x3 = x3 + incrx
                xi.append(x3)
            for i in range(int(multv)):
                y3 = y3 + incry
                yi.append(y3)

            for j in range(len(xi) - 1):  # Aplicação recursiva sobre cada retângulo
                for t in range(len(yi) - 1):
                    ret(xi[j], xi[j + 1], yi[t], yi[t + 1], 2)

    else:
            n1 = (n//2)*2
            fac = primes_fac(n1)  # Lista com a decomposição de n em fatores primos
            div = ceil((len(fac)) / 2)
            multv = 1
            multh = 1
        for t in range(1, div):  # Em quais ponto o retângulo será seccionado na vertical
            multv = fac[t] * multv
        for g in range(div, len(fac)):  # Em quais ponto o retângulo será seccionado na 
horizontal
            multh = fac[g] * multh
        incrx = (x2 - x1) / multh
        incry = (y2 - y1) / multv
        xi = [x1]
        yi = [y1]
        y3 = y1
        x3 = x1
        for s in range(int(multh)):
            x3 = x3 + incrx
            xi.append(x3)
        for i in range(int(multv)):
            y3 = y3 + incry
            yi.append(y3)

        print(f' X:{xi} e Y: {yi}')

        for j in range(len(xi) - 1):  # Aplicação recursiva sobre cada retângulo
            for t in range(len(yi) - 1):
                ret(xi[j], xi[j + 1], yi[t], yi[t + 1], 2)

        h(xi[len(xi)-2], xi[len(xi)-1], yi[len(yi)-2], yi[len(yi)-1])


    def primes_fac(n):  # Função para a decomposição de n em fatores primos
        primes = [2]
        factor = []
        for i in range(3, n+1, 2):
            primes.append(i)
        for j in range(len(primes)):
            while n % primes[j] == 0:
                factor.append(primes[j])
                n = n / primes[j]
                if n == primes[j]:
                    factor.append(primes[j])
                    break
        return factor

def h(c1, c2, d1, d2):
    tga = (d2-d1)/(c2-c1)
    tgb = (c2-c1)/(d2-d1)
    anga = math.atan(tga)
    angb = math.atan(tgb)
    # print(angb + anga)
    cat_ad1 = (c2-c1)*math.cos(angb)
    cat_ad2 = cat_ad1*math.cos(anga)
    cat_op1 = cat_ad1*math.sin(anga)
    c3 = c1 + cat_op1
    d3 = d1 + cat_ad2
    plt.plot([c1, c3], [d1, d3])
    # tgaux = cat_ad2/cat_op1
    # print(math.atan(tgaux)+anga)

if __name__ == '__main__':
    ret(0, 100, 0, 200, 13)  # O retângulo será de 100 por 200, sendo dividido em 13
    # triângulos
    plt.savefig("RET1")
comentou Jul 12 por Pedro Gomes (16 pontos)  
Excelente resolução, acho que a linha
plt.axis([-50, 250, -50, 250])
não é necessária, o código funciona normalmente sem essa linha.
comentou Jul 13 por danielcajueiro (5,786 pontos)  
Cara CP, sua solução aparentemente não funciona para valores impares.
comentou Jul 13 por danielcajueiro (5,786 pontos)  
Teste por exemplo n=3 ou n=5
comentou Jul 13 por danielcajueiro (5,786 pontos)  
Uma solução para esse problema pode ser encontrada em Algorithm Puzzles - Levitin and Levitin
comentou Jul 17 por CP (37 pontos)  
editado Jul 17 por CP
Bem colocado, professor. Ao fazer a questão pensei em seccionar em triângulos iguais. Vendo a referência sugerida entendi melhor a proposta.  Adicionarei a possibilidade para n ímpar em minha resposta. Grata pela observação.
...