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

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

0 votos
22 visitas
perguntada Jun 25 em Ciência da Computação por CP (32 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 (32 pontos)  
editado 1 dia atrás 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 6 dias atrás 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 5 dias atrás por danielcajueiro (5,566 pontos)  
Cara CP, sua solução aparentemente não funciona para valores impares.
comentou 5 dias atrás por danielcajueiro (5,566 pontos)  
Teste por exemplo n=3 ou n=5
comentou 5 dias atrás por danielcajueiro (5,566 pontos)  
Uma solução para esse problema pode ser encontrada em Algorithm Puzzles - Levitin and Levitin
comentou 1 dia atrás por CP (32 pontos)  
editado 1 dia atrás 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.
...