Projete um algoritmo em pseudocódigo que, dada uma árvore de decisão codificada como nós com condição e…

Questão

Projete um algoritmo em pseudocódigo que, dada uma árvore de decisão codificada como nós com condição e referências a filhos, gere todas as regras (caminhos da raiz às folhas). Descreva as variáveis-chave, a estrutura de dado usada para armazenar as regras e como o algoritmo trata variáveis de condição repetidas.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Representação: cada nó tem campos condicion (string), filho_esq, filho_dir, e valor_folha opcional. Variáveis-chave: stack caminho (lista de pares condição?valor), lista_regras (vetor de strings). Algoritmo (DFS recursivo): func gerar_regras(no, caminho): if no == null: return if no.valor_folha != null: regra = concatenar(caminho) + ' => ' + str(no.valor_folha) adicionar lista_regras, regra return // nó interno com condição; ao descer, anotar condição com valor true/false conforme ramo // Exemplo para árvore binária de condição booleana: adicionar fim(caminho, no.condicao + ' = true') gerar_regras(no.filho_esq, caminho) remover_ultimo(caminho) adicionar fim(caminho, no.condicao + ' = false') gerar_regras(no.filho_dir, caminho) remover_ultimo(caminho) Início: lista_regras = [] ; gerar_regras(raiz, []) ; retornar lista_regras. Tratamento de variáveis repetidas: ao concatenar caminho, manter condições na ordem de visita e, se uma mesma variável aparecer múltiplas vezes com valores compatíveis, manter ambas; se conflitantes, priorizar a condição mais próxima da folha ou detectar inconsistência e marcar regra inválida. Armazenamento das regras: lista de strings estruturadas ou registros {condicoes: lista, resultado: valor}. Complexidade: percorre cada nó uma vez, O(n) tempo e O(h) espaço de pilha (h = altura). Observações de implementação: usar estruturas mutáveis para caminho (push/pop) para eficiência; ao serializar regras, normalizar nomes de variáveis para evitar duplicação semântica.

Explicação

A explicação aborda a representação adequada da árvore de decisão e define claramente as variáveis e estruturas de dados necessárias para armazenar as regras geradas. O algoritmo utiliza uma abordagem de busca em profundidade, que é eficiente para percorrer todos os caminhos da raiz às folhas, garantindo que todas as condições sejam consideradas. Além disso, o tratamento de variáveis repetidas é bem fundamentado, assegurando que as regras sejam geradas de forma consistente e válida.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo em pseudocódigo que, dada uma árvore enraizada representada por nós com referências a filhos e uma…
• Descreva um algoritmo em pseudocódigo que, dada uma árvore enraizada onde cada nó mantém uma lista arbitrária de filhos…
• Projete um algoritmo em pseudocódigo que receba uma lista de strings binárias (dados) e construa uma trie (árvore de…
• Projete um algoritmo (pseudocódigo) baseado em Kruskal ou Prim que, dado um grafo conectado ponderado (dados: lista de…
• Considere uma árvore binária. Em linguagem corrente ou pseudocódigo, descreva a ordem de visita do percurso pré-ordem…
• Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado conectado e um vértice raiz, construa a…

Todas as questões de Algoritmos